CP3210 Content and Exam Style Questions

History and Foundations

Content

Exam style questions

  1. What is Doug Lenat's CYC project attempting to achieve?
  2. Describe the Turing test for determining if an AI system has succeeded.
  3. Draw a labelled diagram showing the four components of an intelligent agent. Give examples of the activities that take place in each component.
  4. What facet of Philosophy suggests that the mind operates according to physical law? What implications does this have for AI?
  5. Name the three most important contributions to AI from Mathematics.
  6. Describe how the rapid improvements in computer hardware have advanced the capabilities of AI systems.
  7. What special feature of Chomsky's linguistic theory makes it important to AI?

Environments and Problems

Content

Exam style questions

  1. Explain what is meant by {accessibility,determinism,episodic,dynamic, continuity} for a problem environment. Give examples to illustrate your explanation.
  2. Explain what is meant by {decomposability,recoverability,predictability, solution quality} for a problem. Give examples to illustrate your explanation.
  3. Differentiate between a dynamic and a nondeterministic problem environment.
  4. Describe how the environment characteristics can affect the heuristic function used to guide state space search.
  5. Describe how the problem characteristics can affect the heuristic function used to guide state space search.

Propositional Logic

Content

Exam style questions

  1. Define the following terms used in classical logic:
    • Interpretation
    • Model
    • Satisfiable
    • Unsatisfiable
    • Logical consequence
  2. Explain what meant by an inference rule being:
    • Sound
    • Complete
    • Refutation complete
  3. Use a truth table to show that
           (q => p) | ~(q => (p | r))
    is a logical consequence of the set: 
         { p | q | r, 
       r => (p | q), 
       (q ^ r) => p, 
       ~p | q | r }
    .
  4. What are the two major limitaions of propositional logic?

1st Order Logic

Content

