0

(

ratings

)

2

students

Created by:

Profile Photo

Last updated:

September 21, 2023

Duration:

Unlimited Duration

FREE

This course includes:

Unlimited Duration

Badge on Completion

Certificate of completion

Unlimited Duration

Description

18.404J/6.840J The Theory of Computation(Fall 2020, MIT OCW). Instructor: Prof. Michael Sipser. This course emphasizes computability and computational complexity theory.

Topics include regular and context-free languages, decidable and undecidable problems, reducibility, recursive function theory, time and space measures on computation, completeness, hierarchy theorems, inherently complex problems, oracles, probabilistic computation, and interactive proof systems. (from ocw.mit.edu)

Course Curriculum

  • Lecture 01 – Introduction: Finite Automata, Regular Expressions Unlimited
  • Lecture 02 – Nondeterminism, Closure Properties, Regular Expressions to Finite Automata Unlimited
  • Lecture 03 – Regular Pumping Lemma, Finite Automata to Regular Expressions Unlimited
  • Lecture 04 – Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion Unlimited
  • Lecture 05 – CF Pumping Lemma, Turing Machines Unlimited
  • Lecture 06 – TM Variants, Church-Turing Thesis Unlimited
  • Lecture 07 – Decision Problems for Automata and Grammars Unlimited
  • Lecture 08 – Undecidability Unlimited
  • Lecture 09 – Reducibility Unlimited
  • Lecture 10 – Computation History Method Unlimited
  • Lecture 11 – Recursion Theorem and Logic Unlimited
  • Lecture 12 – Time Complexity Unlimited
  • Lecture 14 – P and NP, SAT, Poly-Time Reducibility Unlimited
  • Lecture 15 – NP-Completeness Unlimited
  • Lecture 16 – Cook-Levin Theorem Unlimited
  • Lecture 17 – Space Complexity, PSPACE, Savitch’s Theorem Unlimited
  • Lecture 18 – PSPACE-Completeness Unlimited
  • Lecture 19 – Games, Generalized Geography Unlimited
  • Lecture 20 – L and NL, NL = coNL Unlimited
  • Lecture 21 – Hierarchy Theorems Unlimited
  • Lecture 22 – Provably Intractable Problems, Oracles Unlimited
  • Lecture 23 – Probabilistic Computation, BPP Unlimited
  • Lecture 24 – Probabilistic Computation (cont.) Unlimited
  • Lecture 25 – Interactive Proof Systems, IP Unlimited
  • Lecture 26 – coNP is a subset of IP Unlimited

About the instructor

5 5

Instructor Rating

6

Reviews

4637

Courses

24151

Students

Profile Photo
OpenCoursa
We are an educational and skills marketplace to accommodate the needs of skills enhancement and free equal education across the globe to the millions. We are bringing courses and trainings every single day for our users. We welcome everyone woth all ages, all background to learn. There is so much available to learn and deliver to the people.