Theory of Computation
- Study mathematical models of computation: automata, Turing machines;
- learn the limit of computation: computability theory;
- analyze the efficiency of computation: complexity theory.
Instructor:
- Prof. Kai Cai (Engineering Building F-610)
- Email: kai.cai@eng.osaka-cu.ac.jp
- Office hour: after each lecture or by email appointment
Lecture Schedule:
- Period: Oct. 2018 -- Feb. 2019
- Day and Time: Tuesdays 14:45-16:15
- Location: Engineering Building B-113
Textbook / Reference:
Lecture notes in class will cover all contents. Two excellent references are:
- M. Sipser, "Introduction to the Theory of Computation", Course Technology, 2012. (Available in our library; there is Japanese translation for this book.)
- J.E. Hopcroft, R. Motwani, J.D. Ullman, "Introduction to Automata Theory, Languages, and Computation", Addison Wesley, 2006. (Available in our library)
Prerequisites:
None
Grading:
- Midterm test 50% (2018.12.18, tentative)
- Final test 50% (2019.02.05, tentative)
Homework Assigments:
- Homework1 (assigned 2018.10.17)
- Homework2 (assigned 2018.11.06)
- Homework3 (assigned 2018.11.20)
- Homework4 (assigned 2018.12.11)
- Homework5 (assigned 2019.01.12)
Course Outline (tentative):
Dates Topics
- 2018.10.02 Introduction
- 2018.10.09 Finite automata
- 2018.10.15 Regular languages
- 2018.10.23 Nondeterministic finite automata
- 2018.11.06 Regular expressions
- 2018.11.13 Nonregular languages, pumping lemma
- 2018.11.20 Context-free grammars, context-free languages, pushdown automata
- 2018.11.27 Non-context-free languages, pumping lemma
- 2018.12.04 Turing machines, Turing-decidable languages, Turing-recognizable languages
- 2018.12.11 Decidability, decidable languages
- 2018.12.18 Midterm test
- 2019.01.08 Algorithms, decidable problems
- 2019.01.15 Undecidable problems
- 2019.01.22 Time complexity, NP-completeness
- 2019.01.29 Final test