Theory of Computation

Semester:
6ο
Course Type:
Track Compulsory courses (EYM)
Track:
CS (Computer Science)
Code:
Κ25
ECTS:
6
TEACHING HOURS per week
Theory:
3
Seminar:
1
Laboratory:
0
Specializations
Foundations of Computer Science (Ε1):
-
Data and Knowledge Management (Ε2):
Υ Υποχρεωτικό
Software (Ε3):
-
Hardware and Architecture (Ε4):
-
Communications and Networking (Ε5):
-
Signal and Information Processing (Ε6):
-
Related Courses
Course Content

The course covers basic and advanced techniques of the Theory of Computation that are needed in various branches of Theoretical Computer Science. Formal languages. Deterministic and non-deterministic automata. Regular languages. Context-free languages. Non-deterministic pushdown automata. Turing machines. Recursive languages. Recursively enumerable languages. The Church-Turing Thesis. Decidability and undecidability. Introduction to computational complexity.

LITERATURE AND STUDY MATERIALS - READING LIST

Basic textbooks in Greek: H. Lewis, Χ. Παπαδημητρίου. Elements of the Theory of Computation, Kritiki publishers. M. Sipser, Introduction to the theory of computation, Crete University Press.
Additionally the students have access to transparencies by P. Rondogiannis, and recommended literature in English.