Course Contents (Syllabus):
Finite automata and regular expressions. Pushdown automata and context-free grammars. Turing machines and Church's thesis. Undecidability. Computational complexity.
Elective course, 3rd year
Prerequisites and/or related courses:
Discrete Mathematics, Introduction to Programming, Object-oriented Programming, Algorithms and Complexity, Graph Theory
Objectives:
- Automata and formal grammars
- Turing Machines- Determinism vs non-determinism
- Unsolvability
- Polynomial hierarchy
- P vs NP
Teaching Methods:
Theory lectures (4h/week) and additionally seminars (2h/ 3 weeks) solving exercises.
Assessment methods:
One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.
Teaching Material: Notes
Recommended reading:
- M. Sipser, ‘’Introduction to Theory of Computation’’, Panepistimiakes Ekdosis Kritis, 2007 (in Greek).
- H. R. Lewis & Ch. Papadimitriou, ‘’ Elements of Computation’’, Kritiki, 2005 (in Greek).
Bibliography:
- M. Sipser, ‘’Introduction to Theory of Computation’’, Panepistimiakes Ekdosis Kritis, 2007 (in Greek).
- H. R. Lewis & Ch. Papadimitriou, ‘’ Elements of Computation’’, Kritiki, 2005 (in Greek).
- E. Zachos, ‘’Automata and Formal Grammars’’, Notes, National Technical University of Athens, 2008 (in Greek).
- E. Zachos, ‘’Computability and Complexity’’, Notes, National Technical University of Athens, 2004 (in Greek).