CS 381K: Midterm Study Guide

Exam Date: Monday, October 29, 2007, in class.

Reading: Russell & Norvig, Chapters 3-9.

Topics Covered in Class:

  1. State Space Search: definition of State Space; breadth-first, depth-first, bounded depth-first searches: algorithms, comparisons, advantages, disadvantages; iterative deepening; uniform-cost search; heuristic search: functions f, g, h and their meanings; A* algorithm; admissability of A*; IDA*; hill climbing; effect of having extra operators that are not needed for a given problem.
  2. Problem Reduction Search: definition; comparison to state space search; AND/OR graph; solution to an AND/OR graph; use of a model to find counter-examples; when to pick node most likely to succeed (fail).
  3. Descriptions of games with AND/OR graphs: game tree; reason for using an AND/OR graph; static evaluation function; depth bound; minimax position evaluation; be able to do a minimax evaluation of a given game tree. Alpha/beta search: algorithm, cutoffs, advantages, comparison to plain minimax search; be able to show alpha/beta search on a given game tree.
  4. Other search topics:Waltz filtering; constraint satisfaction; genetic algorithms; simulated annealing.
  5. GPS (General Problem Solver): how it works; differences; table of connections; means/ends analysis; problems with GPS.
  6. Heuristic Dendral: what it does; the state space; how is the state space reduced?
  7. Symbolic algebraic manipulation: examples, uses; canonical forms and reasons for using them; representation of formulas in Lisp.
  8. Propositional Logic: well-formed formulas (wffs); interpretations; truth/falsity under an interpretation; valid, invalid, consistent, inconsistent, satisfiable, unsatisfiable; decidability of propositional calculus; equivalence of formulas; normal forms; logical consequence; deduction theorem; backward chaining, forward chaining, resolution for propositional calculus.
  9. Predicate Calculus: Elements of a well formed formula (definitions); interpretation (definition); evaluation of a formula under an interpretation; decidability of predicate calculus; prenex normal form; Skolemization; clause form; Herbrand universe and Herbrand base; ground instance; Herbrand's Theorem (statement); substitution; applying a substitution to a formula; unification algorithm; resolution for predicate calculus; deduction tree; level-saturation (two-pointer) method; unit preference; set of support; linear resolution; natural deduction, forward chaining, backward chaining; use of predicate calculus for question answering; answer extraction; Horn clauses; use of predicate calculus for state-space problems: situation calculus, representation of operators; STRIPS: components of a STRIPS operator, how operators are chosen. Planning; plan monitoring. Truth maintenance system (TMS).

Vocabulary

A* algorithm add list admissible
algebraic simplification alpha/beta search AND node
AND/OR graph answer extraction answer literal
antecedent arc consistent assert
atom or atomic formula
average branching factor axiom backed-up value
backward chaining backward search beam search
best-first search bidirectional search blind search
Boolean satisfiability (SAT)
bound occurrence of variable bounded depth-first box
branching factor breadth-first canonical form
chronological backtracking clause closed list
closed world assumption (CWA) combinatoric explosion complete
conjunctive normal form (CNF) consequent consistent
constant constraint network constraint propagation
constraint satisfaction problem (CSP) credit assignment problem
decidable deduction deduction tree
delete list dependency-directed backtracking depth bound
depth-first diameter difference
effective branching factor entail evaluation function
expand a node extension false under an interpretation
first-order logic fluent forward chaining
forward search frame problem free occurrence of variable
function game tree genetic algorithm
goal state GPS ground instance
Herbrand base or atom set Herbrand universe heuristic function
heuristic search hierarchical planning hill climbing
Horn clause horizon effect IDA*
inconsistent instantiate intension
interpretation invalid iterative deepening
level-saturation method linear resolution literal
local maxima logical consequence means/ends analysis
minimax model model checking
modus ponens most general unifier (MGU) negation as failure
non-monotonic logic open list open world assumption
operator OR node parent clauses
pattern matching plan monitoring ply
precondition predicate predicate calculus
prefix premise prenex normal form
primitive subproblem problem reduction search propositional logic
quantifier representation hypothesis resolvent
retract rewrite rule satisfiable
set of support simulated annealing situation calculus
Skolem constant Skolem function Skolemization
sound splitting start state
state space state variable static evaluation function
steepest ascent STRIPS operator subproblem
substitution successor operator symbolic manipulation
table of connections tautology term
true under an interpretation truth maintenance system (TMS) truth table
Turing test two-pointer method unification algorithm
unifier uniform cost search unit clause
unit preference unsatisfiable valid
variable Waltz filtering well-formed formula (wff)