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
Θεωρία Υπολογισμού

Title: Θεωρία Υπολογισμού
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.


Algorithms and Complexity, Introduction to Programming, Data Structures, Discrete Mathematics.

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

Final exams.

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