UNIVERSITY OF SOUTHAMPTON COMP6231W1 SEMESTER 1 FINAL ASSESSMENT 2020 - 2021 FOUNDATIONS OF ARTIFICIAL INTELLIGENCE DURATION 5 Hours This paper contains 4 questions You must answer ALL questions. Each question is worth 25 points An outline marking scheme is shown in brackets to the right of each ques- tion. 8 page examination paper. Copyright 2021 c University of Southampton Page 1 of 8 COMP6231W1 Question 1. A student is writing a program to solve a puzzle. In the puzzle there are 5 moves that can be made from each state. From the nature of the puzzle it is clear that solutions exist, and (unusually) it is also known that some solutions exist at a depth of 100 and all others at depth of 104. The rules of the puzzle ensure that after 200 moves from the start position there are no further moves possible (i.e. maximum depth of search tree=200). Each move has a cost of 6. For the following questions, where appropriate show the relevant formula and give a numerical answer (i.e. show that you can plug in the correct numbers to the formulae you know). The first approach the student considers is to use tree search with a breadth first strategy (BFS). (a) How many nodes will this method generate in the worst case? [2 marks] (b) What is the maximum number of nodes that will be stored in memory at any one time? [2 marks] (c) What will be the cost of the solution that it finds if it finds one? [2 marks] The second approach the student considers is to use tree search with a depth first strategy (DFS). (d) How many nodes will this method generate in the worst case? [2 marks] (e) What is the maximum number of nodes that will be stored in memory at any one time? [2 marks] Copyright 2021 c University of Southampton Page 2 of 8 COMP6231W1 (f) What will be the cost of the solution that it finds if it finds one? [2 marks] The student contemplates their options. They have a supercomputer that can generate 10 million search nodes per second and store up to 1020 nodes. (g) Explain whether either of these methods definitely, or even possibly, finds a solution given these resources. Include yes/no summary an- swers for BFS definite, BFS possible, DFS definite, DFS possible. [10 marks] The student then realises that they can easily compute something poten- tially useful about any state in this puzzle. Specifically, it is possible to calculate (in constant time), for any given state, exactly how many moves this state is away from reaching a solution. (h) Explain briefly what method the student should use to best utilise this information? [3 marks] Copyright 2021 c University of Southampton TURN OVER Page 3 of 8 COMP6231W1 Question 2. (a) The following shows a game tree. Player 1 is maximising and it is player 1’s turn to move. (i) What is the value of the game to player 1? [1 marks] (ii) Using the minimax algorithm with alpha-beta pruning, and as- suming the usual left-to-right traversal, indicate the branches that can be pruned. [10 marks] (b) The following figure shows a partially completed graph-colouring prob- lem using 3 colours. Nodes 3, 9 and 13 have been assigned the same colour and node 8 has been assigned a different colour. Other nodes do not yet have a colour assigned. Which node do you assign a colour to next? Explain briefly. [2 marks] Copyright 2021 c University of Southampton Page 4 of 8 COMP6231W1 (c) The following figure shows a partially completed graph-colouring prob- lem using 3 colours. Nodes 3 and 9 have been assigned the same colour. Other nodes do not yet have a colour assigned. Which node do you assign a colour to next? Explain briefly. [2 marks] (d) Briefly describe (one or two sentences each) the ways in which these statements are true and/or untrue? (simply writing ‘true’/‘false’ an- swers without justification is insufficient for a mark) (i) The Turing test is a practical test of intelligence because it de- scribes exactly how to conduct the test and it doesn’t need us to define intelligence. [2 marks] (ii) If a computer passed the Turing Test it must be really intelligent. [2 marks] (iii) If a computer can answer a question with the right symbol then it must know what that symbol means. [2 marks] (iv) Rodney Brooks built robots to show that good old-fashioned AI could do anything we needed. [2 marks] (v) Being able to play chess captures everything difficult about intel- ligence. [2 marks] Copyright 2021 c University of Southampton TURN OVER Page 5 of 8 COMP6231W1 Question 3. (a) Let A,B,C be propositional variables, and let KB be the following knowledge base: KB = {¬A! ¬B,¬(¬C ^B),¬A! C,¬B _ C}. For each of the following formulas, determine whether the formula is a semantic consequence of KB: (i) A _ ¬B (ii) C ! B (iii) (A ^B) ^ ¬C (iv) ¬¬C ! (¬(A! ¬B)! C) You must show your calculations and explain your answer. [Hint: use the definition of semantic consequence] [14 marks] (b) Let A,B,C be propositional variables, and let KB be the following knowledge base: KB = {A,¬A _B,A _ ¬B _ C,¬B _ C}. For each of the following formulas, determine whether the formula is a semantic consequence of KB, by applying the resolution algorithm: (i) C, (ii) ¬B. You must show your calculations and explain your answer. [11 marks] Copyright 2021 c University of Southampton Page 6 of 8 COMP6231W1 Question 4. (a) Clinical evaluation has shown that immunoglobin E (IgE) tests are both accurate and sensitive in the detection of dust allergy. The re- sults of the clinical evaluations show that the sensitivity of the test is 76.8%, i.e.: the probability that the result of an IgE test is positive given that an individual is allergic to dust is 76.8%. The specificity of the test was recorded at 99.68%, i.e.: the probability that the result of an IgE test is negative given that an individual is not allergic to dust is 99.68%. It is estimated that approximately 1.2% of the population is allergic to dust. Let - A = the IgE test is positive; - B = an individual is allergic to dust. Suppose that someone takes an IgE test and the result is negative. What is the probability that this individual is allergic to dust given that the IgE test is negative? Show your calculations and explain how you obtain the final result. [Note 1: Round the values to four decimal places, i.e.: 1.11116 is rounded to 1.1112, while 1.11113 is rounded to 1.1111.] [Note 2: Please note that the percentages in this question are made up and do not correspond to the real figures for dust allergy.] [14 marks] (b) Suppose that a computer monitor has a probability of malfunctioning of 0.2. A monitor image sometimes starts flickering and this is 10 times more likely to happen if the monitor is malfunctioning. In partic- ular, the probability that the monitor image is flickering given that the monitor is malfunctioning is 0.6, while it is 0.06 otherwise. Copyright 2021 c University of Southampton TURN OVER Page 7 of 8 COMP6231W1 This is represented in the Bayesian network below. Answer the following questions (you must show your calculations). (i) What is the probability P (f) that the image is flickering? (ii) What is the probability P (m|f) that the monitor is malfunctioning given that the image is flickering? (iii) What is the probability P (m|¬f) that the monitor is malfunction- ing given that the image is not flickering? (iv) What is the probability P (¬m,¬f) that the monitor is not mal- functioning and the image is not flickering? [11 marks] Copyright 2021 c University of Southampton END OF PAPER Page 8 of 8
欢迎咨询51作业君