xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

数学代写-CM3112

时间：2021-01-21

CM3112

CARDIFF UNIVERSITY

EXAMINATION PAPER

Academic Year: 2015-2016

Examination Period: Autumn

Examination Paper Number: CM3112

Examination Paper Title: Artificial Intelligence

Duration: 2 hours

Do not turn this page over until instructed to do so by the Senior Invigilator.

Structure of Examination Paper:

There are 8 pages.

There are 5 questions in total.

The following appendices are attached to this examination paper: Formula sheet

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

Q1. Search

(a) Explain how the minimax algorithm can be extended to deal with chance ele-

ments (e.g. in games such as backgammon). [6]

(b) i. When do we say that a heuristic function is admissible? [2]

ii. When do we say that a heuristic function is consistent? [2]

iii. Consider a pathfinding problem with the following state space:

where a is the initial state, f is the only goal state, and the edges are labelled

with the costs of the corresponding actions. Give an example of a heuristic

function which is admissible but not consistent. Explain why the function is

not consistent. [6]

(c) Consider the following implementation of breadth-first search with multiple-path

pruning:

i. How would you modify this code to obtain an implementation of depth-first

search? [3]

ii. Suggest two ways in which the implementation of multiple-path pruning can

be improved. [6]

Total: [25]

2

CM3112

Q2. Propositional logic

(a) i. What is the definition of a possible world? [3]

ii. What is the definition of a tautology? [3]

iii. Explain why a SAT solver can be used to check whether α |= β holds for

formulas α and β. [3]

(b) Which of the following formulas are entailed by a ∨ b [6]

i. a

ii. a ∨ b ∨ c

iii. c→ a ∨ b

iv. c ∨ ¬c

v. a ∨ (b→ (c ∧ a))

vi. ¬a→ ((c ∨ ¬e) ∧ (¬a ∨ d ∨ e)→ b)

(c) Prove the following entailment relation using the properties of propositional logic

that have been provided in the appendix: [10]

e ∨ f → (a→ b) ∧ (b→ c ∨ d) |= e ∧ a→ c ∨ d

Total: [25]

3 PLEASE TURN OVER

CM3112

Q3. Planning

(a) i. When is it useful to search for partially ordered plans instead of totally or-

dered plans? [4]

ii. What is the advantage of searching partially-ordered plans instead of totally

ordered plans? [3]

(b) Explain how causal links and ordering constraints are used when searching for

partially ordered plans. [6]

(c) Formalise the 8-puzzle as a STRIPS planning problem. Provide a full specifi-

cation of all actions, as well as the initial and final states which are illustrated

below: [12]

Recall that the 8-puzzle is a puzzle in which numbered tiles on a 3× 3 grid need

to be rearranged such that the numbers appear in increasing order (as in the figure

on the right). To this end, the player can slide one of the tiles which is adjacent

(horizontally or vertically) to the empty grid cell onto that empty grid cell. For

example, in the figure on the left, the player can slide the 5-tile to the right, the

6-tile to the left, the 2-tile down or the 3-tile up.

Hint: arithmetic operations are not supported in STRIPS, so you cannot use

expressions such as row + 1. Instead you could assign labels to the rows

and columns (e.g. a, b, c, d, e, f ) and explicitly encode in the initial state which

rows/columns are adjacent to each other.

Total: [25]

4

CM3112

Q4. Bayesian networks

(a) i. What does it mean for random variables to be conditionally independent?

[5]

ii. What assumptions about conditional independence are encoded by the struc-

ture of a Bayesian network? [5]

(b) Give an example of a Bayesian network with random variables A,B,C,D,E

such that the Markov blanket of A is given by {B,C}, the Markov blanket of C

is given by {A,B,D,E} and the Markov blanket of E is given by {B,C,D}.

You only need to provide the network structure, not the conditional probability

tables. [6]

(c) Calculate the value of P (a,¬c|b) for P the probability measure defined by the

following Bayesian network: [9]

