CS3313: Theory of Computation (Fall 2023)
- Instructor:
Huan Long, longhuan (at) sjtu.edu.cn
- Class: 12:55 - 15:40 every Friday
- Place: Dong ZhongYuan 3-406
- TA: Weijun Chen (陈蔚骏), cwj2018(AT)sjtu.edu.cn
- Office hour: 9:00pm - 10:00pm 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 (pdf)
PART III: Computational Complexity
- Time Complexity (pdf)
- NP-completeness (pdf)
- Space Complexity (pdf)
- The log Space (pdf)
- Intractability (pdf)
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