NAME: SID#: Section: 1CS 188 Introduction to AISpring 2004 Stuart RussellMidtermYou have 50 minutes. The exam is open-book, op en-notes. 100 points total. Panic not.ALL QUESTIONS IN THIS EXAM ARE TRUE/FALSE, MULTIPLE- CHOICE, OR SHORT-ANSWER.Mark your answers ON THE EXAM ITSELF. Write your name, SID, and section number at the top of each page.For tr ue/false questions, CIRCLE True OR False.For multiple-choice questions, CIRCLE ALL CORRECT CHOICES (in some cases, there may be mo re than one).If you are not sure of your answer you may wish to pr ovide a brief explanation.For official use onlyQ. 1 Q. 2 Q. 3 Q. 4 Q. 5 Q. 6 Total/12 /15 /25 /12 /18 /18 /1001. (12 pts.) Agents and Environments(a) (3) True/False: There exist task environments (PEAS) in which some pure reflex agents behave rationally.(b) (3) True/False: There exist task environments (PEAS) in which all pure r eflex agents behave irr ationally.(c) (3) True/False: The input to an agent program is the same as the input to the corresponding agentfunction.(d) (3) True/False: Every age nt function is implementable by s ome program/machine combination2. (15 pts.) SearchConsider the problem o f moving k knights from k starting squares s1, . . . , skto k goal squares g1, . . . , gk, onan unbounded chessboard, subject to the rule that no two knights can land on the same square at the sametime. Each action consists of moving up to k knights simultaneously. We would like to complete the maneuverin the smallest number of actions.(a) (5) What is the maximum branching factor b in this state space?(i) 8k (ii) 9k (iii) 8k(iv) 9k(b) (6) Suppose hiis an admissible heuristic for the problem of moving knight i to goal giby itself. Which ofthe following heuristics are admissible for the k-knight problem?(i) min{h1, . . . , hk} (ii) max{ h1, . . . , hk} (iii)!ki = 1hi(c) (4) Which of these is the best heuristic?(i) min{h1, . . . , hk} (ii) max{ h1, . . . , hk} (iii)!ki = 1hi23. (25 pts.) CSPs and local searchConsider the pr oblem of placing k kn ights on an n × n chessboa rd such that no two knights are attacking eachother, wher e k is given and k ≤ n2.(a) (5) Choose a CSP formulation. In your formulation, wha t are the variables?(b) (5) What are the values of each variable?(c) (5) What sets of variables are constrained, and how?(d) (5) Now co nsider the problem of putting as many knights as possible on the board without any attacks.We will so lve this using local search. Briefly describe in English a sensible successor function.(e) (5) Briefly describe in English a sensible objective function.NAME: SID#: Section: 34. (12 pts.) Propositional logicConsider a propositiona l language with four symbols, A, B, C, and D. How many models are there for ea ch ofthe following sentences?(a) (4) B ∨ C(b) (4) ¬A ∨ ¬B ∨ ¬C ∨ ¬D(c) (4) (A ⇒ B) ∧ A ∧ ¬B ∧ C ∧ D5. (18 pts.) Propositional logicAccording to p olitical pundits, a person who is radical (R) is electable (E) if he/she is conservative (C), butotherwise is not electable.(a) (12) Which of the following are correct representations of this assertion?i. (R ∧ E) ⇐⇒ Cii. R ⇒ (E ⇐⇒ C)iii. R ⇒ ((C ⇒ E) ∨ ¬E)(b) (6) Which of the sentences in (a) can be expressed in Horn form?(i) (ii) (iii)6. (18 pts.) First-Order Logic(a) (12) Which of the following are correct translations of “No two adjacent countries have the same color”?i. ∀x, y ¬Country(x) ∨ ¬Country(y) ∨ ¬Adja cent(x, y) ∨ ¬(Color(x) = Color(y)).ii. ∀x, y (Country(x) ∧ Country(y) ∧ Adjacent(x, y) ∧ ¬(x = y)) ⇒ ¬(Color(x) = Color(y)).iii. ∀x, y Country(x) ∧ Country(y) ∧ Adjacen t(x, y) ∧ ¬(Color(x) = Color(y))iv. ∀x, y (Country(x) ∧ Country(y) ∧ Adjacen t(x, y)) ⇒ Color(x (= y).(b) (6) Which of the following are valid sentences?i. (∃x x = x) ⇒ (∀y ∃z y = z).ii. ∀x P (x) ∨ ¬P (x).iii. ∀x Smart(x) ∨ (x =
View Full Document
Unlocking...