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.

Course Information Sheet

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:

  1. M. Sipser, "Introduction to the Theory of Computation", Course Technology, 2012. (Available in our library; there is Japanese translation for this book.)
  2. 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:

Course Outline (tentative):

    Dates              Topics
  1. 2018.10.02 Introduction
  2. 2018.10.09 Finite automata
  3. 2018.10.15 Regular languages
  4. 2018.10.23 Nondeterministic finite automata
  5. 2018.11.06 Regular expressions
  6. 2018.11.13 Nonregular languages, pumping lemma
  7. 2018.11.20 Context-free grammars, context-free languages, pushdown automata
  8. 2018.11.27 Non-context-free languages, pumping lemma
  9. 2018.12.04 Turing machines, Turing-decidable languages, Turing-recognizable languages
  10. 2018.12.11 Decidability, decidable languages
  11. 2018.12.18 Midterm test
  12. 2019.01.08 Algorithms, decidable problems
  13. 2019.01.15 Undecidable problems
  14. 2019.01.22 Time complexity, NP-completeness
  15. 2019.01.29 Final test