Department of Information & Communication Systems Engineering
University of the Aegean

Department of Information
& Communication Systems Engineering

Information & Communication Systems Security
Information Systems
Artificial Intelligence
Computer & Communication Systems
Geometry, Dynamical Systems & Cosmology
Theory of Computation

Title: Theory of Computation
Lesson Code: 321-6702
Semester: 5
Theory Hours: 3
Lab Hours:
Faculty: Kaporis Alexios
Content outline

Regular languages, finite automata, pumping lemma for regular languages. Grammars for context free languages, pushdown automata, pumping lemma. Turing machines, computability and Church-Turing thesis. Non computability, halting problem. Time complexity, class P, Cook-Carp Thesis. NP completeness and time reductions. Space complexity and Savitch's theorem.

Learning outcomes

To understand the limits of computation through the study of simple and complex computing machines.

Not required.
Basic Textbooks

1. Sipser Michael, Introduction to the Theory of Computation.
2. Lewis Harry R., Παπαδημητρίου Χρίστος Χ., Elements of the Theory of Computation.

Additional References

Information and Computation

Learning Activities and Teaching Methods

Lectures with slides. The lectures appear in videos to help the understanding.

Assessment/Grading Methods


Activity Semester workload
Lectures 39 hours

Personal study 83 hours
Final exams 3 hours
Course total 125 hours (5 ECTS)


Language of Instruction
Greek, English (for Erasmus students)
Μode of delivery


Home | Contact

University Of The Aegean

Department of Information & & Communications Systems Engineering

© Copyright ICSD :: 2008 - 2017