UeduGPTs

--

Jupyters

8

Local AI

--

CISOSE26 本地 AI UG26

AI Reply Desktop Notifications

Show a desktop notification when the AI TA finishes replying

Chat Message Notifications

Notify me when classmates post messages in the forum

Sound notification

Play an alert sound whenever there is a new notification

More settings

Account settings Data privacy settings Research Informed Consent Form

18.404J

Theory of Computation

Prof. Michael Sipser | Fall 2020

Data Science, Analytics & Computer Technology Computer Science Science & Math Mathematics Engineering Computation Discrete Mathematics Theory of Computation

前往原始課程

CC BY-NC-SA 4.0

課程簡介

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.

Course Information

Source	MIT 開放式課程
科系	Electrical Engineering and Computer Science
Language	English
影片數	25

課程影片 (25)

1. Introduction, Finite Automata, Regular Expressions

1. Introduction, Finite Automata, Regular Expressions

2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA

2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA

3. Regular Pumping Lemma, Conversion of FA to Regular Expressions

3. Regular Pumping Lemma, Conversion of FA to Regular Expressions

4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion

4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion

5. CF Pumping Lemma, Turing Machines

5. CF Pumping Lemma, Turing Machines

6. TM Variants, Church-Turing Thesis

6. TM Variants, Church-Turing Thesis

7. Decision Problems for Automata and Grammars

7. Decision Problems for Automata and Grammars

8. Undecidability

8. Undecidability

9. Reducibility

9. Reducibility

10. Computation History Method

10. Computation History Method

11. Recursion Theorem and Logic

11. Recursion Theorem and Logic

12. Time Complexity

12. Time Complexity

14. P and NP, SAT, Poly-Time Reducibility

14. P and NP, SAT, Poly-Time Reducibility

15. NP-Completeness

15. NP-Completeness

16. Cook-Levin Theorem

16. Cook-Levin Theorem

17. Space Complexity, PSPACE, Savitch's Theorem

17. Space Complexity, PSPACE, Savitch's Theorem

18. PSPACE-Completeness

18. PSPACE-Completeness

19. Games, Generalized Geography

19. Games, Generalized Geography

20. L and NL, NL = coNL

20. L and NL, NL = coNL

21. Hierarchy Theorems

21. Hierarchy Theorems

22. Provably Intractable Problems, Oracles

22. Provably Intractable Problems, Oracles

23. Probabilistic Computation, BPP

23. Probabilistic Computation, BPP

24. Probabilistic Computation (cont.)

24. Probabilistic Computation (cont.)

25. Interactive Proof Systems, IP

25. Interactive Proof Systems, IP

26. coNP is a subset of IP

26. coNP is a subset of IP