6.045 Automata, Computability, and Complexity

Class Info

Provides an introduction to some of the central ideas of theoretical computer science, including circuits, finite automata, Turing machines and computability, efficient algorithms and reducibility, the P versus NP problem, NP-completeness, the power of randomness, cryptography, computational learning theory, and quantum computing. Examines the classes of problems that can and cannot be solved in various computational models.

This class has 6.042 as a prerequisite.

6.045 will not be offered this semester. It will be available in the Spring semester, and will be instructed by R. R. Williams.

Lecture occurs 2:30 PM to 4:00 PM on Tuesdays and Thursdays in 4-270.

This class counts for a total of 12 credits.

You can find more information at the http://www.google.com/search?&q=MIT+%2B+6.045&btnG=Google+Search&inurl=https site or on the 6.045 Stellar site.

Recommended Textbooks
Save up to up to 50% by purchasing through MIT Textbooks!
MIT 6.045 Automata, Computability, and Complexity Related Textbooks
MIT 6.045 Automata, Computability, and Complexity On The Web

© Copyright 2015