Automata, Computability, and Complexity, Spring 2011
Remix and Share
- Author:
- Aaronson, Scott
- Subject:
- Science and Technology
- Institution Name:
- M.I.T.
- Collection:
- MIT OpenCourseWare
- Grade Level:
- Post-secondary
- Abstract:
This course provides a challenging introduction to some of the central ideas of theoretical computer science. Beginning in antiquity, the course will progress through finite automata, circuits and decision trees, Turing machines and computability, efficient algorithms and reducibility, the P versus NP problem, NP-completeness, the power of randomness, cryptography and one-way functions, computational learning theory, and quantum computing. It examines the classes of problems that can and cannot be solved by various kinds of machines. It tries to explain the key differences between computational models that affect their power.
- Languages:
- English
- Material Type:
- Full Course, Homework and Assignments, Lecture Notes, Readings, Syllabi
- Media Format:
- Text/HTML, Downloadable docs
- Conditions of Use:
- Creative Commons Attribution-Noncommercial-Share Alike 3.0
- Copyright Holder:
- Massachusetts Institute of Technology
Comments