MIT机电工程与计算机科学系【本科生课程】6.080.理论计算机科学中的伟大思想.Great.Ideas.in.Theoretical.Computer.Science.pdf

Great Ideas in puter
Science
As taught in: Spring 2008

Searle's Chinese Room, a thought experiment discussed in lecture 6.
(Image courtesy of Tiffany Wang. Used with permission.)

Instructors:
Prof. Scott Aaronson
MIT Course Number:
/
Level:
Undergraduate

Course Description
This course provides a challenging introduction to some of the central ideas of puter science. It attempts
to present a vision of "computer science puters": that is, CS as a set of mathematical tools for understanding
complex systems such as universes and minds. Beginning in antiquity—with Euclid's algorithm and other ancient
examples putational thinking—the course will progress rapidly through propositional logic, Turing machines and
computability, finite automata, Gödel's theorems, efficient algorithms and reducibility, pleteness, the P versus
NP problem, decision trees and other putational models, the power of randomness, cryptography and
one-way functions, computational theories of learning, interactive proofs, and puting and the physical
limits putation. Class participation is essential, as the class will include discussion and debate about the
implications of many of these ideas.

Syllabus
Course Meeting Times
Lectures: 2 sessions / week, hours / session
This course provides a challenging introduction to some of the central ide