Exam style questions

  1. Describe the three components of a 1st order logic language.
  2. Describe the three components of an interpretation of a 1st order logic language. Give an example for the language: 
         V = { V : V starts with uppercase }
     F = { coke/0, pepsi/0, competitor/1 }
     P = { fizzy/1, sells_more/2 }
     

  3.  Given the 1st order logic language:
     
         V = { V : V starts with uppercase }
     F = { holden/0, ford/0, honda/0 main_competitor/1 }
     P = { fast/1, faster/2 }
     
    
     and the interpretation:
     
         D = { commodore, laser, prelude }
     F = { holden -> commodore,
           ford -> laser,
           honda -> prelude,
           main_competitor(commodore) -> prelude,
           main_competitor(laser) -> prelude,
           main_competitor(prelude) -> commodore }
     R = { fast(commodore) -> TRUE,
           fast(laser) -> FALSE,
           fast(prelude) -> TRUE,
           faster(commodore,commodore) -> FALSE,
           faster(commodore,laser) -> TRUE,
           faster(commodore,prelude) -> TRUE,
           faster(laser,commodore) -> FALSE,
           faster(laser,laser) -> FALSE,
           faster(laser,prelude) -> FALSE,
           faster(prelude,commodore) -> FALSE,
           faster(prelude,laser) -> TRUE,
           faster(prelude,prelude) -> FALSE }
     
    
     Show the steps of the interpretation of:
     
     
      
     
    •  faster(main_competitor(laser),commodore)
     
    •  fast(main_competitor(main_competitor(prelude))
     
    •  forall X ( faster(main_competitor(X),laser) & fast(X) )
     
    •  exists X ( fast(main_competitor(main_competitor(X))) |
                     forall Y ( faster(X,Y) ) )
     
    
         

  4.  Express the following scenario and conclusion in 1st order logic, in a 
     form ready to be converted to clause normal form.
     
    
     There are some students who fail. If a student fails, then either there 
     is a lecturer who has taught the student badly, the student is stupid. 
     No lecturer teaches any student badly. Therefore there is some student 
     who is stupid.
     
    

  5.  Explain why truth tables cannot be used to establish logical consequence 
     in 1st order logic.

  6.  Explain how "unsatisfiability" can be used to establish logical 
     consequence in classical logic.

Resolution

Content

Exam style questions

  1. Convert the following to CNF. Notation: & for AND, | for OR, ! for universal quantifier, ? for existential quantifier. 
             ? [Y] :
         ! [X] :
           ( element(X,Y)
         <=> element(X,X) )
      => ~ ( ! [X1] :
             ? [Y1] :
             ! [Z] :
               ( element(Z,Y1)
             <=> ~ element(Z,X1) ) )
  2. Explain, with examples, the difference between Horn and non-Horn clauses.
  3. Explain, with examples, what is meant by "Kowalski form" for clauses. Why is Kowalski form important?
  4. Use resolution to derive the empty clause from the set 
         { p(X,Y),
       ~p(f(X,Y),g(X,Y)),
       ~p(X,h(Y)) v p(X,Y),
       ~p(X,h(Y)) v ~p(X,X),
       ~p(X,Y) v p(X,X) v p(X,h(Y)) }
  5. Use linear-input resolution to derive the empty clause from the set 
         S = { ~r(Y) v ~p(Y),
           p(b),
           r(a),
           p(S) v ~p(b) v ~r(S),
           r(c) }

Prolog

Content

Exam style questions

  1. Write a Prolog program that counts the number of unique atoms in a list of atoms. The entry point to the program must be the clause unique/2. For example: 
         ?-unique([cat,hat,cat,rat,mat,cat,hat],N).
     yes
     N = 4
    You may assume that the member/2 predicate (that checks for list membership) already exists.
  2. Write a Prolog program that repeatedly reads data from the user (each input is . terminated), and stores each data item in the Prolog database, as the single argument of a fact. The predicate symbol of the facts is user_input. The input is terminated when the user enters the sentinal value exit. The entry point of the program must be the clause store_input/0. For example : 
         ?-store_input.
     Enter data : cat.
     Enter data : rat.
     Enter data : hat.
     Enter data : exit.
     
     yes
    would store the facts 
         user_input(cat).
     user_input(rat).
     user_input(hat).
    in the database.
  3. Explain what the =.. and functor/3 predicates do in Prolog. Give examples to illustrate your answer.

State Space Search and Production Systems

Content

Exam style questions

  1. What are the three components of the formal definition of a problem and its solution?
  2. What is the "state space" of a problem, and what are the two types of information stored in each state?
  3. Given certain achieved states in a state space, how can new states be reached?
  4. Describe how a problem can be solved using the state space search paradigm.
  5. In what two ways may one problem solution be considered better than another?
  6. Give two reasons why independent generation of states not suitable as a mechanism for reaching a goal state in a state space?
  7. Explain the fundamental and computational reasons why depth first search and breadth first search are not suitable as mechanisms for reaching a goal state in a state space?
  8. What are the three requirements of a state space for a control strategy to be able to intelligently guide search in the state space?
  9. What are the major factors that determine the direction of search in state space problem solving. Explain how these factors should be used to decide on the direction to use.
  10. Describe three common approaches for storing the dynamic information in states. Indicate the advantages and disadvantages of each.
  11. Expain the problems and advantages of bi-directional search.
  12. Describe three techniques for avoiding repeated states in state space search. Use examples to illustrate the differences between them. Mention the relative costs of using each.
  13. What are the components of a production system? Explain what each component does.
  14. Give the overall algorithm executed in a production system.

Search Control Strategies

Content

Exam style questions

  1. What are the four criteria for measuring the performance of a search control strategy? What fifth criteria is typically assumed for production systems?
  2. List the order in which the states are expanded in the following state space, using a WHATEVER search control strategy.
    PICTURE OF STATE SPACE
  3. Give the Time-Space-Optimality-Completness measures for the BFS, DFS, and Iterative deepening search strategies. Explain the features of these strategies that cause the differences in the measures.
  4. Explain how the A* strategy can be used to implement the Best first search, BFS, and Branch and bound strategies.
  5. Differentiate between:
    • informed and uninformed search
    • weak and strong methods
    • domain specific and non-domain specific heuristics
  6. Give the MiniMax algorithm for searching game trees.
  7. Fill in the internal node values in the following game tree, after traversal by the MiniMax algorithm: 
                                   _                           MAX
              /                |                \
             _                 _                 _         MIN
        /    |    \       /    |    \       /    |     \
       _     _     _     _     _     _     _     _      _  MAX
      /|\   /|\   /|\   /|\   /|\   /|\   /|\   /|\    /|\
     8 7 3 9 1 6 2 4 1 1 3 5 3 9 2 6 5 2 1 2 3 9 7 2 16 6 4
  8. Give the MiniMax algorithm with Alpha-Beta pruning, for searching game trees.
  9. Fill in the internal node values in the following game tree, after traversal by the MiniMax algorithm with Alpha-Beta pruning. Indicate which leave nodes would not require static evaluation. 
                                   _                           MAX
              /                |                \
             _                 _                 _         MIN
        /    |    \       /    |    \       /    |     \
       _     _     _     _     _     _     _     _      _  MAX
      /|\   /|\   /|\   /|\   /|\   /|\   /|\   /|\    /|\
     8 7 3 9 1 6 2 4 1 1 3 5 3 9 2 6 5 2 1 2 3 9 7 2 16 6 4

Knowledge Features

Content

Exam style questions

  1. Differentiate between the epistemic status and the assertional status of knowledge. Give examples to illustrate.
  2. The epistemic status of a statement describes our commitment to that statement. In this light differentiate between belief, hypothesis and knowledge.
  3. What are deductive, abuductive, and inductive reasoning?
  4. What is the "assertional status" of a statement? Give a simple example to illustrate three possible assertional statuses.
  5. Explain what is meant by each of the following, in terms of knowledge:
    • Incompleteness
    • Nonmonotonicity
    • Inconsistency
    • Inaccuracy
    • Uncertainty
    • Imprecision
  6. Explain what the "closed world assumption" is, and what feature of knowledge is the basis for its existence.
  7. Describe four approaches to assimilating inconsistent knowledge in a knowledge base.
  8. Differentiate between uncertainty and imprecision in a knowledge base. Give an example to illustrate.

Knowledge Representation

Content

Exam style questions

  1. Give a definition of "knowledge representation", based on appropriate definitions of "knowledge" and "representation".
  2. Explain what is meant by each of the following, in terms of knowledge representation:
    • Representational adequacy
    • Representational efficiency
    • Inferential adequacy
    • Inferential efficiency
    • Acquisitional efficiency
  3. Give a brief description of each of the five steps of engineering a knowledge base.
  4. What are the two properties that a general purpose ontology should have?
  5. In the context of a general purpose ontology, give examples to illustrate how each of the following can be represented:
    • Categories
    • Measures
    • Composite objects
    • Time, space, and change
    • Events and processes
    • Physical objects
    • Substances
    • Mental objects and beliefs
  6. Explain how semantic nets and frames can be viewed as different implementations of the same basic knowledge representation schema. Suggest types of knowledge for which each is more suitable.
  7. Give a frame/semantic net representation of the following:
    Billy is a mountain. Ethel is a tree. All mountains have trees growing on them. Billy has one tree growing on him. Ethel grows on Billy.
  8. Explain what the following are in terms of scripts:
    • Track
    • Props
    • Roles
    • Entry conditions
    • Scenes
    • Results
  9. Give a script suitable for the typical exam writing event.
  10. What is the main benefit of using a description logic, as opposed to classical 1st order logic? What two features of classical 1st order logic are omitted from description logic in order to obtain this benefit.

Uncertainty

Content

[RN95 pp.413-431]

Exam style questions

  1. What are three sources of uncertainty?
  2. Give the algorithm for search with uncertainty, based on expected utility.
  3. Explain the difference between prior probability and conditional probability. Give the formula for computing conditional probability from prior probabilities.
  4. Derive how P(p -> q) can be computed from P(p), P(q), and P(~p ^ q).
  5. Given that 80% of students who pass have studied, on average 60% of students pass, and the probability of a student studying is 0.5, what is the probability of passing given that you study?
  6. Explain (without necessarily doing the maths) how Bayesian updating can be used to combine evidence.
  7. Give an example to show how a belief network represents the joint probability distribution.
  8. Explain what each of the following kinds of probabilistic inference are:
    • Diagnostic
    • Causal
    • Intercausal
    • Mixed

Expert Systems

Content

Exam style questions

  1. Name the five basic components of an expert system.
  2. Explain what each of the following does in an expert system:
  3. What is the main practical difficulty with the application of expert systems, and what AI technique may help to overcome this?
  4. Describe how the devlopment of an expert system differs from the development of other forms of software.
  5. Give three examples of expert systems used in industry/commerce. Breifly describe what each is used for.

Neural Networks

Content

Exam style questions

  1. Describe the structure and operation of a processing element.
  2. Explain what is meant by a neural network being "fully feedforward connected".
  3. Explain the difference between supervised and unsupervised learning in a neural network.
  4. Describe the architecture of a Kohonen/counter propogation network. What (in general terms) are the tasks of each of the layers?
  5. Give details of how the output and hidden layers of a backpropogation network are trained. After sufficient training, what has a backpropogation network learned?

Natural Language Processing

Content

Exam style questions

  1. What are the levels of processing in NLP?
  2. What factors cause variations in phonemes? Give examples.
  3. What are the three major types of grammar?
  4. Define Chomsky languages types 0 to 3.
  5. Briefly explain how each of the following parsing techniques works:
    • Augmented transition networks
    • Chart parsers
    • DCGs
    Not covered in 1997.
  6. What is the task of semantic processing in NLP?
  7. In terms of discourse processing, give examples to illustrate the following:
    • Identical entities
    • Parts of entities
    • Entities in actions
    • Elements in sets
    • Names objects
    • Causal chains

References

[DM86] Delgrande J.P., Mylopolous J. (1986), Knowledge Representation : Features of Knowledge, in Bibel W., Jorrand Ph (Eds), Fundamentals of Artificial Intelligence : An Advanced Course, pp.3-36, Lecture Notes in Computer Science 232, Springer-Verlag.

[RN95] Russell S.J., Norvig P. (1995), Artificial Intelligence: a modern approach, Prentice-Hall.

[Ric83] Rich E. (1983), Artificial Intelligence, McGraw-Hill.

[Sut97] Sutcliffe G. (1997), CP3210 Logic & Prolog Lecture Notes, Dep't of Computer Science, James Cook University.