Computer Science 4500 --  Artificial Intelligence  

Test 1 -- Review

1. AI Concepts

definitions of AI: intelligent in human, humans better at, symbolic,
heuristic, pattern matching, learning, the Turing test
why it is hard to define; the two fallacies
areas: robotics, vision, human language, expert systems,
theorem proving, games, problem solving, machine learning

2. LISP

functional/applicative programming (versus procedural/imperative)
function evaluation (application), quote, math functions
atoms, lists, S-expressions; null list; car, cdr, cons, list;
predicates: Boolean values (t, nil), atom, null, equality
functions; defun, lambda, cond; recursion; symbols, setq;
special forms (cond, lambda); conditionals: cond, and, or
iteration: (recursion preferred), dolist, dotimes, do
applicative and mapping: apply, funcall, mapcar, maplist
I/O: read, read-line, print, princ, terpri
property lists & association lists; using Allegro Common LISP
writing simple and star recursive functions (numbers & lists)

3. Logic methods

propositions, connectives, laws, derivation rules
propositional vs. predicate calculus; predicates, functions,
quantifiers (universal, existential), variables
converting to clause form: implies, complement, variables,
quantifiers, existential (Skolem), drop prefix,
disjuncts, clauses, indep. variables
resolution: matching (unification) of clauses,
delete complementary terms and combine rest of 2 clauses
using resolution for proofs: original statements to clause form,
negate statement, clause form, add to list of clauses,
resolve; contradiction proves statement

4. State space search methods

state space, state variables, operators/move generators,
forward (data-driven) & backward (goal-driven),
trees and graphs, search space, search strategies
weak search methods: generate & test, depth/breadth first,
branching factors, combinatorial explosion
heuristic methods: h. goodness functions, f(s)=g(s)+h(s),
OR vs. AND/OR (decomposition); best vs. first solution,
hill climb, best-first (algorithm); admissibility,
monotonicity, informedness
zero-sum games, minimax move evaluation, alpha-beta pruning