Study Guide for Cmput325 Final
N.b., his list is just meant to be SUGGESTIVE!
You should know about EVERYTHING covered, up to and
including the 7/Dec/04 lecture.
-
SECD Machines
-
Theoretical Foundations
-
Semantics: Interpretation, Entailment
-
Proof theory (Derivation Process)
- Model Elimination vs "Syntactic"
- (Sound) Inference Rules -- Modus Ponens, Resolution, etc
- Sound, Complete, Decidable
-
Resolution
-
Unification (MGU)
-
Conjunctive Normal Formula (CNF) form
-
Refutation Proof
-
Strategies (UnitPreference, Ordered, SetOfSupport, ...)
Prolog as TheoremProving
- Horn clauses
- Specific search strategy
Using Prolog
-
Be able to WRITE a RECURSIVE predicate
(set of predicates)
-
Be able to TRACE a RECURSIVE predicate
(set of predicates)
-
Be able to INTERPRET a (given) RECURSIVE
predicate (set of predicates)
MetaControl Issues
Constraint Satisfaction Programming (CSP)
- Foundations
- Framework: Variables, Domains, Constraints
- Examples
- Complexity
- Naive Generate-&-Test Implementation
- Improvements to Generate-&-Test
- Arc-consistency (k-consistency)
- Forward Checking
- Heuristics: Most-constrained variable, Most-constraining variable,
Least-constraining value
Be able to WRITE a CSP
Be able to TRACE a CSP
Be able to INTERPRET a a CSP
Probabilistic Reasoning
- Terms: Random Variable, Distribution, Event, Joint Prob. Dist.,
Conditional Probability (posterior)
- Bayes Rule
- Bayesian Networks: DAG + CPtable, Independence
+ Things included in Midterm StudyGuide
-
Lisp topics
-
Recursion, Variables (scoping), O( f(n) ), SideEffects
-
Lambda Calculus