CSC 380/480 - Foundations of Artificial Intelligence - Winter 2007

Topics Covered in the Exam

• Intelligent Agents
  • PEAS description for agents
  • Architectural patterns for agent design (reflex agents, goal-based and utility agents, etc.)
  • Environments and their properties

• Problem Solving and Search
  • State-space representation and state-space graphs
  • Role of operators and goals (e.g., impact of operators on branching factor in the search space, etc.)
  • Problem types and their characteristics (single-state, multiple-state, contingency, etc.)
  • Search strategies (depth-first, breadth-first, iterative deepening, uniform cost)
  • Analysis of completeness, optimality, and space/time complexity for various search strategies

• Informed Search
  • Admissible heuristics and comparison of various heuristic functions
  • Hill-climbing search strategies
  • Greedy Best-first search
  • A* search

• Adverserial Search and Games
  • Heuristics in games
  • Minimax procedure
  • Alpha-Beta pruning
• Knowledge Representation and Logical Reasoning
  • Logical entailment and logical equivalence in Propositional Logic
  • Models and interpretations in Propositional Logic
  • Representation of problems in First-Order Predicate Calculus (e.g., translation from English)
  • Models and interpretations in FOPC, and the semantics of FOPC statements
  • Using the rules of inference in proofs (derivations) in Propositional Logic and FOPC
  • Conversion of First-Order logic formulas into CNF or clausal form (including "Skolemization")
  • Resolution rule of inference and refutation procedure
  • forward and Backward chaining and AND-OR proof trees
• Reasoning with Uncertainty
  • Probabilistic Reasoning
    • axioms of probability theory
    • join probability distributions and making inferences
    • Bayes’ Rule and its use in making probabilistic inferences
    • normalization and combining evidence (Bayesian updating)
    • notion of conditional independence
    • basic ideas of Bayesian networks, including making inferences given a BN
  • Decision Theoretic Agents
    • Action model for DT agents
    • Decision trees, including computation of state utilities
    • Principle of Maximum Expected Utility
  • Reasoning with certainty factors (MYCIN)

Text Material Related to the Final Exam
(Note: some of the topic and issues discussed in the class is not in the text book; your are responsible for both the text material as well as the the class material)

• Chapter 1 (Sections 1.1 and 1.3)
• Chapter 2 (all)
• Chapter 3 (all)
• Chapter 4 (Sections 4.1, 4.2, 4.3 - not local beam search and genetic algorithms)
• Chapter 6 (Sections 6.1-6.4)
• Chapter 7 (7.1-7.5)
• Chapter 8 (8.1-8.3)
• Chapter 9 (all - through "Example Proofs" subsection of 9.5)
• Chapter 13 (all)
• Chapter 14 (Section 14.1-14.2)