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

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

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

Face-to-face.



Home | Contact

University Of The Aegean

SCHOOL OF ENGINEERING
Department of Information & & Communications Systems Engineering

© Copyright ICSD :: 2008 - 2017