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作业君