CS353: Elements of the Theory of Computation
Spring 1999
Overview
The mathematical theory of computing is important
not only because of its intrinsic interest but
because of its key role underlying many significant applications.
Indeed, to thoroughly understand the practice of computing
one needs a good understanding of the associated theory.
This course will focus on the following topics:
- Computability - what problems are solvable by algorithms
and which are not? Universal models of computation;
decidable and undecidable problems; halting problem;
problem transformations to establish undecidability.
- Complexity - what problems can be solved by efficient algorithms
and which cannot? NP-completeness; propositional satisfiability,
hamilton path, and other NP-complete problems; other complexity classes;
intractable problems.
- Logics of Programs - how can we ensure that computer programs
behave correctly? Temporal logic; finite state transition graphs;
model checking algorithms; limiting state explosion.
Administrative Information
- Unique Number: 48130
- Meeting Time/Place: TuTh 5-6:30, TAY 3.144
- Instructor:
E. Allen Emerson
- Office Hours: TBA.
- Classlist with e-mail.
- Texts:
- Lewis and Papadimitriou, Elements of the Theory of Computation,
2nd ed. (Required)
- Arnold, Finite Transition Systems (Recommended)
- Provisional grading scheme:
- Two tests (No Final) 50%.
- Class Participation 50%.
Readings
- E. Allen Emerson,
Temporal and Modal Logic. In J. van Leeuwen, Ed.,
Handbook of Theoretical Computer Science, Vol. B, Elsevier, 1990.
- E. Allen Emerson,
Model Checking and the Mu-Calculus.
- E. Allen Emerson,
Automated Temporal Reasoning about Reactive Systems.
- K. L. McMillan,
The SMV System (draft).
- If you are just getting started with SMV,
click here.