CARDIFF UNIVERSITY EXAMINATION PAPER
Academic Year: Examination Period: Examination Paper Number: Examination Paper Title: Duration:
2019-2020
Autumn
CM3112
Artificial Intelligence 2 hours
Do not turn this page over until instructed to do so by the Senior Invigilator.
Structure of Examination Paper:
There are 6 pages.
There are 5 questions in total.
The maximum mark for the examination paper is 100 and the mark obtainable for a question or part of a question is shown in brackets alongside the question.
Students to be provided with:
The following items of stationery are to be provided: ONE answer book.
Instructions to Students:
Answer four questions.
The use of calculators is permitted in this examination.
Important note: if you answer more than the number of questions instructed, then answers will be marked in the order they appear only until the above instruction is met. Extra answers will be ignored. Clearly cancel any answers not intended for marking. Write clearly on the front of the answer book the numbers of the answers to be marked.
The use of translation dictionaries between English or Welsh and a foreign language bearing an appropriate departmental stamp is permitted in this examination.
1 PLEASE TURN OVER
CM3112
CM3112
Q1. Search
(a) Are the following statements true or false? Explain why. Please note that no
marks will be awarded without a suitable explanation. [9]
i. Multiple-path pruning is not useful if the search space is a tree.
ii. Cycle checking is not useful if the search space is a tree.
iii. Iterative deepening is guaranteed to need less memory than breadth-first search to find a solution.
(b) Prove the following property: if the state space is a tree and the heuristic evalua- tion function h is admissible, then A* is guaranteed to find the optimal solution.
[8]
(c) Consider the following state space, where A represents the initial state and I is the only goal state:
344
BEHI
1 A5C1F3G
21
D
Suppose furthermore that a heuristic h is given according to which: h(A) = 7, h(B) = 9, h(C) = 5, h(D) = 4, h(E) = 5, h(F) = 4, h(G) = 1, h(H) = 2, h(I) = 0.
i. Is the heuristic h admissible? Explain. [2]
ii. Is the heuristic h consistent? Explain. [2]
iii. Show step by step which nodes will be expanded and which nodes are in the frontier, when using greedy best-first search. [4]
52
2
Total: [25]
Q2. Minimax and planning
(a) i. Explain how the order in which moves are analysed can influence the effec-
tiveness of α-β pruning. [5] ii. Give an example of a method that can be used to optimise the order in which
moves are analysed. [3] (b) Consider the following game tree:
a
bcd efghij
CM3112
mnopqrstuv 3 2 12 6 5 1 9 10 15 4 1 2
i. Which move should the computer player choose? Briefly explain why. [3]
ii. Assuming that nodes are explored from left to right, which game states will
be pruned if α-β pruning is used? [4]
(c) In the context of STRIPS planning:
i. What is the advantage of searching partially-ordered plans instead of totally
kl
ordered plans?
ii. What is the purpose of causal links?
[5] [5]
3
Total: [25] PLEASE TURN OVER
CM3112
Q3. Propositional logic
(a) In the context of the propositional logic:
i. What does it mean for a formula α to entail a formula β? [4] ii. What is a clause? [4]
(b) Convert the following formula to conjunctive normal form: [9]
(a∧b∧¬c)∨¬(x∨¬y)
(c) Provide a truth table to answer the following questions. Clearly explain why your
answer follows from the given truth table.
• Istheformulaa∧b→¬a∨batautology? [4]
• Doesitholdthata→(b→a)|=a? [4]
4
Total: [25]
Q4. Bayesian networks
(a) Consider a Bayesian network with the following structure:
A BC D EF G
i. What is the Markov blanket of F ? [4] ii. Which random variables are conditionally independent from D given A? [4]
(b) Describe the algorithm for constructing the structure of a Bayesian network. [8] (c) Consider the following Bayesian network:
CM3112
P (A)
0.4
P(C)
0.2
AC
B
D
Use this Bayesian network to evaluate the following probabilities:
A
C
P(B|A,C)
T T F F
T F T F
0.1 0.6 0.9 0.3
B
P(D|B)
T F
0.5 0.4
i. P(a,¬b,¬c,d) ii. P(d|a,¬b,¬c)
[4] [5]
Total: [25] 5 PLEASE TURN OVER
CM3112
Q5. Fuzzy logic
(a) (b)
(c)
i. How is the direct product of a fuzzy set A and fuzzy relation R defined? [5] ii. How is the intersection of two fuzzy sets defined? [5]
For classical sets A and B, the Jaccard index is defined as follows: Jacc(A, B) = |A ∩ B|
|A∪B|
The Jaccard index thus models the degree of similarity between two sets, where Jacc(A, B) = 1 if and only if A = B. Suggest a way to generalise the Jaccard index to fuzzy sets, where you can assume that the universe is finite. [7]
Let us consider the following fuzzy sets: 1 if x = 0
0.7 if x = 1 0.3 ifx=2 0 if x = 3
0 0.3
0.7 1
ifx=0 ifx=1 ifx=2 ifx=3
ifx=0 ifx=1 ifx∈{2,3}
ifx=0 ifx=1 ifx∈{2,3}
Small(x) =
Low(x)=
Cheap(x)=
Large(x) =
1 ifx∈{0,1} 0
0.5 ifx=2 0 if x = 3
High(x)= 0.5 1
1 if x ∈ {0, 1}
0.3 ifx=2 Expensive(x)= 0.3
0
0 if x = 3 1 Consider the following rules about the price of televisions:
• If Size is Large and Quality is High then Price is Expensive • If Size is Small and Quality is Low then Price is Cheap
where we assume that size, quality and price are encoded on a scale from 0 to 3 stars. What can you derive about the price of a television whose size is 1 star and whose quality is 2 stars using the conjunctive model of approximate reasoning with the minimum t-norm? [8]
6X END OF EXAMINATION
Total: [25]