Total: [25]

5 PLEASE TURN OVER

CM3112

Q5. Fuzzy logic

(a) i. What is the definition of a t-conorm? [5]

ii. What is the definition of the residual implicator induced by a continuous

t-norm T ? [5]

(b) Let the fuzzy set A and the fuzzy relation R be defined as follows:

A = {a/0.7, b/0.3, c/0.8}

R = {(a, x)/0.9, (a, y)/0.5, (b, x)/0.7, (b, y)/1, (c, x)/0.8, (c, y)/0.6}

Evaluate the direct product of A and R w.r.t. the Łukasiewicz t-norm TW (see

appendix for the definition). [8]

(c) Let A be a set in the universe X and let R be a relation from X to X . The lower

approximation of A w.r.t. R is defined as follows:

A↓R = {x | for every y in X it holds that if (x, y) ∈ R then y ∈ A}

Suggest a way to define the lower approximation of a fuzzy set A w.r.t. a fuzzy

relation R which generalises the above definition. [7]

Total: [25]

6

CM3112

Appendix I: Formula sheet

Propositional logic

Law of De Morgan ¬(a ∨ b) ≡ ¬a ∧ ¬b

¬(a ∧ b) ≡ ¬a ∨ ¬b

Distributivity a ∧ (b ∨ c) ≡ (a ∧ b) ∨ (a ∧ c)

a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)

Implication law a→ b ≡ ¬a ∨ b

Double negation ¬¬a ≡ a

Absorption a ∧ (a ∨ b) ≡ a

a ∨ (a ∧ b) ≡ a

Excluded middle a ∨ ¬a ≡ true

Contradiction a ∧ ¬a ≡ false

Symmetry a ∨ b ≡ b ∨ a

a ∧ b ≡ b ∧ a

Contraposition a→ b ≡ ¬b→ ¬a

Idempotency a ∨ a ≡ a

a ∧ a ≡ a

Truth constants a ∨ true ≡ true

a ∨ false ≡ a

a ∧ true ≡ a

a ∧ false ≡ false

¬false ≡ true

Equivalence if α ≡ β then α |= β

Deduction theorem α |= β iff true |= α→ β

Weakening a ∧ b |= a

a |= a ∨ b

a→ c |= a ∧ b→ c

a ∨ b→ c |= a→ c

a→ b |= a→ b ∨ c

a→ b ∧ c |= a→ b

Resolution (a ∨ b) ∧ (¬a ∨ c) |= b ∨ c

7 PLEASE TURN OVER

CM3112

Fuzzy logic

Popular choices for t-norms and t-conorms are:

t–norm t–conorm

TM(a, b) = min(a, b) SM(a, b) = max(a, b)

TP (a, b) = ab SP (a, b) = a+ b− ab

TW (a, b) = max(0, a+ b− 1) SW (a, b) = min(1, a+ b)

The corresponding S-implicators and residual implicators are given by:

S–implicator Residual implicator

ISM (a, b) = max(1− a, b) ITM (a, b) =

