CSE 3401
Old Title: Functional and Logic Programming
New Title: Introduction to Artificial Intelligence and Logic Programming
Fall 2012

Course Description

Artificial Intelligence (AI) deals with how to build intelligent systems. In this course, we examine fundamental concepts in AI: knowledge representation and reasoning, search, constraint satisfaction, reasoning under uncertainty, etc. The course also provides an introduction to logic programming and Prolog. Functional programming will only be discussed briefly.

What's New

• Nov 26: Assignment 4 is out; it due on Dec. 3 at 23:55.
• Nov 12: Assignment 3 is out; it due on Nov. 26 at noon - deadline extended!
• Nov 6: The deadline for assignment 2 has been extended again; it is now due on Nov 12 at noon.
• Oct 31: The office hours on Nov 1 and Nov 2 are cancelled. Send email to the instructor if you have questions.
• Oct 21: Assignment 2 is out; it due on Nov. 12 at noon -- deadline extended!
• Oct 2: The midterm test will be on Oct 25. It will cover all material seen from the beginning of the term until Oct 23 inclusive.
• Sept 28: The office hour on Sept 28 is cancelled.
• Sept 27: Assignment 1 is out; it due on Oct. 16 at the beginning of class.
• Sept 19: The office hours on Thursdays will be from 13:00 to 14:00 from now on.
• Classes start Sept. 6.

Instructor

Prof. Yves Lespérance
Office: LAS 3052A
Tel: 736-2100 ext. 70146
Email: lesperan "at" cse.yorku.ca

Lectures

Tuesday and Thursday from 14:30 to 16:00 in BC 215 (BC is Bethune College).

Instructor Office Hours

Tuesday from 17:00 to 18:00, Thursday from 13:00 to 14:00, and Friday from 14:00 to 15:00 in LAS 3052A.

Textbooks

Russell, S.J. and Norvig, P., Artificial Intelligence: A Modern Approach, 3rd edition Prentice Hall, 2010.
Authors' web site, Publisher's web site.

Clocksin, W.F. and Mellish, C.S., Programming in Prolog, (5th edition), Springer Verlag, New York, 2004.

The textbooks are required; they are available at the York University Bookstore.

Prerequisites

General prerequisites; MATH1090 3.0.

Evaluation

Assignements (4 @ 6% each)	24%
Midterm test	26%
Final exam	50%
Total	100%

Tentative Schedule

• Week 1 (Sept 6) Introduction & intelligent agents (R&N ch. 1 & 2).
• Week 2 (Sept 10) Logical representations, first-order logic syntax and semantics, use in knowledge representation. (R&N ch. 7 & 8).
• Week 3 (Sept 17) Basics of logic programming and Prolog, syntax, backchaining procedure, arithmetic, lists, I/O, recursive definitions, constraints solving, debugging. (C&M ch. 1, 2, 3.1-3.3, 5, and 8)
• Week 4 (Sept 24) Inference in first order logic, unification, resolution. (R&N ch. 9).
• Week 5 (Oct 1) Reasoning with Horn theories, SLDNF resolution, Prolog control flow, backtracking, closed world assumption, negation as failure. (R&N ch. 9 & C&M ch. 4 & 10)
• Week 6 (Oct 8) Prolog control flow, negation as failure, cut, 2nd order features, tail recursion. (C&M ch. 3, 4, 6, & 10)
• Week 7 (Oct 15) Prolog programming techniques, recursion, divide and conquer, text proessing. (C&M ch. 7 & 9)
• Week 8 (Oct 22)Uninformed search (R&N ch. 3, sec. 1 to 4). Midterm test on Oct 25.
• Week 9 (Oct 29) Uninformed search continued (R&N ch. 3, sec. 1 to 4).
• Week 10 (Nov 5) Informed search (R&N ch. 3, sec, 5 to 7).
• Week 11 (Nov 12) Game/Adversarial Search (R&N ch. 5).
• Week 12 (Nov 19) Constraint satisfaction and backtracking search (R&N ch. 6)
• Week 13 (Nov 26) Uncertain Reasoning (R&N ch. 13-14), Brief discussion of functional programming and Lisp.

Readings and Lecture Transparencies

