CSci 4511 Spring 2019
Thursday May 9
120 minutes – Open book and not
人工智能代考 Can you construct a graph in which A* (with an admissible heuristics) will expand more nodes than uniform cost? if yes, show an example
1.15 points 人工智能代考
You are given the following English sentence: “Anyone who owns a pool owns a house” and these translations into predicate calculus:
(a) Is there a statement that represents well the English sentence? If yes, specify which one it is. If no, please write the correct logical sentence.
(b) For each of the logical sentences above write in English what the logical sentence is actually saying.
10 points Write the following sentences in predicate calculus using predicates such as Student(x), Building(x), Room(x), V isited(x, y) and convert them to CNF:
(a) Every student has been in at least one room of every building on campus.
(b) There is a student who has been in every room of at least one building on campus.
15 points Express each of the following statements in fifirst-order logic and convert to CNF, skolemizing as needed.
(a) All computer science majors own a Mac or a PC.
(b) Everyone who owns a Mac owns an IPOD. 人工智能代考
(c) All except one student in Stats 101 are Math majors.
(d) IPOD owners love music.
(e) John is a CS major who does not like music.
Prove by resolution with refutation that “John owns a PC”
15 points Prove by resolution with refutation that the following set of expressions in CNF is unsatisfifiable. Assume that upper case arguments are constant, lower case arguments are variable: 人工智能代考
(a) ¬Bar(x) ∨ ¬Zip(x)
(b) ¬Bar(w) ∨ ¬F oo(w, y) ∨ Bar(y)
(c) F oo(A, B)
(d) F oo(A, C)
(f) Zip(C) 人工智能代考
20 points You are given the following action schema to transfer object o from location x to location y:
Action (T ransfer(o, x, y),
Precond: At(Robot, x) ∧ At(o, x)
Effect: ¬At(Robot, x) ∧ ¬At(o, x) ∧ At(Robot, y) ∧ At(o, y)
(a) Create new action schemas by decomposing the action schema given into three schemas, one to grasp the object, one to move it to the destination, and one to drop it at the destination. 人工智能代考
(b) Describe in general how action schemas can be created by split ting existing schemas. Explain when this would be a good idea and when it would not.
25 points Answer these questions explaining your reasoning brieflfly but precisely. 人工智能代考
(a) Can you construct a graph in which A* (with an admissible heuristics) will expand more nodes than uniform cost? if yes, show an example, if not, explain why not.
(b) Does iterative deepening depth-fifirst search use less memory than breadth-fifirst search? Why (or why not)?
(c) How does the number of variables and the size of the domain af fect the complexity of solving a CSP problem using backtracking search?
(d) Explain why dropping negative effffects from every action schema results in a relaxed problem. 人工智能代考
Extra Credit 10 points
Suppose you decide to use simulated annealing but you do not want to reduce the initial temperature. How will the algorithm behave? Be precise.