Theory of Computation
| Course Code | 321-6700 |
|---|---|
| Semester | 5 |
| ECTS | 5.00 |
| Hours (Theory) | 3 |
| Hours (Lab) | |
| Instructor | Kaporis Alexis |
Course Content
Regular languages, finite automata (deterministic or, non deterministic), 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
- When the student completes the course succesfully:
- She will have the knowledge to identify the limits of the current models of computation.
- She will have the skills to study computing machines.
- She will have the capability to study the power of various computing models.
Prerequisites
Not required.
Teaching and Learning Methods
| Activity | Semester workload |
|---|---|
| Lectures | 39 hours |
| Personal study | 83 hours |
| Final exams | 3 hours |
| Course total | 125 hours (5 ECTS) |
Assessment Methods / Grading
Lectures with slides. The lectures appear in videos to help the understanding.
Teaching Language
Greek (English for Erasmus students)