人工智能期中代考 Artificial Intelligence代写

Artificial Intelligence: Mid-Term Exam

Problem 1 (15 points)

Consider the following simple PCFG (not in Chomsky normal form):

S -> NP VP [0.8]
S -> VP [0.2]
VP -> Verb [0.6]
VP -> Verb NP [0.4]
NP -> Noun [0.9]
NP -> Noun Noun [0.1]
Noun -> "fish" [1]
Verb -> "fish" [1]

Show three possible parse trees for the sentence “fish fish fish”, and mark each node with its probability.

You may write the probability as a product e.g. “0.2*0.3*0.4”; this is not an test on how well you can multiply. Hint: Think about this problem top-down; do not try to simulate the CYK parser, which works bottom-up, and requires Chomsky normal form.

Problem 2 (15 points) 人工智能期中代考

Consider the following sentence:

Sam got a sandwich at the deli and ate it for lunch.

A. Identify an instance of anaphoric ambiguity, of syntactic ambiguity, and of lexical ambiguity (one of each).

B. Explain how selectional restrictions can be used to exclude one wrong interpretation.

Problem 3 (20 points) 人工智能期中代考

The following problem is known as EXACT SET COVER: You are given a universal set U of elements and a collection W of subsets of U. The object is to find a subcollection Y of W such that every element of U is in exactly one set in Y.

For instance, suppose that U is the set {a,b,c,d,e,f,g,h,i} and that W is the following collection:

W1 = {a,d,f,h}
W2 = {b,e,g}
W3 = {e,g}
W4= {d,e,i}
W5 = {b,d,f,h}
W6 = {a,c,i}
W7 = {c,d,e}
W8 = {b,c,f}

Then one solution would be Y={W3,W5,W6}

The following state space can be used to solve EXACT SET COVER. 人工智能期中代考

A state is a subcollection S of W such that no element of U appears in more than one set in S. For example {W1,W2} is a state.

Let S be a state. The successors to S are formed as follows: Let X be the first element of U, alphabetically, that is not convered by any element of S, and let Wi be any set in W that contains X and does not overlap with S. Then adding Wi to S is a possible successor of S.

For instance, if S is the collection {W6}, then X is the element “b”. The successors to S are the collections {W6,W2}, and {W6,W5}. The collection {W6,W8} is not a successor to S — in fact, it is not a legitimate state at all — because both W6 and W8 contain the element “c”.

The start state is the empty collection.

A goal state is one that covers every element of U.

A. 人工智能期中代考

Show the part of the state space generated by a depth-first search for the above example.

B.

Suppose that in a particular problem, there are 100 elements in U; there are 50 sets in W; each set in Whas exactly 20 elements; and each element in U is covered by exactly 10 sets in W. Thus, a solution to the problem must consist of exactly 5 sets in W (100 elements total divided by 20 elements per set). What is the branching factor in the state space? What is the depth of the state space? Give an upper bound on the size of the state space.

C.

Would it be worthwhile using iterative deepening rather than depth-first search for the problem in B? Explain your answer.

D.

Suppose that in a particular problem, there are 100 elements in U; there are 50 sets in W; each set in W has between 10 and 20 elements; and each element in U is covered by between 5 and 10 sets in W. Thus, a solution to the problem contains somewhere between 5 (=100/20) and 10 (=100/10) sets in W. Might it be worthwile using iterative deepening for this problem rather than depth-first search? Explain your answer.

Problem 4 (10 points) 人工智能期中代考

Suppose that we want to solve EXACT SET COVER using hill climbing. Let us define a state to be any subcollection of W; for instance, in the above example {W3, W4, W7} would be one state. Propose a plausible neighbor relation on the state space and a plausible error function.

Problem 5 (10 points)

Show the result of carrying out alpha-beta pruning on the game tree shown below. What is the best move for MAX? What is the value of the game? (You may do this problem on the exam sheet; if so, please put your name on the exam sheet.)

Problem 6 (10 points)

Convert the following sentences to CNF:

A. ~ [P ^ (Q=>R)]

B. ~[Q <=> R]

Problem 7 (20 points) 人工智能期中代考

Trace the workings of the Davis-Putnam procedure on the set of clauses. When you reach a choice point, use the alphabetically first unbound atom and try TRUE before FALSE.

~P V Q V R.
Q V ~R V ~W.
P V Q V ~R
~Q.
~P V ~W
W V X
~R V W V ~X.

合作平台：essay代写论文代写写手招聘英国留学生代写