CS3313: Theory of Computation (Fall 2024)
- Instructor:
Huan Long, longhuan (at) sjtu.edu.cn
- Class: 12:55 - 15:40 every Thursday
- Place: Dong ShangYuan 107
- TA: TBA
- Office hour: 9:00am - 11:00am every Tuesday,
Location: Dianxin Building 3-327 (电信群楼3-327)
Announcement
PART I: Automata and Language
- Finite automata and regular language (pdf)
- Pushdown automata and context free language (pdf)
- (*) Deterministic Context-Free Languages (pdf)
PART II: Computability
- The Church-Turing Thesis (pdf)
- Decidability (pdf)
- Reducibility (pdf)
- (*) Goedel Number
PART III: Computational Complexity
- Time Complexity
- NP-completeness
- Space Complexity
- The log Space
- Intractability
Assignments
- CANVAS
References
- Introduction to the Theory of Computation, Michael Sipser, Third Edition, 2012.
- 计算复杂性, 傅育熙,清华大学出版社,2023.
- N.J.Cutland, Computability:An introduction to recursive function theory, 1980
- Robert I. Soare, Recursively Enumerable Sets and Degrees: A study of computable functions and computably generated sets, 1987