Important dates

• 2019/11/05: 停課 (校際活動日)

• 2019/10/11: 停課 (雙十節彈性放假)

• 2019/10/05: 補課 (雙十節彈性放假)

• 2019/09/13: 中秋節

Info

• Course: Computation Theory

• Semester: 108-1

• Credit: 3

• Time: Fri 9:10-12:10

• Classroom: 綜合館 202

Textbook

• Michael Sipser. Introduction to the Theory of Computation, 3/e. CENGAGE Learning.

Reference

• Christos H. Papadimitriou. Computational Complexity. Addison-Wesley

Grading

• midterm 60% (2 group discussions, with take-home exam)

• final 30% (oral presentation/take-home exam)

• participation 10%

Syllabus

• Introduction (last update: 2019/09/19)

• Regular languages (last update: 2019/09/19)

• The Church-Turing thesis (last update: 2019/11/29)

• Decidability (last update: 2019/11/29)

• Reducibility (last update: 2019/11/29)

• Time complexity

• Space complexity

• Intractability

• Selected topics

Assignments

1st: [1.31, 1.32], 1.39, 1.45, 1.48, 1.56, 1.57, 1.58, 1.63

2nd: 4.18, 4.20, 5.16, 5.20, 5.22, 5.28, 5.31, 5.34

reading: PCP is undecidable