User Tools
Table of Contents
The goal of this course is to acquaint the students with the basic concepts in computation theory and to cultivate the students' ability in analyzing the complexity of computational problems.
Announcements
- 06/10: slides for space complexity.
- 05/27: old exams: 2000-2017
- 05/20: HW#10 due on 05/27.
- 05/16: Corrected a typo in the slides for Reducibility.
- 05/13: HW#9 due on 05/20.
- 05/06: HW#8 due on 05/13.
- 04/29: HW#7 due on 05/06.
- 04/01: HW#6 due on 04/15.
- 03/25: HW#5 due on 04/1.
- 03/18: Section 4.1 and 4.5 of this paper describes the Rivest's version of the L* algorithm.
- 03/11: Here you can find a good lecture note on minimizing finite automata. We will explain this lecture note on 03/18.
- 03/11: HW#4 due on 03/25.
- 03/4: HW#3 due on 03/18.
- 03/4: HW#2 due on 03/11.
- 02/27: Update HW#1. Fixed a bug in question 0.10.
- 02/25: HW#1 due on 03/04.
Instructors
Yu-Fang Chen (陳郁方)
Institute of Information Science, Academia Sinica
02-27883799 ext 1514
Xyfc@iis.sinica.edu.twX (between the enclosing pair of X's)
Ming-Hsien Tsai (蔡明憲)
Institute of Information Science, Academia Sinica
02-27883799 ext 2411
Xmhtsai208@gmail.comX (between the enclosing pair of X's)
Lectures
Monday 2:20-5:20PM, Room 302, Building II, College of Management
TAs
蕭法宣(Xb04705007@ntu.edu.twX)(between the enclosing pair of X's)
Textbook
- Introduction to the Theory of Computation, 3rd Edition, Michael Sipser, Cengage Learning, 2012. (歐亞圖書代理)
Syllabus/Schedule
This is an introductory course to the theory of computation. It covers
various mathematical models, including automata and Turing machines, for
physical computing machineries along with their computational
capabilities/limitations. In terms of specific topics and the order of their
exposition, the course will follow closely the book by Sipser.
- Introduction and Mathematical Preliminaries (1.5 weeks: 2/18, 2/25) [slides]
- Context-Free Languages and Pushdown Automata (2 weeks: 3/25, 4/1) [slides]
- Midterm (2019/04/15)
- Turing Machines (2 weeks: 4/22 4/29) [slides]
- Decidability (and Undecidability) (1 week: 5/6) [slides]
- Reducibility (2 weeks: 5/13, 5/20) [slides] [selected topics]
- Time Complexity and NP-Completeness [slides] (3 weeks: 5/27, 6/3, 6/10)
- Final (2019/06/17)
Grading
Homework 20%, Participation 10%, Midterm 35%, Final 35%.
