CIS 511, Spring 2009

Brief description:

The course provides an introduction to the theory of computation. The treatment is mathematical, but the point of view is that of Computer Science. Roughly speaking, the theory of computation consists of three overlapping subareas: (1) formal languages and automata; (2) Models of computation, computability, and basics of recursive function theory; (3) complexity theory.

The course will focus mostly on (1) and (2), but will also cover some of (3): the classes P and NP, and NP-complete problems. Applications of (1) to programming (and natural) language specification and parsing (top-down and bottom-up parsing) will be mentioned, whenever appropriate.

Students are expected to have some undergraduate knowledge of the theory of computation. Some material assumed to be known will either not be covered in class or reviewed quickly. This material is marked with a (-). Materiall not required for the WPE is marked with a (*).


Topics will include: ((*) means: if time permits)

PART 1: Languages and Automata

PART II: Models of Computation and Basics of Recursive Function Theory

PART III: Computational Complexity

Back to Gallier Homepage

published by:

Jean Gallier