 |
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 2003, from 11 to 12:30 (MW) in 37-212.
Recitations times are 1pm and 4pm, Thursdays, in 34-304.
There will be an additional recitation at 10:00am on Thursday in
34-302.
TA Office Hours will be held Monday from 5-6pm, Tuesday from 1-2pm and
Tuesday 4:30-6:00pm. Additional times available by appointment.
TA Office Hours will be held in the 3rd floor lounge
of building
NE43.
|