• Week 1 (Sept 6) Introduction & intelligent agents
  Required Readings: Russell & Norvig Chapter 1 & 2.
  Lecture transparencies.
• Week 2 (Sept 10) Knowledge Representation & First-Order Logic
  Required Readings: Russell & Norvig Chapter 8 (Chapter 7 is optional).
  Lecture transparencies.
• Week 3 (Sept 17) Prolog Core Concepts and Notation
  Required Readings: Clocksin & Mellish Chapters 1, 2, 3.1 to 3.3, 5, and 8.
  Lecture transparencies, zebra.swipl zebra logic puzzle example code (the zebra.pl file has been renamed zebra.swipl so that our web server will let you download it).
• Week 4 (Sept 24) Inference in First-Order Logic
  Required Readings: Russell & Norvig Chapter 9.
  Lecture transparencies.
• Week 5 (Oct 1) Reasoning with Horn Theories and Procedural Control of Reasoning
  Required Readings: Russell & Norvig Chapter 9 and Clocksin & Mellish Chapter 4 & 10.
  Optional Readings: Brachman and Levesque, Knowledge Representation and Reasoning, Chapters 5 & 6.
  Lecture transparencies from Brachman and Levesque.
• Week 6 (Oct 8) Prolog control flow, negation as failure, cut, 2nd order features, tail recursion.
  Required Readings: Clocksin & Mellish Chapters 3, 4, 6, and 10.
  Lecture transparencies (updated!).
• Week 7 (Oct 15) Prolog programming techniques, recursion, divide and conquer, text proessing.
  Required Readings: Clocksin & Mellish Chapters 7 and 9.
  Lecture transparencies.
• Week 8 (Oct 23) Uninformed Search
  Required Readings: Russell & Norvig Chapter 3, Sec 1-4.
  Lecture transparencies.
• Week 9 (Oct 30) Uninformed Search
  Required Readings: Russell & Norvig Chapter 3, Sec 1-4.
  Lecture transparencies (updated)!
• Week 10 (Nov 5) Informed Search
  Required Readings: Russell & Norvig Chapter 3, Sec 5 & 6 and Chapter 4 Section 1.
  Lecture transparencies.
• Week 11 (Nov 12) Game Tree Search
  Required Readings: Russell & Norvig Chapter 5, Sec 1-3 and 7.
  Lecture transparencies.
• Week 12 (Nov 19) Constraint Satisfaction Problems and Backtracking Search
  Required Readings: Russell & Norvig Chapter 6.
  Lecture transparencies.
• Week 13 (Nov 26) Reasoning under Uncertainty
  Required Readings: Russell & Norvig Chapter 13 and Chapter 14 Sec. 1 and 2.
  Lecture transparencies from Brachman and Levesque.

Additional References

Other good AI textbooks:

Poole, D. and Mackworth, A. Artificial Intelligence, Foundations of Computational Agents, Cambridge University Press, 2010.

Poole, D., Mackworth, A., Goebel, R. Computational Intelligence, A Logical Approach,, Oxford University Press, New York, 1998.

Nilsson, N.J., Artificial Intelligence: A New Synthesis,, Morgan Kaufmann, San Francisco, 1998.

On knowledge representation:

Ronald J. Brachman and Hector J. Levesque, Knowledge Representation and Reasoning, Elsevier/Morgan Kaufmann 2004, ISBN 1-55860-932-6

Baral, C. Knowledge representation, reasoning, and declarative problem solving. Cambridge University Press, Cambridge/New York, 2003.

Genesereth, M.R. and Nilsson, N.J. Logical foundations of artificial intelligence. Morgan Kaufmann, Los Altos, CA, 1987.

On reasoning about action:

Reiter, R., Knowledge in Action: Logical Foundations for Specifying and Implementing Dynamical Systems, MIT Press, 2001. York Library eCopy, Book home page.

Running SWI-Prolog in the Prism Lab

• To run Prolog execute the command pl. To exit enter <CTRL>-D at the prompt.
• Documentation is available on the web.

Getting Prolog

• SWI-Prolog -- Windows, Linux, and Mac OS X versions of Prolog. Free software licensed under the Lesser GNU Public License. Look under downloads and IDE tools.

About Prolog

• A starting point is the Carnegie Mellon School of Computer Science Prolog repository.