 |
6.045/18.400
Automata, Computability, and Complexity |
|
Slower paced than 6.840J/18.404J. Introduces basic mathematical models
of computation and the finite representation of infinite
objects. Finite automata and regular languages. Context-free
languages. Turing machines. Partial recursive functions. Church's
Thesis. Undecidability. Reducibility and completeness. Time complexity
and NP-completeness. Probabilistic computation. Interactive proof
systems.
This course is offered Spring of 2005, from 11 to 12:30 (MW) in 37-212.
Recitation times are Thursdays, 10am in 34-302 and 1pm and 4pm in 34-304.
Office hours for the TA are (tentatively) Mondays 4-5pm in 32-G630 (actually somewhere in the ε-neighborhood of 32-G630) and by appointment.
|