Περιεχόμενα: Γλώσσες και προβλήματα. Πεπερασμένα αυτόματα. Μηχανές Turing, υπολογισμοί με μηχανές Turing, επεκτάσεις της Μηχανής Turing. Μη Επιλυσιμότητα, αναγωγές προβλημάτων. Ακολούθως, εξετάζονται οι βασικές κλάσεις πολυπλοκότητας χρόνου και χώρου και οι γνωστές μεταξύ τους σχέσεις. Εξετάζεται σχετικά αναλυτικά η κλάση ΝΡ και τα πλήρη της προβλήματα, εμβαθύνοντας στην έννοια της αναγωγής, καθώς και η πολυωνυμική ιεραρχία. Έμφαση δίνεται σε μερικά από τα αποτελέσματα που αναδεικνύουν τη δυσκολία διαχωρισμού κλάσεων πολυπλοκότητας, με αναφορά ιδίως στο περίφημο πρόβλημα P vs NP.
Aν ο χρόνος επιτρέπει, εξετάζονται - έστω και επιφανειακά - κάποιο από τα πιό «προχωρημένα» θέματα στη Θεωρία Πολυπλοκότητας (πιθανοτική πολυπλοκότητα, προσεγγισιμότητα, δομικές ιδιότητες του ΝΡ).

Αξιολόγηση: Γραπτή εξέταση στο τέλος του εξαμήνου.

Μέθοδοι αξιολόγησης: Ερωτήσεις σύντομης απάντησης, Ερωτήσεις ανάπτυξης δοκιμίων, Ερωτήσεις πολλαπλής επιλογής, Επίλυση προβλημάτων.

https://eclass.uop.gr/courses/1769/

Βιβλιογραφία:

1. H. Lewis, Χ. Παπαδημητρίου, Στοιχεία θεωρίας υπολογισμού, 1η έκδοση, Κριτική, 2005. Κωδικός στον Εύδοξο: 11776
2. M. Sipser, Εισαγωγή στη θεωρία υπολογισμού, 1η έκδοση, Πανεπιστημιακές Εκδόσεις Κρήτης, 2009. Κωδικός στον Εύδοξο: 257