Theory of Computation

 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.

• Automata and formal grammars
• Turing Machines
• Determinism vs non-determinism
• Unsolvability
• Polynomial hierarchy
• P vs NP

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

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

Notes