Department of Information & Communication Systems Engineering
University of the Aegean
SCHOOL OF ENGINEERING

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
ECTS: 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.

 
Prerequisites
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

Face-to-face.



Home | Contact

University Of The Aegean

SCHOOL OF ENGINEERING
Department of Information & & Communications Systems Engineering

© Copyright ICSD :: 2008 - 2017