prolog代写-ECEMBER 2020
时间：2021-08-07
UNIVERSITY OF BRISTOL
DECEMBER 2020
FACULTY OF ENGINEERING
Third Year Examination for the Degrees of
Bachelor of Science and Master of Engineering
COMS30013-SAMPLE
ARTIFICIAL INTELLIGENCE
This sample paper is not timed.
The real exam paper will be set for TWO HOURS.
Answer ALL questions in Part I
Each question in Part I is worth 1 mark.
Answer TWO of the three questions in Part II
Each question in Part II is worth 15 marks.
For each multiple-choice question in Part I, only one answer is considered
correct. If you think more than one answer is correct, choose the most correct
answer. There is no penalty (negative mark) for incorrect answers.
In Part I, questions that require you to fill in a blank part of a sentence, need
one or more words added to each blank to complete the sentence. The size of
the blank space is not related to the length of the answer.
This sample paper contains 15 questions in Part I. The real exam paper will
contain 30 questions in Part I, each worth 1 mark.
For Part II, indicate CLEARLY and UNAMBIGUOUSLY which part of which
question each of your answers relates to. Ensure your answers are presented
in the correct order with all of your work related to one answer in the same
place, and each answer clearly separated from the next by a line of dashes
(--------------------------------------------------------).
If you answer MORE than two questions from Part II, the two questions for
which you achieve the best marks will be used.
Calculators must have the Faculty of Engineering Seal of Approval.
Part I – Answer all 15 questions. Each question is worth 1 Mark.
1. Which one of the following is a well-formed Prolog term?
A. _r(_a)
B. R(a,B)
C. r_(a_)
D. R'
2. What is the standard logical interpretation of the Prolog operator ";"?
A. OR
B. XOR
C. IF
D. AND
3. Which one of the following is a unifier of the Prolog terms p(W,f(W,X)) and
p(Y,f(a,Z))?
A. { W/a }
B. { W/Y , Y/a }
C. { W/a, Y/a, X/V, Z/V }
D. { }
4. If (x,y) are the coordinates of an agent in a modified GridWorld where it can
move one square at a time up, down, left, right OR diagonally, which one of
the following is an admissible heuristic for the length of the shortest path back
to the origin (0,0)?
A. (x*x) + (y*y)
B. x+y
C. x*y
D. x
5. Which one of the following statements is FALSE?
A. A* will never return a worse solution than breadth-first search
B. breadth-first search will never visit more nodes than A*
C. breadth-first search will never return a worse solution than depth-first
search
D. depth-first search may visit fewer nodes than A*
6. Which of the following is NOT a real bio-inspired computing paradigm?
A. DNA computing
B. Swarm Intelligence
C. Genetic programming
D. Artificial Immune Systems
E. Trick question – they are all real
7. What is an “allele”?
A. A value taken by a gene
B. A loci
C. A chromosome
D. A genotype
8. Which of the following statements is least true? Hillclimbing methods are:
A. Effective for unimodal landscapes
B. Good at finding local optima
C. Efficient
D. Local search methods
9. The fitness score assigned to individual A in generation G of a GA's execution
is X before fitness sharing is applied but becomes Y afterwards. If Ycan we infer about A?
A. Other individuals in G are similar to A
B. A is suboptimal
C. Fitness sharing has reduced the fitness score of other individuals in G
D. A and C
E. A, B and C
10. Which CS pioneer worked on which area of biology:
A. Turing = Evolution; Babbage = Development; Von Neumann = Learning
B. Turing = Development; Babbage = Evolution; Von Neumann = Learning
C. Turing = Self-Reproduction; Babbage = Development; Von Neumann =
Evolution
D. Turing = Development; Babbage = Evolution, Von Neumann = Self-
Replication
E. Turing = Development; Babbage = Learning; Von Neumann = Self-
Reproduction
11. Proactive agents anticipate changes in the environment.
A. TRUE
B. FALSE
12. Consider a smart home as an agent. The smart home agent is programmed to
dim the lights in a room when a person in the room stops reading a book and
turns on the TV. The behaviour that the smart agent exhibits is an example of
a reactive behaviour.
A. TRUE
B. FALSE
13. In a norm lifecycle, which of these is a non-terminal state?
A. Violated
B. Satisfied
C. Expired
D. Conditional
14. Which of these statements about the environment and environmental
properties is false?
1) The environment in a chess game is deterministic
2) The environment in a chess game is accessible
3) For a card game in which each player draws one card in each round and the
player drawing the highest card is declared the winner of the round, the
environment is episodic
4) The environment through which a space probe travels is dynamic
A. 1
B. 2
C. 3
D. 4
E. None
15. The government’s Christmas guidance for university students includes the
following statement: “Universities should move learning online by 9
December so students can continue their education while also having the
option to return home to study from there.”
Provide a normative representation (norm type, subject, object, antecedent,
consequent) for the above-mentioned Christmas guidance statement.
A. Authorization(Government, University, CurrentDate > 9 Dec 2020,
Move-Learning-Online)
B. Commitment(University, Student, True, Move-Learning-Online)
C. Commitment(Student, University, CurrentDate > 9 Dec 2020,
Move-Learning-Online)
D. Commitment(University, Student, CurrentDate > 9 Dec 2020,
Move-Learning-Online)
END OF PART I
Part II – Answer TWO of the three questions. Each is worth 15 Marks.
II.1 Logic Programming
You are given the following Prolog program which concerns natural numbers
expressed in Peano notation - where successive integers are represented by the
terms 0, s(0), s(s(0)), s(s(s(0))), etc. The program contains one fact (stating
that zero is an even number), one rule (stating the double-successor of an even
number is also even) and one query (aiming to verify that one is not even):
even(0).
even(s(s(N))) :- even(N).
?- \+ even(s(0)).
Note that, when Prolog encounters a query while loading a program, it will
either proceed silently after finding the first successful answer, or it will issue
an error message if the query fails (in order to notify the user that the specified
goal/directive failed).
a) State whether the above query succeeds or fails.
[1 mark]
b) Rewrite the two clauses in the above program as a single equivalent rule.
[2 marks]
c) Give the standard translation of the rule you wrote down for part (b) above into First-
Order Logic (FOL) by simply replacing each Prolog operator by its closest classical
counterpart and quantifying over any variables.
NOTE: You should assume standard operator binding conventions (inserting
parentheses where necessary) and use the following ASCII symbols to represent the
quantifiers (A and E) and connectives (^, v, ?, <-, -> and <->).
[2 marks]
d) Consider the following definition of predicate odd/1 - which is intended to characterise
odd Peano numbers in the same way that even/1 characterises even Peano numbers.
odd(X) :- \+ even(X).
Draw SLD trees to explain the behaviour of this definition when it is called with ground
and variable arguments, respectively, and argue why this definition is not fit for
purpose.
NOTE: Assume the standard Prolog search strategy with the "cut-fail" definition of
negation and use the ascii notation illustrated below to write your tree (where a “?-”
precedes each goal, “+” is a choice point, “X” marks a subtree pruned by cut, “#” is a
failure branch, “:” is an infinite branch, “[]” is a success branch, and {..} represents any
computed answer):
?- goal.
|
?- resolvent.
|
+--------------------+----------X----------.
| | |
?- branch_1 ?- branch_2 ?- branch_n
| | |
... .!. ...
| | |
?- success ?- failure ?- infinite
| | :
[] # :
{..}
[8 marks]
e) Write down an alternative definition of odd/1 which is fit for purpose (and whose
argument can be treated as an input or an output).
[2 marks]
II.2 Genetic Algorithms
Gary is interested in evolving images using a genetic algorithm. Each image is a
50-by-50 grid of coloured pixels. Each genotype is a one-dimensional array of N
alleles that each explicitly specify one Red-Green-Blue colour component of
one pixel. The colour of one pixel is defined by three consecutive alleles on the
genotype, specifying the red, green, and blue components of the pixel's colour,
respectively. Each allele can take a floating point value in the legal range [0,1].
The first three alleles in the genotype define the colour of the top-left pixel, the
next three alleles define the colour of the pixel immediately to the right of this
first pixel. The final triple of alleles defines the colour of the bottom-right pixel
in the image.
a) If each allele can take one of 2^16 different values between 0 and 1, how
many different images does the search space contain?
[1 mark]
b) Gary implements mutation in the following way. Each allele in the genotype
of a new offspring image has independent probability m of being mutated.
When an allele is mutated, the parental value is perturbed by adding a value
drawn uniformly at random from the range [-0.1, +0.1]. If the new, perturbed
value is outside the legal range of [0,1] it is truncated to the nearest legal
value.
When Gary runs his genetic algorithm, he is interested to see that images with
bright bold colours tend to be evolved. Explain how his mutation operator may
be contributing to this result.
[4 marks]
c) Gary is thinking of implementing sexual recombination. He wants to combine
two high fitness parental images to create an offspring. He has considered one-
point crossover at a randomly selected position on the genotype, but he isn't
convinced that this will be a good choice. Define a simple crossover operator
that will take two parental genotypes and create a single offspring genotype.
The offspring genotype should comprise a rectangular section of one parent
replacing the equivalent part of the image provided by the second parent.
[4 marks]
d) Gary is a little disappointed with the results generated by his genetic
algorithm. The images in the population tend to be quite similar and it takes a
long time to discover interesting images. Gary has been told by Sue that his
"direct genotype-phenotype mapping might be too simplistic", but he has not
come across this idea before. Help Gary to understand the concept of a
genotype-phenotype mapping and explain how a less direct mapping could
allow evolution to generate more diverse images more quickly.
[6 marks]
II.3 Multi-Agent Systems
Consider a case in which two students (Grace and Judy) live together in a
rented house. They need to agree on which Internet service to sign up for from
their local cable company (Example Media Co.). Grace will sign the contract
with the cable company and pay for the service but she would like to also sign
a side contract with Judy in which Judy agrees to pay her share.
a) List and describe the social norms needed to characterize the interactions in
this setting. Use the commitment-based notation to define the identified
norms.
[6 marks]
b) Describe a scenario in which one of these norms is violated. State the relevant
event sequence using the notation from your answer to part (a) above. Who is
accountable for this norm violation?
[3 marks]
c) Grace and Judy graduate. Grace (who signed the contract with the cable
company) leaves the city. Judy finds a job in the same city and continues to
stay in the same rented house. Judy takes over the contract with Example
Media Co. from Grace. Olivia and Alice join Judy as her new house mates.
Olivia and Alice sign side contracts with Judy to pay their shares of the cost
for the Internet service.
Refine the initial normative specification and produce the new normative
specification for the new setting. You should describe the required
commitment changes and then use (some of) the ASSIGN, CANCEL,
CREATE, DECLARE, DELEGATE and RELEASE commitment operations
to define the required refinement process.
[6 marks]
