CS 457/490 EXAM Number 1

15 October 1997

Name___________________________

No books or notes. The points for each question and percent of total credit follows the question number. Good luck.

1. (12) Consider the following story:

Fred is a Collie and Sam is Fred's master. Today is Saturday, and when it is warm, Sam always goes to the park. On the other hand, if it is not warm Sam goes to the Museum. It is cold on this Saturday. All good dogs that have a master will be with their master. Cocker Spaniels or Collies that are trained are good dogs. Fred is trained. Where is Fred??

a) Translate the story into predicate calculus expressions.

b) Solve the problem with goal driven reasoning

c) Show the solution process with either the iterations of a production system or the and/or graph search indicating the unification substitutions and exactly where each one is made.

Name_________________________

3. (8) Give four reasons why the production is an important architecture for AI problem solving.

Name_____________________

4. (6)

Given a set, S, of Predicate Calculus expressions,

a) define what we mean by "an interpretation of S."

b) define "a sound inferencing scheme."

c) define a "complete inference strategy.".

5. (9) Define:

a) An A* algorithm.

b) A "monotonic heuristic."

c) A "more informed" heuristic

Name_____________________

6. (6) What is "beam search," why is it important and what is a potential danger?

7. (5) What is the most general unifier and how is it important in problem solving?

8. (4) Trace, by generating the search tree, the unification algorithm of Chapter 2 on the two following expressions. Show all substitutions if the algorithm succeeds, otherwise show exactly where it fails.

p(X, george, X) and p(fred, Y, george)

Name_____________________

9. (6) Perform an alpha-beta prune of the following tree. Show the direction you are taking, the alpha and beta values at each appropriate place, and exactly where all pruning takes place. Circle the nodes that are NOT evaluated. You are playing the top node and want to win. Heuristic values are printed at the leaf nodes.

6 2 8 5 2 3 0 -2 6 2 5 8 6 7

10. (5) What is a "blackboard" and how might it be used.

11. (8) What is, in predicate calculus problem solving,

a) the "closed world assumption?"

b) "negation as failure?"

Name_____________________

12. (8) Explain how explanations are generated for rule-based expert systems:

a) In data-driven reasoning:

b) Goal-driven reasoning:

13.(8) List four things that show the difference between rule based reasoning and model based reasoning.

14. (5) What is the "indexing problem" in a case based reasoner. How might it be addressed?

15. (5) Explain what the exploratory development cycle and quick prototyping are and why these methodologies are important in AI problem solving.

Take home question: Assignment 2. You may use books or notes. Turn in before class next Monday.

Consider the sliding-tile puzzle pictured below. The start position has 3 black tiles at the left, a blank space in the middle, and three white tiles on the right. There are three legal moves: 1) move into an adjacent empty location, 2) jump exactly one tile and land in the empty location, and 3) jump two tiles and land in the empty location.

The cost of a jump move is the number of tiles jumped over. The goal is to move all the white tiles to the left of all the black tiles (the final location of the blank is not important).

B B B W W W

Create two heuristics for this game. Show whether or not each is admissible, monotonic, and whether or not one is more informed than the other.

17 December 1997 CS 457 Name _____________

Exam on final third of semester. No books or notes. Points (of 100) after each question number.

I do NOT want my semester grade posted, by SSN, on the professor's door

Signed _________________

1. (14) Use the back of this page, if necessary.

Consider the following story:

All people that are not poor and are smart are happy. Those people that read are smart. John is wealthy. Helen

can read and is wealthy. Happy people have exciting lives. Wealthy people are not poor. Find someone with an

exciting life.

a) Translate the story into predicate calculus expressions.

b) Translate the clauses into disjunctive normal form.

c) Show the resolution refutation solution process with an appropriate proof tree.

d) Use your example to demonstrate the answer extraction

process for resolution refutations.

2. (9)

a) Why are search strategies important in theorem proving?

b) Describe two strategies for use in a resolution refutation system and describe the advantages/disadvantages of each.

3. (6)

What is the role of data types in CommonLisp and PROLOG? How can the program designer address this issue, say if it was desired to have strong type constraints in a PROLOG database?

17 December 1997 CS 457 Name _____________

4. (5)

What did Herb Simon mean in his Turing award lecture when he described computer science as empirical enquiry?

5. (4 )

In what sense is the PROLOG interpreter a theorem prover?

6. (6)

Describe conceptual dependencies.

Who first proposed this representational scheme and for what reason?

Describe two possible problem solving applications that might use this representation.

17 December 1997 CS 457 Name _____________

7. (12)

a. (4) Give three of the reasons why the MYCIN researchers created the Stanford Certainty factor algebra.

b. (8) Given the following rules in a "back-chaining" expert system application:

A ^ not(B) --> C (.8)

C v D --> E (.9)

F --> A (.7)

G --> D (.8)

The system can conclude the following facts (with their corresponding confidences):

F(.9)

B(-.6)

G(.8).

Use the Stanford certainty Factor algebra to conclude E and its confidence. Show your work.

8. (9)

What is non-monotonic reasoning?

Why is it an important aspect of intelligent reasoning?

How might it be built into a computational system?

9. (3)

What is the problem of overlearning? Give an example.

17 December 1997 CS 457 Name _____________

10. (6)

What is the role of inductive bias in learning? What can be done about it?

11. (6)

a) What is a metainterpreter?

b) Why is this problem solving tool important?

c) Why are some languages better for designing metainterpreters than others?

12. (8)

What is abductive inference? Describe briefly three computational models for abduction.

Abduction is...

1.

2.

3.

13. (9)

What is a frame system. Who proposed this approach to representation? Give an example of a frame.

14. (3)

How do you see as the future of AI in computer science? Justify your answer.