計算理論概論
Introduction to Theory of Computation
| 節 | 週三 |
|---|---|
5 13:20–14:10 | 計算理論概論 MB311（光復） 3 節連堂 |
6 14:20–15:10 | |
7 15:30–16:20 |
* 根據陽明交大上課時間表所列
This course is intended as an upper-level undergraduate or graduate introduction to theory of computation. In studying this subject we seek to determine what can and cannot be computed, how quickly, with how much memory, and on which type of computational model. It can be divided into roughly four parts: automata and languages, computability theory, complexity theory, and learning theory.
(optional) Algorithms or Discrete Mathematics
無備註
教師未提供此項資料
1. Homework and Assignments: 4 homework assignments 2. Evaluation and Grading Policy: Homework: exercises (60%) Presentations: assigned class materials (40%)
Regular Languages
- 講授：
- 9
Context-Free Grammars
- 講授：
- 6
Turing Machines
- 講授：
- 6
Decidability
- 講授：
- 6
Reducibility
- 講授：
- 6
Time Complexity
- 講授：
- 6
Final presentation
- 其他：
- 3
Introduction and Preliminaries
- 講授：
- 6
| 週次 | 主題 |
|---|---|
| 第 1 週 | Introduction and Preliminaries 2024-02-21(三) |
| 第 2 週 | Introduction and Preliminaries 2024-02-28(三) |
| 第 3 週 | Regular Languages 1 2024-03-06(三) |
| 第 4 週 | Regular Languages 1 2024-03-13(三) |
| 第 5 週 | Regular Languages 2 2024-03-20(三) |
| 第 6 週 | Context-Free Grammars 2024-03-27(三) |
| 第 7 週 | Context-Free Grammars 2024-04-03(三) |
| 第 8 週 | Turing Machines 2024-04-10(三) |
| 第 9 週 | Turing Machines 2024-04-17(三) |
| 第 10 週 | Decidability 2024-04-24(三) |
| 第 11 週 | Decidability 2024-05-01(三) |
| 第 12 週 | Reducibility 2024-05-08(三) |
| 第 13 週 | Reducibility 2024-05-15(三) |
| 第 14 週 | Time Complexity 2024-05-22(三) |
| 第 15 週 | Learning Theory 2024-05-29(三) |
| 第 16 週 | Final presentation 2024-06-05(三) |
Introduction to the Theory of Computation 3rd edition, Michael Sipser. 2012 References: Computational Complexity: A Modern Approach, S. Arora and B. Barak. 2009 Understanding Machine Learning: From Theory to Algorithms, Shai Shalev-Shwartz and Shai Ben-David. 2014
- 地點
- TBD
- 時間
- By appointment
- 聯絡方式
- poanch@gmail.com