Theory of Computation

Course ID
5ΕΠ08
Επίπεδο
Undergraduate
Είδος
Optional (compulsory)
Εξάμηνο
5
Περίοδος
Fall Semester
ECTS
5
Ώρες Θεωρίας
3
Ώρες Εργαστηρίου
-

Instructor

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

  • ΘΕΜΕΛΙΩΔΕΙΣ ΕΝΝΟΙΕΣ ΤΗΣ ΕΠΕΞΕΡΓΑΣΙΑΣ ΣΗΜΑΤΩΝ, McCLELLAN, SCHAFER, YODER, “ΓΚΟΤΣΗΣ ΚΩΝ/ΝΟΣ & ΣΙΑ Ε.Ε.”,  1η /2006, ΠΑΤΡΑ, 13255848
  • Βασικές Αρχές Σημάτων και Συστημάτων, Καραγιάννης Γιώργος, Μαραγκός Πέτρος, “Α. ΠΑΠΑΣΩΤΗΡΙΟΥ & ΣΙΑ Ι.Κ.Ε.”, 1η έκδ./2010, ΑΘΗΝΑ, 9770
  • Βασικές Τεχνικές Ψηφιακής Επεξεργασίας Σημάτων, Μουστακίδης Γεώργιος Β., ΕΚΔΟΣΕΙΣ Α. ΤΖΙΟΛΑ & ΥΙΟΙ Α.Ε., 1η εκδ./2004, ΘΕΣ/ΝΙΚΗ, 18548755

Assessment method

 One group of exercises (homework) every 3 weeks, mid-term written examination, final written examination.

Course material

Notes