Home
學生控制台
註冊會員/登入
研究知情同意書
UeduGPTs
Aida 優學伴
Uedu Open
支援與訊息
功能介紹
教學實踐研究
學術交流
教學工作坊
開發者 API
活動主辦

UeduGPTs

--

Jupyters

2

AI 回覆桌面通知

AI 助教回覆完成時顯示桌面通知

聊天訊息通知

同學在討論區發送訊息時通知

聲音通知

每當有新通知時播放提示音

更多設定
帳戶設定 資料隱私設定 研究知情同意書
Uedu Open / Theory of Computation
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.
課程資訊
來源MIT 開放式課程
科系Electrical Engineering and Computer Science
語言English
影片數25
課程影片 (25)
1
1. Introduction, Finite Automata, Regular Expressions
1. Introduction, Finite Automata, Regular Expressions
2
2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
2. Nondeterminism, Closure Properties, Conversion of Regular Expressions to FA
3
3. Regular Pumping Lemma, Conversion of FA to Regular Expressions
3. Regular Pumping Lemma, Conversion of FA to Regular Expressions
4
4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
4. Pushdown Automata, Conversion of CFG to PDA and Reverse Conversion
5
5. CF Pumping Lemma, Turing Machines
5. CF Pumping Lemma, Turing Machines
6
6. TM Variants, Church-Turing Thesis
6. TM Variants, Church-Turing Thesis
7
7. Decision Problems for Automata and Grammars
7. Decision Problems for Automata and Grammars
8
8. Undecidability
8. Undecidability
9
9. Reducibility
9. Reducibility
10
10. Computation History Method
10. Computation History Method
11
11. Recursion Theorem and Logic
11. Recursion Theorem and Logic
12
12. Time Complexity
12. Time Complexity
13
14. P and NP, SAT, Poly-Time Reducibility
14. P and NP, SAT, Poly-Time Reducibility
14
15. NP-Completeness
15. NP-Completeness
15
16. Cook-Levin Theorem
16. Cook-Levin Theorem
16
17. Space Complexity, PSPACE, Savitch's Theorem
17. Space Complexity, PSPACE, Savitch's Theorem
17
18. PSPACE-Completeness
18. PSPACE-Completeness
18
19. Games, Generalized Geography
19. Games, Generalized Geography
19
20. L and NL, NL = coNL
20. L and NL, NL = coNL
20
21. Hierarchy Theorems
21. Hierarchy Theorems
21
22. Provably Intractable Problems, Oracles
22. Provably Intractable Problems, Oracles
22
23. Probabilistic Computation, BPP
23. Probabilistic Computation, BPP
23
24. Probabilistic Computation (cont.)
24. Probabilistic Computation (cont.)
24
25. Interactive Proof Systems, IP
25. Interactive Proof Systems, IP
25
26. coNP is a subset of IP
26. coNP is a subset of IP