Theory of Computation (Automata, Computability, and Complexity)
- 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. 2019 -- Feb. 2020
- Day and Time: Tuesdays 15:15-16:55
- 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, 2013. (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:
- Final test 100% (2020.02.04)
Homework Assigments:
- Homework1 (assigned 2019.10.08)
- Homework2 (assigned 2019.11.05)
- Homework3 (assigned 2019.11.19)
- Homework4 (assigned 2019.12.03)
- Homework5 (assigned 2020.01.14)
(Submission of homework is not mandatory; only submitted homework will be marked)
Course Outline (tentative):
Dates Topics
- 2019.10.01 Introduction (slides.pdf) (slides.pptx)
- 2019.10.08 Finite automata (slides.pdf) (slides.pptx)
- 2019.10.15 Regular languages (slides.pdf) (slides.pptx)
- 2019.10.29 Nondeterministic finite automata, regular operations (slides.pdf) (slides.pptx)
- 2019.11.05 Regular expressions (slides.pdf) (slides.pptx)
- 2019.11.12 Nonregular languages, pumping lemma (slides.pdf) (slides.pptx)
- 2019.11.19 Context-free grammars, context-free languages, pushdown automata (slides.pdf) (slides.pptx)
- 2019.11.26 Non-context-free languages, pumping lemma (slides.pdf) (slides.pptx)
- 2019.12.03 Turing machines (slides.pdf) (slides.pptx)
- 2019.12.17 Turing-recognizable languages, Turing-decidable languages, variants of Turing machines (slides.pdf) (slides.pptx)
- 2020.01.07 Algorithms, decidable problems, decidability (slides.pdf) (slides.pptx)
- 2020.01.14 Undecidable problems (slides.pdf) (slides.pptx)
- 2020.01.21 Time complexity, P and NP (slides.pdf) (slides.pptx)
- 2020.01.28 Summary (slides.pptx)
- 2020.02.04 Final test
- For 2018 course see here.