20 CS 724: Logic in Artificial Intelligence

Course Number	20 CS 724
Credit Hours	3 Graduate
Prerequisites	20CS633 20CS634 20CS621
Catalog Data	A survey of algorithms for logic inference. Logic inference is a particularly important NP-complete problem. It is often important in its own right (as in AI). Also, logic is based upon a natural (and ancient) mode of expression, and reducing other NP problems to prepositional logic is very often straightforward ?saving one the effort of writing tailored solvers for other NP problems. Prereq.: 20-CS-633, 634 and 15-CS-621.
Textbooks	Research papers.
References	None
Prerequisites by Topic	20-CS-633, 634, Artificial Intelligence I and II 15-CS 621, Mathematical Logic I Either 1 and 2 or Permission of the instructor
Goals	Students will be expected tp present papers and to write or modify programs.
Topics	Top-down resolution-based algorithms, such as in Prolog. (These are usually based on 3-valued logic.) Davis-Putnam-Loveland-Logeman type search algorithms. Lemmas and other speedups. Stochastic Local Search Algorithms. (These are fast but incomplete algorithms; they can fail to find inferences.) E.g., GSAT, WalkSAT, and tabu search methods.
Computer Usage	Students will be expected to write or modify programs.
Labs	None
Estimated ABET	Engineering Science: 3 credits or 100%
Prepared By	John Schlipf, Ph.D. on 2002/09/01