0
(
ratings
)
2
students
Created by:
![Profile Photo](https://opencoursa.com/wp-content/uploads/avatars/809/62de1041c5027-bpfull.jpg)
Last updated:
December 1, 2022
Duration:
Unlimited Duration
FREE
This course includes:
Unlimited Duration
Badge on Completion
Certificate of completion
Unlimited Duration
Description
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.
Course Curriculum
- Introduction Unlimited
- Logic, circuits, and gates Unlimited
- Deterministic finite automata (DFAs) and nondeterministic finite automata (NFAs) Unlimited
- NFAs and regular expressions Unlimited
- Non-regular languages and the pumping lemma Unlimited
- Turing machines Unlimited
- Decidability Unlimited
- Undecidable problems and Post correspondence problem (PCP) Unlimited
- Mapping reducibility and Rice’s theorem Unlimited
- Self-reference and the recursion theorem Unlimited
- Introduction to cryptography Unlimited
- Complexity theory Unlimited
- Pseudorandom generators and one-way functions Unlimited
- Public-key cryptography Unlimited
- More complexity theory Unlimited
- More NP-completeness Unlimited
- Probabilistic Turing machines and complexity classes Unlimited
- Trapdoor one-way functions and zero-knowledge proofs Unlimited
- Probably approximately correct (PAC) learning Unlimited
- More PAC learning Unlimited
- Introduction to quantum Unlimited
- Quantum mechanics and BQP Unlimited
- Quantum algorithms Unlimited
About the instructor
5
5
Instructor Rating
1
Reviews
1520
Courses
1916
Students
![Profile Photo](https://opencoursa.com/wp-content/uploads/avatars/809/62de1041c5027-bpfull.jpg)
Massachusetts Institute of Technology