3517 Υπολογισιμότητα και Πολυπλοκότητα

Μάθημα Επιλογής, Η’ εξάμηνο, 6 μονάδες ECTS

Διδάσκουσα: Επίκουρη Καθηγήτρια Ευγενία Φουστούκου

URL: https://eclass.aueb.gr/courses/INF147/

Περιεχόμενο

Υπολογισιμότητα: Επαγωγικές αποδείξεις και αναδρομικοί ορισμοί. Κωδικοποιήσεις. Εισαγωγή μοντέλων υπολογισμού. Πρωτογενείς αναδρομικές συναρτήσεις και σχέσεις. Μερικές αναδρομικές συναρτήσεις και ελαχιστοποίηση. Αναδρομικά σύνολα. Μηχανική υπολογισιμότητα. Μηχανές Turing και Turing-υπολογίσιμες συναρτήσεις. Ισοδυναμία μεταξύ αναδρομικών συναρτήσεων και Turing-υπολογίσιμων συναρτήσεων. Θέση Church-Turing. Τα βασικά θεωρήματα: κανονικού τύπου, απαρίθμησης και παραμέτρων (s-m-n). Αναδρομικά απαριθμήσιμα σύνολα και ανεπίλυτα προβλήματα. Ορισιμότητα και αριθμητική ιεραρχία. Turing-αναγωγισιμότητα και βαθμοί μη επιλυσιμότητας. Πολυπλοκότητα: Οι κλάσεις NP και co-NP. Οι κλάσεις της πολυωνυμικής ιεραρχίας και η κλάση PSPACE. Κλάσεις πολυπλοκότητας για προβλήματα εύρεσης (FP, FNP, PPAD). Προβλήματα μέτρησης: η κλάση #P. Κλάσεις για προβλήματα βελτιστοποίησης (APX, MAXSNP). Αναγωγές χάσματος και θεώρημα PCP.

Μαθησιακά Αποτελέσματα

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

Να κατανοούν και να χειρίζονται ορισμούς και αποδείξεις γύρω από τον διαισθητικό/εμπειρικό ορισμό του αλγορίθμου και της υπολογίσιμης συνάρτησης.
Να κατανοούν και να χειρίζονται ορισμούς και αποδείξεις σχετικές με την έννοια του αλγορίθμου ορισμένου ως μαθηματικό αντικείμενο στις δύο -ισοδύναμες μεταξύ τους- θεωρίες, την Θεωρία Αναδρομικών Συναρτήσεων και την Θεωρία Turing-Υπολογίσιμων Συναρτήσεων.
Να κατανοούν και να χειρίζονται την αριθμητικοποίηση δηλαδή την κωδικοποίηση σε φυσικούς αριθμούς των αναδρομικών συναρτήσεων, των μηχανών Turing, των αλγορίθμων καθώς και την αντίστροφη διαδικασία της αποκωδικοποίησης.
Να κατανοούν και να χειρίζονται θεμελειώδεις έννοιες της Θεωρίας Αναδρομικών Συναρτήσεων στους φυσικούς καθώς και βασικά θεωρήματα.
Να κατανοούν και να χειρίζονται το μοντέλο υπολογισμού των Turing-υπολογίσιμων συναρτήσεων.
Να περιγράφουν τις παρακάτω κλάσεις: κλάσεις NP και co-NP, κλάσεις της πολυωνυμικής ιεραρχίας, κλάση PSPACE, κλάσεις πολυπλοκότητας για προβλήματα εύρεσης (FP, FNP, PPAD), για προβλήματα μέτρησης (#P) καθώς και για προβλήματα βελτιστοποίησης (APX, MAXSNP).

Προαπαιτούμενα Μαθήματα

Για να εγγραφεί στο μάθημα, ο φοιτητής πρέπει να έχει εξεταστεί επιτυχώς σε προηγούμενο εξάμηνο είτε στο μάθημα «Αυτόματα και Πολυπλοκότητα» είτε στο μάθημα «Αλγόριθμοι». Όμως, συνιστάται στους φοιτητές να έχουν εξεταστεί επιτυχώς σε προηγούμενο εξάμηνο και στα δύο αυτά μαθήματα καθώς και στο μάθημα «Λογική» σε προηγούμενο εξάμηνο.

Συνιστώμενη Βιβλιογραφία

Εισαγωγή στη Θεωρία Υπολογισμού, M. Sipser, Πανεπιστημιακές Εκδόσεις Κρήτης, 2007.
Computable functions, A. Shen, N.K. Vereshchagin, Student Mathematical Library Vol 19, American Mathematical Society, 2003.
Theory of Computation, Dexter Kozen, Texts in Computer Science, Springer, 2006.
Theory of Computation, George Tourlakis, Wiley Editions, 2012.

Διδακτικές και Μαθησιακές Μέθοδοι

Διαλέξεις (2 δίωρες διαλέξεις εβδομαδιαίως), προαιρετικές ασκήσεις κατ’ οίκον και ενδιάμεση προαιρετική γραπτή εξέταση (πρόοδος).

Μέθοδοι Αξιολόγησης/Βαθμολόγησης

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