 |
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 2007, from 11 to 12:30 (MW) in 32-144.
Recitation times are Thursdays, 12-1pm and 1-2pm in 26-328.
Office hours for the TA are on Fridays at 12-1pm, and Mondays 12:30-1:30pm in the neighborhood of 32-G614.
You can check your grades here . You need MIT certificates in order to access the site. If you are not in the database, please follow the link to add yourself to the class list.
Please fill up the HKN course evaluation form here . The deadline is May 20th . Thanks!
|