Υπολογιστική Πολυπλοκότητα (M171 και ΘΠ20)
Αρχοντία Γιαννοπούλου
Στόχος του μαθήματος είναι ο αυστηρός ορισμός της χρονικής και χωρικής πολυπλοκότητας των αλγορίθμων, ο ορισμός των βασικών κλάσεων πολυπλοκότητας και η παρουσίαση αντιπροσωπευτικών προβλημάτων για κάθε μία από αυτές.
Μεγάλη έμφαση δίνεται στην περιγραφή του μη-ντετερμινιστικού υπολογισμού και στην παρουσίαση του ερωτήματος αν οι κλάσεις P και NP ταυτίζονται.
Τέλος, επιδιώκεται η εξοικείωση των φοιτητών με τις τεχνικές κατάταξης προβλημάτων στις κλάσεις πολυπλοκότητα.
(Περισσότερες πληροφορίες εδώ.)
Ώρες διδασκαλίας: Τετάρτη 11:00 - 13:00 και Πέμπτη 13:00 - 15:00 στην Αίθουσα Δ.
Ημερομηνία έναρξης μαθημάτων: 5 Οκτωβρίου 2022.
Στόχος του μαθήματος είναι ο αυστηρός ορισμός της χρονικής και χωρικής πολυπλοκότητας των αλγορίθμων, ο ορισμός των βασικών κλάσεων πολυπλοκότητας και η παρουσίαση αντιπροσωπευτικών προβλημάτων για κάθε μία από αυτές.
Μεγάλη έμφαση δίνεται στην περιγραφή του μη-ντετερμινιστικού υπολογισμού και στην παρουσίαση του ερωτήματος αν οι κλάσεις P και NP ταυτίζονται.
Τέλος, επιδιώκεται η εξοικείωση των φοιτητών με τις τεχνικές κατάταξης προβλημάτων στις κλάσεις πολυπλοκότητα.
(Περισσότερες πληροφορίες εδώ.)
Ώρες διδασκαλίας: Τετάρτη 11:00 - 13:00 και Πέμπτη 13:00 - 15:00 στην Αίθουσα Δ.
Ημερομηνία έναρξης μαθημάτων: 5 Οκτωβρίου 2022.
Στόχος του μαθήματος είναι ο αυστηρός ορισμός της χρονικής και χωρικής πολυπλοκότητας των αλγορίθμων, ο ορισμός των βασικών κλάσεων πολυπλοκότητας και η παρουσίαση αντιπροσωπευτικών προβλημάτων για κάθε μία από αυτές.
Μεγάλη έμφαση δίνεται στην περιγραφή του μη-ντετερμινιστικού υπολογισμού και στην παρουσίαση του ερωτήματος αν οι κλάσεις P και NP ταυτίζονται.
Τέλος, επιδιώκεται η εξοικείωση των φοιτητών με τις τεχνικές κατάταξης προβλημάτων στις κλάσεις πολυπλοκότητα.
(Περισσότερες πληροφορίες εδώ.)
Ώρες διδασκαλίας: Τετάρτη 11:00 - 13:00 και Πέμπτη 13:00 - 15:00 στην Αίθουσα Δ.
Ημερομηνία έναρξης μαθημάτων: 5 Οκτωβρίου 2022.
Πληροφορίες
Περιεχόμενο μαθήματος
Υπολογισιμότητα:
- Μηχανές Turing (πολυταινιακές Μ.Τ., μη-ντετερμινιστικές Μ.Τ.)
- Η θέση Church-Turing.
Χρονική πολυπλοκότητα:
- Σχέση πολυπλοκότητας μεταξύ μοντέλων (Μ.Τ., πολυταινιακών Μ.Τ. και μη-ντετερμινιστικών Μ.Τ.).
- Χρονική πολυπλοκότητα μη-ντετερμινιστικών Μ.T..
- Η κλάση P.
- Η κλάση NP.
- Το θεώρημα προβολής.
- Η κλάση coNP.
- Η κλάση EXP.
- Αναγωγές και πληρότητα, η έννοια της NP-δυσκολίας.
- Το θεώρημα Cook-Levin.
- NP-πλήρεις γλώσσες.
- Ψευδοπολυωνυμικότητα και ισχυρά NP-πλήρεις γλώσσες.
Χωρική πολυπλοκότητα:
- Το θεώρημα του Savitch.
- H κλάση PSPACE.
- PSPACE πληρότητα.
- Οι κλάσεις L, NL και EXPSPACE.
- NL πληρότητα.
Θεωρήματα Ιεραρχίας:
- Το Θεώρημα Χωρικής Ιεραρχίας.
- Το Θεώρημα Χρονικής Ιεραρχίας.
Προαπαιτούμενα
Οι φοιτητές θα πρέπει να έχουν αποκτήσει εξοικείωση με την έννοια του αλγορίθμου και την ανάλυση της πολυπλοκότητάς του. Πέραν αυτού, καλό θα ήταν να έχουν στοιχειώδεις γνώσεις από τα Διακριτά Μαθηματικά, τη Λογική, τη Θεωρία Συνόλων και τη Θεωρία Γραφημάτων.
Μέθοδοι αξιολόγησης
Oι φοιτητές θα κληθούν να επιλύσουν 2 πακέτα ασκήσεων που θα λειτουργούν βελτιωτικά στον συνολικό βαθμό που θα επιτύχουν στο μάθημα (1.5 μονάδα το κάθε πακέτο για τους προπτυχιακούς και 1 μονάδα το κάθε πακέτο για τους μεταπτυχιακούς). Οι παρουσιάσεις αυτές θα γίνουν τις ώρες διεξαγωγής των διαλέξεων εφόσον ο χρόνος το επιτρέπει, ή σε κάποιο έξτρα δίωρο.
Τελικός βαθμός = min{βαθμός εξέτασης+βαθμός ασκήσεων, 10} εφόσον ο βαθμός της εξέτασης είναι προβιβάσιμος.
Προτεινόμενα συγγράμματα
- Michael Sipser, Εισαγωγή στην Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης (Κωδικός βιβλίου στον Εύδοξο: 86195794)
- Harry R. Lewis, Χρήστος Παπαδημητρίου: Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική (Κωδικός Βιβλίου στον Εύδοξο: 11776)
Βιβλιογραφία
- Christos H. Papadimitriou: Computational Complexity, Pearson publications
- Michael R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Company
- Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press
- John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman: Introduction to automata theory, languages, and computation, Addison-Wesley
Υπολογισιμότητα:
- Μηχανές Turing (πολυταινιακές Μ.Τ., μη-ντετερμινιστικές Μ.Τ.)
- Η θέση Church-Turing.
Χρονική πολυπλοκότητα:
- Σχέση πολυπλοκότητας μεταξύ μοντέλων (Μ.Τ., πολυταινιακών Μ.Τ. και μη-ντετερμινιστικών Μ.Τ.).
- Χρονική πολυπλοκότητα μη-ντετερμινιστικών Μ.T..
- Η κλάση P.
- Η κλάση NP.
- Το θεώρημα προβολής.
- Η κλάση coNP.
- Η κλάση EXP.
- Αναγωγές και πληρότητα, η έννοια της NP-δυσκολίας.
- Το θεώρημα Cook-Levin.
- NP-πλήρεις γλώσσες.
- Ψευδοπολυωνυμικότητα και ισχυρά NP-πλήρεις γλώσσες.
Χωρική πολυπλοκότητα:
- Το θεώρημα του Savitch.
- H κλάση PSPACE.
- PSPACE πληρότητα.
- Οι κλάσεις L, NL και EXPSPACE.
- NL πληρότητα.
Θεωρήματα Ιεραρχίας:
- Το Θεώρημα Χωρικής Ιεραρχίας.
- Το Θεώρημα Χρονικής Ιεραρχίας.
Οι φοιτητές θα πρέπει να έχουν αποκτήσει εξοικείωση με την έννοια του αλγορίθμου και την ανάλυση της πολυπλοκότητάς του. Πέραν αυτού, καλό θα ήταν να έχουν στοιχειώδεις γνώσεις από τα Διακριτά Μαθηματικά, τη Λογική, τη Θεωρία Συνόλων και τη Θεωρία Γραφημάτων.
Oι φοιτητές θα κληθούν να επιλύσουν 2 πακέτα ασκήσεων που θα λειτουργούν βελτιωτικά στον συνολικό βαθμό που θα επιτύχουν στο μάθημα (1.5 μονάδα το κάθε πακέτο για τους προπτυχιακούς και 1 μονάδα το κάθε πακέτο για τους μεταπτυχιακούς). Οι παρουσιάσεις αυτές θα γίνουν τις ώρες διεξαγωγής των διαλέξεων εφόσον ο χρόνος το επιτρέπει, ή σε κάποιο έξτρα δίωρο.
Τελικός βαθμός = min{βαθμός εξέτασης+βαθμός ασκήσεων, 10} εφόσον ο βαθμός της εξέτασης είναι προβιβάσιμος.
- Michael Sipser, Εισαγωγή στην Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης (Κωδικός βιβλίου στον Εύδοξο: 86195794)
- Harry R. Lewis, Χρήστος Παπαδημητρίου: Στοιχεία Θεωρίας Υπολογισμού, Εκδόσεις Κριτική (Κωδικός Βιβλίου στον Εύδοξο: 11776)
- Christos H. Papadimitriou: Computational Complexity, Pearson publications
- Michael R. Garey, David S. Johnson: Computers and Intractability: A Guide to the Theory of NP-completeness, W. H. Freeman and Company
- Sanjeev Arora and Boaz Barak: Computational Complexity: A Modern Approach, Cambridge University Press
- John E Hopcroft, Rajeev Motwani, Jeffrey D Ullman: Introduction to automata theory, languages, and computation, Addison-Wesley
