Search the whole station

# 人工智能代考 Artificial Intelligence代写 考试助攻 CS代写

329

## Artificial Intelligence: Sample Mid-Term Exam

### Problem 1

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 sub collection 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 sub collection 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 W has 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-fifirst 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 worth wile using iterative deepening for this problem rather than depth-first search? Explain your answer.

### Problem 2

Suppose that we want to solve EXACT SET COVER using hill climbing. Let us define a state to be any sub collection 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 3人工智能代考

Convert the following sentences to CNF:

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

B. ~[Q <=> R]

### Problem 4

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

1. ~P V Q V R.

2. Q V ~R V ~W.

3. P V Q V ~R

4. ~Q.

5. ~P V ~W

6. W V X

7. ~R V W V ~X.

### Problem 5人工智能代考

Let U be a domain of people and books. Let L a first-order language over U with the following symbols:

B(b,p) — book b is a biography of person p

G(p1,p2,b) — person p1 gave a copy of book b to person p2.

O(p,b) — person p owns a copy of book b.

W(p,b) — person p wrote book b.

F(p1,p2) — persons p1,p2 are friends.

A,P,S — Anne, Pamela, Sam

Express the following in L

1. Sam gave a copy of a book by Anne to Pamela.

2. If person p1 gave book b to person p2 then p2 owns a copy of b.

3. Sam owns a copy of every book that Anne has written.

4. The only books that Anne has written are biographies of friends of Anne’s.

### Problem 6人工智能代考

Consider the following situation. A patient arrives at a doctor’s office, complaining of symptoms. Given these symptoms, the probability is 3/4 that this is a benign situation that will go away in a week, and 1/4 that it is a serious condition that, left untreated, will not go away. There is a treatment for the condition that is always immediately effective. There is also a test for the condition, which is not all that good. It never gives false positives — that is, it never comes up positive if the patient does not have the condition — but the probability of a false negative if the patient does have the condition is 1/2.

The associated costs are:

• If the patient has to put up with the condition for a week, that has a cost, in terms of pain, of 100.
• The cost of the test is 100.
• The cost of the treatment is 400.

So the doctor has the following choices:

• He can do nothing. If the symptoms do not go away in a week, then the treatment has to be given.
• He can begin the treatment immediately without giving the test.
• He can give the test. If the test comes up positive, then he starts the treatment. If the test comes up negative, then he holds off giving the treatment and waits a week. If the symptoms have gone away, then nothing more has to be done. If the symptoms have not gone away, then the treatment has to be given.

Draw the decision tree. Label each out arc of a chance node with its probability, and every node of the tree with its utility. (Note: you may use a calculator for this purpose.)

The prev:

### Related recommendations

• #### 国际经济代考 经济学考试代考 考试助攻 经济考试代考

30

Midterm 国际经济代考 Problem 1 1.1 What is the opportunity cost of cloth in Foreign in terms of widgets? 1.2 Which of the following statements is true? Problem 1 1.1 What is...

View details
• #### 机器学习课业代做 CSE 158/258代写 cs代写 cs作业代写

255

CSE 158/258: Homework 3 机器学习课业代做 Instructions These homework exercises are intended to help you get started on potential solutions to Assignment 1. We’ll work directly with the Instr...

View details
• #### 信息系统代写 INFOSYS 110-1213代写 IT代写 cs代写

210

INFOSYS 110-1213 信息系统代写 Instructions: You must answer ALL parts of ALL questions in this exam, based on information given in the Exam Case. Type your answers into the Instructions: ...

View details
• #### 图像处理代写 image processing代写 python代写

374

image processing python Implementation (50 %) 图像处理代写 1 DoG (20 %) Use two Gaussian filters with suitable kernel sizes to to extract the license plate and remove most of the background ...

View details
1