Theory of Computation (5ΕΠ08)
Instructor : Evripides Markou
Course typeElective
Semester5
TermFall Semester
ECTS5
Teaching hours3
Laboratory hours
Description
Induction proofs and recursive definitions. Introduction to models of computation. Primitive recursive functions and relations. Partial recursive functions and minimalization. Computability. Turing machines and Turing computable functions. Church - Turing thesis. Basic Theorems : Normal form, enumerability and s-m-n Theorem. Recursive enumerable sets and unsolvable problems. Definability and arithmetical hierarchy. Turing reducibility and degrees of unsolvability. Computational complexity. Deterministic and Nondeterministic Turing machines. The classes P and NP. Polynomial time reductions and NPcompleteness. Cook's Theorem. NP-complete problems and reductions.
Course objectives
  • Automata and formal grammars
  • Turing Machines
  • Determinism vs non-determinism
  • Unsolvability
  • Polynomial hierarchy
  • P vs NP
Textbooks/Bibliography
  • Εισαγωγή στη Θεωρία Υπολογισμού, M. Sipser, Πανεπιστημιακές Εκδόσεις Κρήτης, 2007.
  • Στοιχεία θεωρίας υπολογισμού, H. Lewis, Χ. Παπαδημητρίου, Εκδόσεις Κριτική, 2005.
  • Αυτόματα και Τυπικές Γραμματικές, Ε. Ζάχος, Σημειώσεις, Εθνικό Μετσόβιο Πολυτεχνείο, 2008.
  • Υπολογισιμότητα και Πολυπλοκότητα, Ε. Ζάχος, Σημειώσεις, Εθνικό Μετσόβιο Πολυτεχνείο, 2004.
Assessment method
One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.
Course material
Notes