Προβλήματα, αλγόριθμοι και υπολογιστική πολυπλοκότητα, Μηχανές Turing, Αναδρομικές και αναδρομικά αριθμήσιμες γλώσσες, Ειδικοί τύποι και συνδυασμοί μηχανών Turing, Μη ντετερμινιστικές μηχανές Turing, Καθολικές μηχανές Turing, Η θέση του Church, Μη απο­κρισιμότητα, Το πρόβλημα του τερματισμού, Το θεώρημα του Rice, Κλάσεις πολυπλοκότητας και σχέσεις μεταξύ τους, Οι κλάσεις L, NL, P, NP, PSPACE και EXPTIME, Αναγωγές, Η έννοια της Πληρότητας, Το θεώρημα των Cook-Levin, Πληρότητα κατά NP, Το συμπλήρωμα της κλάσης NP

Με την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα:

• κατανοούν απόλυτα τον σχεδιασμό και την λειτουργία των μηχανών Τuring
• κατανοούν προβλήματα τερματισμού
• κατανοούν τις κλάσεις πολυπλοκότητας και τον τρόπο κατάταξης των προβλημάτων σε κλάσεις
• κατανοούν την έννοια της πληρότητας και θα είναι σε θέση να επιλύσουν προβλήματα
• κατανοούν τις έννοιες της πληρότητας κατά ΝΡ και το συμπλήρωμα κλάσης κατά ΝΡ

-

Σημειώσεις, Παρουσιάσεις, Ασκήσεις

Γραπτό (70%), Εργασίες (30%)

• SIPSER MICHAEL, ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ, ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΚΡΗΤΗΣ, 2009
• Lewis Harry R.,Παπαδημητρίου Χρίστος Χ., Στοιχεία θεωρίας υπολογισμού, ΕΚΔΟΣΕΙΣ ΚΡΙΤΙΚΗ, 2005