|
|
 |
|
 |
|
Image of cover of Prof. Sipser's textbook. (Courtesy of Thomson/Course Technology. Used with permission.)
|
|
|
Highlights of this Course
This course web site features problem sets, a sample mid-term exam, and information about Professor Sipser's textbook: Introduction to the Theory of Computation.
Course Description
A more extensive and theoretical treatment of the material in 18.400J, Automata, Computability, and Complexity, emphasizing computability and computational complexity theory. Regular and context-free languages. Decidable and undecidable problems, reducibility, recursive function theory. Time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems.
|
|
|
| Staff |
|
Instructor:
Prof. Michael Sipser
|
| Course Meeting Times |
Lectures:
Two sessions / week
1.5 hours / session
Recitations:
One session / week
1 hour / session
|
| Level |
|
Graduate
|
| Feedback |
| Send
feedback about OCW or this course. |
|
|
|
|
|
 |
|