Topics List for Qualifying Examination: Artificial Intelligence

You do not need to know more about the topics than can be obtained from the Davis book (used in CS 575 in Spring 92 and Spring 93), 475-level texts, and your course notes and extra readings in 475 and 575.

Basic Topics

• Use of Lisp or Prolog in AI programming.
• The general nature of production systems. The notion of rule instantiations, and methods for conflict resolution.
• Search algorithms: depth-first, breadth-first, best-first, hill-climbing, beam search, branch-and-bound, A*. The different ways heuristics can be involved.
• Constraint satisfaction.
• How to represent information in first-order predicate logic, semantic networks, and frame systems.
• Resolution theorem proving.

• Semantics of first-order predicate logic.
• Non-monotonic reasoning. :: Inheritance, defaults and exceptions in semantic networks. :: Truth Maintenance Systems: at least the basic form (after Doyle), but preferably also ATMSs and LTMSs [see Rich & Knight book]. :: Default Logic. :: Closed-world assumption, domain closure, unique-names assumption. :: Circumscription. :: Abduction.
• Analogy-based reasoning (incl. case-based reasoning).
• Representation of and reasoning about :: time, events, states :: mental states (beliefs, etc.)
• Natural language
• Expert systems

Any questions on the above topics in the examination will be based on

1. the material presented in CS 575 in those semesters in which the relevant candidates attended the course
2. relevant sections of 475-level AI texts such as: Winston; Rich & Knight; Luger & Stubblefield; ...