Μάθημα : Υπολογιστική Πολυπλοκότητα

Μαθησιακοί στόχοι

Στόχος του μαθήματος είναι ο αυστηρός ορισμός της χρονικής και χωρικής πολυπλοκότητας των αλγορίθμων, ο ορισμός των βασικών κλάσεων πολυπλοκότητας και η παρουσίαση αντιπροσωπευτικών προβλημάτων για κάθε μία από αυτές. Μεγάλη έμφαση δίνεται στην περιγραφή του μη-ντετερμινιστικού υπολογισμού και στην παρουσίαση του ερωτήματος αν οι κλάσεις P και NP ταυτίζονται. Τέλος, επιδιώκεται η εξοικείωση των φοιτητών με τις τεχνικές κατάταξης προβλημάτων στις κλάσης πολυπλοκότητα.

Προαπαιτούμενα

Οι φοιτητές θα πρέπει να έχουν αποκτήσει εξοικείωση με την έννοια του αλγορίθμου και την ανάλυση της πολυπλοκότητάς του. Πέραν αυτού, καλό θα ήταν να έχουν στοιχειώδεις γνώσεις από τα Διακριτά Μαθηματικά, τη Λογική, τη Θεωρία Συνόλων και τη Θεωρία Γραφημάτων.

Μέθοδοι διδασκαλίας

Θα δίνεται μία τρίωρη διάλεξη την εβδομάδα στην οποία θα παρουσιάζεται η ύλη του μαθήματος. Όταν προχωράει αρκετά η παρουσίαση της ύλης κάποια από τις διαλέξεις αυτές (ή τμήμα τους) θα αφιερώνεται για την επίλυση ασκήσεων.

Ως επιπλέον κίνητρο, οι φοιτητές θα κληθούν να επιλύσουν 2 πακέτα ασκήσεων που θα λειτουργούν βελτιωτικά στον συνολικό βαθμό που θα επιτύχουν στο μάθημα. Πιο συγκεκριμένα, οι φοιτητές θα κληθούν να σχηματίσουν ομάδες συνεργασίας (μέχρι 3 άτομα ανά ομάδα), οι ομάδες αυτές θα πρέπει να επιλύσουν τις ασκήσεις, να γράψουν τις απαντήσεις τους (κατά προτίμηση σε LaTeX) και να τις καταθέσουν στον διδάσκοντα μέσω της πλατφόρμας «η-τάξη». Μετά το πέρας αυτής της διαδικασίας, εφόσον η ορθότητα/πληρότητα των απαντήσεων που έδωσε η κάθε ομάδα ελεγχθεί από τον διδάσκοντα, τα μέλη των ομάδων θα παρουσιάσουν τις απαντήσεις των ασκήσεων στους υπόλοιπους φοιτητές (με τυχαία επιλογή). Οι παρουσιάσεις αυτές θα γίνουν τις ώρες διεξαγωγής των διαλέξεων εφόσον ο χρόνος το επιτρέπει, ή σε κάποιο έξτρα δίωρο.

Στο τέλος του εξαμήνου οι φοιτητές θα κληθούν να συμμετάσχουν στην εξέταση του μαθήματος, κατά την διάρκεια της οποίας θα μπορούν να συμβουλεύονται τις σημειώσεις και τα βιβλία τους, αλλά δεν θα μπορούν να χρησιμοποιήσουν ηλεκτρονικές συσκευές συνδεδεμένες στο διαδίκτυο.

Περιεχόμενο μαθήματος

Υπολογισιμότητα:

• Μηχανές Turing (πολυταινιακές Μ.Τ., μη-ντετερμινιστικές Μ.Τ.)
• Η θέση Church-Turing.

Χρονική πολυπλοκότητα:

• Σχέση πολυπλοκότητας μεταξύ μοντέλων (Μ.Τ., πολυταινιακών Μ.Τ. και μη-ντετερμινιστικών Μ.Τ.).
• Χρονική πολυπλοκότητα μη-ντετερμινιστικών Μ.T..
• Η κλάση P.
• Η κλάση NP.
• Το θεώρημα προβολής.
• Η κλάση CONP.
• Η κλάση EXP.
• Αναγωγές και πληρότητα, η έννοια της NP-δυσκολίας.
• Το θεώρημα Cook-Levin.
• NP-πλήρεις γλώσσες.
• Ψευδοπολυωνυμικότητα και ισχυρά NP-πλήρεις γλώσσες.

Χωρική πολυπλοκότητα:

• Το θεώρημα του Savitch.
• H κλάση PSPACE.
• PSPACE πληρότητα.
• Οι κλάσεις L, NL και EXPSPACE.
• NL πληρότητα.

Θεωρήματα Ιεραρχίας:

• Το θεώρημα χωρικής Ιεραρχίας.
• Το θεώρημα χρονικής Ιεραρχίας.

Μέθοδοι αξιολόγησης

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

• Δημήτρης Ζώρος: (Πρόχειρες) σημειώσεις στη Θεωρία Αναδρομής 
• Michael Sipser: Εισαγωγή στην Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης 
• Harry R. Lewis, Χρήστος Παπαδημητρίου: Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική
• Jon Kleinberg, Eva Tardos: Σχεδιασμός Αλγορίθμων, Εκδόσεις  Κλειδάριθμος
• Christos H. Papadimitriou: Computational Complexity, Pearson publications
• Sanjeev Arora, Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press
• Oded Goldreich, Computational Complexity: A Conceptual Perspective, Cambridge University Press
• Michael R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Company