{

1 if a ≤ b

b otherwise

ISP (a, b) = 1− a+ ab ITP (a, b) =

{

1 if a ≤ b

b

a

otherwise

ISW (a, b) = min(1, 1− a+ b) ITW (a, b) = min(1, 1− a+ b)

Some properties of a continuous t-norm T and its corresponding residual implicator IT are:

IT (1, a) = a

a ≤ b⇔ IT (a, b) = 1

T (IT (a, b), c) ≤ IT (a, T (b, c))

IT (T (a, b), c) = IT (a, IT (b, c))

IT (a, IT (b, c)) = IT (b, IT (a, c))

T (IT (a, b), IT (b, c)) ≤ IT (a, c)

T (IT (a, b), IT (c, d)) ≤ IT (T (a, c), T (b, d))

T (a, IT (b, c)) ≤ IT (IT (a, b), c)

T (a, IT (a, b)) = min(a, b)

8X END OF EXAMINATION

CARDIFF UNIVERSITY

EXAMINATION PAPER

Academic Year: 2015-2016

Examination Period: Autumn

Examination Paper Number: CM3112

Examination Paper Title: Artificial Intelligence

Duration: 2 hours

Do not turn this page over until instructed to do so by the Senior Invigilator.

Structure of Examination Paper:

There are 8 pages.

There are 5 questions in total.

The following appendices are attached to this examination paper: Formula sheet

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

Q1. Search

(a) Explain how the minimax algorithm can be extended to deal with chance ele-

ments (e.g. in games such as backgammon). [6]

(b) i. When do we say that a heuristic function is admissible? [2]

ii. When do we say that a heuristic function is consistent? [2]

iii. Consider a pathfinding problem with the following state space:

where a is the initial state, f is the only goal state, and the edges are labelled

with the costs of the corresponding actions. Give an example of a heuristic

function which is admissible but not consistent. Explain why the function is

not consistent. [6]

(c) Consider the following implementation of breadth-first search with multiple-path

pruning:

i. How would you modify this code to obtain an implementation of depth-first

search? [3]

ii. Suggest two ways in which the implementation of multiple-path pruning can

be improved. [6]

Total: [25]

2

CM3112

Q2. Propositional logic

(a) i. What is the definition of a possible world? [3]

ii. What is the definition of a tautology? [3]

iii. Explain why a SAT solver can be used to check whether α |= β holds for

formulas α and β. [3]

(b) Which of the following formulas are entailed by a ∨ b [6]

i. a

ii. a ∨ b ∨ c

iii. c→ a ∨ b

iv. c ∨ ¬c

v. a ∨ (b→ (c ∧ a))

vi. ¬a→ ((c ∨ ¬e) ∧ (¬a ∨ d ∨ e)→ b)

(c) Prove the following entailment relation using the properties of propositional logic

that have been provided in the appendix: [10]

e ∨ f → (a→ b) ∧ (b→ c ∨ d) |= e ∧ a→ c ∨ d

Total: [25]

3 PLEASE TURN OVER

CM3112

Q3. Planning

(a) i. When is it useful to search for partially ordered plans instead of totally or-

dered plans? [4]

ii. What is the advantage of searching partially-ordered plans instead of totally

ordered plans? [3]

(b) Explain how causal links and ordering constraints are used when searching for

partially ordered plans. [6]

(c) Formalise the 8-puzzle as a STRIPS planning problem. Provide a full specifi-

cation of all actions, as well as the initial and final states which are illustrated

below: [12]

Recall that the 8-puzzle is a puzzle in which numbered tiles on a 3× 3 grid need

to be rearranged such that the numbers appear in increasing order (as in the figure

on the right). To this end, the player can slide one of the tiles which is adjacent

(horizontally or vertically) to the empty grid cell onto that empty grid cell. For

example, in the figure on the left, the player can slide the 5-tile to the right, the

6-tile to the left, the 2-tile down or the 3-tile up.

Hint: arithmetic operations are not supported in STRIPS, so you cannot use

expressions such as row + 1. Instead you could assign labels to the rows

and columns (e.g. a, b, c, d, e, f ) and explicitly encode in the initial state which

rows/columns are adjacent to each other.

Total: [25]

4

CM3112

Q4. Bayesian networks

(a) i. What does it mean for random variables to be conditionally independent?

[5]

ii. What assumptions about conditional independence are encoded by the struc-

ture of a Bayesian network? [5]

(b) Give an example of a Bayesian network with random variables A,B,C,D,E

such that the Markov blanket of A is given by {B,C}, the Markov blanket of C

is given by {A,B,D,E} and the Markov blanket of E is given by {B,C,D}.

You only need to provide the network structure, not the conditional probability

tables. [6]

(c) Calculate the value of P (a,¬c|b) for P the probability measure defined by the

following Bayesian network: [9]

Total: [25]

5 PLEASE TURN OVER

CM3112

Q5. Fuzzy logic

(a) i. What is the definition of a t-conorm? [5]

ii. What is the definition of the residual implicator induced by a continuous

t-norm T ? [5]

(b) Let the fuzzy set A and the fuzzy relation R be defined as follows:

A = {a/0.7, b/0.3, c/0.8}

R = {(a, x)/0.9, (a, y)/0.5, (b, x)/0.7, (b, y)/1, (c, x)/0.8, (c, y)/0.6}

Evaluate the direct product of A and R w.r.t. the Łukasiewicz t-norm TW (see

appendix for the definition). [8]

(c) Let A be a set in the universe X and let R be a relation from X to X . The lower

approximation of A w.r.t. R is defined as follows:

A↓R = {x | for every y in X it holds that if (x, y) ∈ R then y ∈ A}

Suggest a way to define the lower approximation of a fuzzy set A w.r.t. a fuzzy

relation R which generalises the above definition. [7]

Total: [25]

6

CM3112

Appendix I: Formula sheet

Propositional logic

Law of De Morgan ¬(a ∨ b) ≡ ¬a ∧ ¬b

¬(a ∧ b) ≡ ¬a ∨ ¬b

Distributivity a ∧ (b ∨ c) ≡ (a ∧ b) ∨ (a ∧ c)

a ∨ (b ∧ c) ≡ (a ∨ b) ∧ (a ∨ c)

Implication law a→ b ≡ ¬a ∨ b

Double negation ¬¬a ≡ a

Absorption a ∧ (a ∨ b) ≡ a

a ∨ (a ∧ b) ≡ a

Excluded middle a ∨ ¬a ≡ true

Contradiction a ∧ ¬a ≡ false

Symmetry a ∨ b ≡ b ∨ a

a ∧ b ≡ b ∧ a

Contraposition a→ b ≡ ¬b→ ¬a

Idempotency a ∨ a ≡ a

a ∧ a ≡ a

Truth constants a ∨ true ≡ true

a ∨ false ≡ a

a ∧ true ≡ a

a ∧ false ≡ false

¬false ≡ true

Equivalence if α ≡ β then α |= β

Deduction theorem α |= β iff true |= α→ β

Weakening a ∧ b |= a

a |= a ∨ b

a→ c |= a ∧ b→ c

a ∨ b→ c |= a→ c

a→ b |= a→ b ∨ c

a→ b ∧ c |= a→ b

Resolution (a ∨ b) ∧ (¬a ∨ c) |= b ∨ c

7 PLEASE TURN OVER

CM3112

Fuzzy logic

Popular choices for t-norms and t-conorms are:

t–norm t–conorm

TM(a, b) = min(a, b) SM(a, b) = max(a, b)

TP (a, b) = ab SP (a, b) = a+ b− ab

TW (a, b) = max(0, a+ b− 1) SW (a, b) = min(1, a+ b)

The corresponding S-implicators and residual implicators are given by:

S–implicator Residual implicator

ISM (a, b) = max(1− a, b) ITM (a, b) =

{

1 if a ≤ b

b otherwise

ISP (a, b) = 1− a+ ab ITP (a, b) =

{

1 if a ≤ b

b

a

otherwise

ISW (a, b) = min(1, 1− a+ b) ITW (a, b) = min(1, 1− a+ b)

Some properties of a continuous t-norm T and its corresponding residual implicator IT are:

IT (1, a) = a

a ≤ b⇔ IT (a, b) = 1

T (IT (a, b), c) ≤ IT (a, T (b, c))

IT (T (a, b), c) = IT (a, IT (b, c))

IT (a, IT (b, c)) = IT (b, IT (a, c))

T (IT (a, b), IT (b, c)) ≤ IT (a, c)

T (IT (a, b), IT (c, d)) ≤ IT (T (a, c), T (b, d))

T (a, IT (b, c)) ≤ IT (IT (a, b), c)

T (a, IT (a, b)) = min(a, b)

8X END OF EXAMINATION