Theory of Computation

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, 4th 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).

Updated: 19-July-2017                                                                               email: emarkou@ucg.gr