Candidate Number
THE UNIVERSITY OF SUSSEX
BSc FINAL YEAR EXAMINATION January 2019 (A1)
Knowledge and Reasoning Assessment Period: January 2019 (A1)
G6019
DO NOT TURN OVER UNTIL INSTRUCTED TO BY THE LEAD INVIGILATOR
Candidates should answer TWO questions out of THREE.
If all three questions are attempted only the first two answers will be marked.
The time allowed is TWO hours. Each question is worth 50 marks.
At the end of the examination the question paper and any answer books/answer sheets, used or unused, will be collected from you before you leave the examination room.
G6019 Knowledge and Reasoning
1. Bothinformedanduninformedsearchstrategiesarecommonlyusedinproblem- solving applications. However, they have distinct properties that determine when it may be advisable to prefer one over the other.
Consider the search problem below, where A is the initial state, and D is the goal state. The optimal path is that with the lowest accumulated path cost.
a) Uniform-Cost-Search (UCS) is an algorithm that uses the path cost to determine which nodes to explore in sequence.
i) Assuming a tree-search implementation, give the sequence of nodes in
which UCS is going to explore the tree.
ii) Did UCS find the optimal solution for this problem?
iii) Given positive path cost for any given search problem, is UCS
guaranteed to always find an optimal solution? Explain.
[18 marks]
b) Admissibility and consistency are properties of heuristics that allow the A* algorithm to be optimal.
i) Explain the difference between admissibility and consistency and
discuss in which context each is relevant for optimality.
ii) If we used a heuristic that estimates the cost from node A to node D as
h(A)=50, node B to node D as h(B)=40, and from node C to node D as
h(C)=10, would this heuristic be admissible for this problem?
iii) Change the values for h(B) and h(C) to any that would make the
heuristic consistent.
[18 marks]
c) Forthesearchproblemabove,howwouldyoudeviseaheuristicfor
i) Greedy Best-First Search
ii) A* search
that is guaranteed to miss the optimal path (i.e., always explore a more expensive route)? Explain your approach and state an evaluation function that would yield such behaviour.
[14 marks]
2
G6019 Knowledge and Reasoning
2. Semanticnetworksandsententiallogicscanbeusedtorepresentknowledge about concepts and their relationships.
a) Represent the following sentences in a semantic network (Draw a diagram):
Apes and monkeys are primates. All primates eat fruit. Chimpanzees are apes. Baboons are monkeys. Chimpanzees eat insects. Bananas are fruit.
Termites are insects.
[21 marks]
b) Answer the following questions about the statements above and explain briefly your reasoning:
i) Do baboons eat bananas?
ii) Do chimpanzees eat termites?
iii) Do baboons eat termites?
c) Formulatethefollowingsentencesinpredicatecalculus:
All big houses are expensive.
A house is prestigious only if it is big.
Any small apartment costs less than any big house. There is a house, which is bigger than any apartment. All apartments have at least one bathroom.
There is only one red house.
[6 marks]
[18 marks]
d) Would it be easier to represent the sentences in c) using propositional logic? Argue why or why not.
[5 marks]
/Turn over
3
G6019 Knowledge and Reasoning
3. Morethan60yearsago,AlanTuringproposedanexperimentthatcould determine, in his opinion, if a machine exhibited human-like intelligent behaviour. Since then, the issue of whether machine intelligence is possible has been widely debated.
a) If your task was to set up an experiment that resembles the Turing test, what would you have to do? Describe the setup and procedure in general
terms.
[15 marks]
b) In his Chinese Room Argument, John Searle proposes that computers are incapable of understanding anything they do because, in his opinion, their capabilities are limited to performing syntactic symbol-processing operations.
What is your opinion? Write a short essay of 3-4 pages length that starts with summarizing the Chinese Room thought experiment, and then presents a critical discussion of Searle’s motion. In this, you may want to include mention of existing opinions and thought experiments that you have come across in your previous study of the literature in this subject area. (Don’t worry if you do not remember the bibliographic details of those publications – stating these is not required for this task).
[35 marks] End of paper
4