Περιγραφή θέματος

  • Γενικά

    Θεωρία Πολυπλοκότητας

    Διδάσκων : Xάρης Παπαδόπουλος

         

    Περιγραφή μαθήματος: Η έννοια της πολυπλοκότητας επίλυσης προβλημάτων και οι κλάσεις πολυπλοκότητας P, NP, PSPACE, NSPACE, EXP. Μέθοδοι επίλυσης υπολογιστικών δύσκολων προβλημάτων. 

    Μαθησιακοί στόχοι μαθήματος: Στόχος του μαθήματος είναι η μετάδοση γνώσεων στους μεταπτυχιακούς του Τμήματος Μαθηματικών για την μέτρηση πολυπλοκότητας (χρόνος και χώρος), ασυμπτωτικές εκφράσεις και συμβολισμοί, περιορισμοί στους πόρους υπολογισμού, το θεμελιώδες ερώτημα εάν P = NP, το θεώρημα του Savitch, σχέσεις μεταξύ κλάσεων πολυπλοκότητας, η ιεραρχία κλάσεων DSPACE και DTIME. Πολυωνυμικές αναγωγές. Μέθοδοι απόδειξης NP-πληρότητας προβλημάτων. Η πολυωνυμική ιεραρχία χρόνου, PSPACE-πλήρη προβλήματα και αποδεδειγμένα δύσκολα υπολογιστικά προβλήματα. 

    Λέξεις κλειδιά: κλάσεις πολυπλοκότητας, πολυωνυμική αναγωγή, ΝΡ-πληρότητα, μέθοδοι επίλυσης δύσκολων προβλημάτων, ικανοποιησιμότητα λογικών εκφράσεων (SAT). 

  • 1 - Εισαγωγή στη Θεωρία Πολυπλοκότητας

    Περιγραφή θεματικής ενότητας: Εισαγωγή στη Θεωρία Πολυπλοκότητας. Υπολογιστικά δύσκολα προβλήματα. Προβλήματα απόφασης και προβλήματα βελτιστοποίησης. 

    Λέξεις κλειδιά: Προβλήματα απόφασης, Προβλήματα γραφημάτων, αριθμητικά, ικανοποιησιμότητα λογικής έκφρασης. 

  • 2 - H κλάση ΝΡ

    Περιγραφή θεματικής ενότητας: Ασυμπτωτικοί συμβολισμοί, αναγωγές πολυωνυμικού χρόνου, κατηγορίες πολυωνυμικών αναγωγών, αυτοαναγωγή, η κλάση ΝΡ, πιστοποιητές και πιστοποιητικά, προβλήματα απόφασης.  

    Λέξεις κλειδιά: αναγωγή με μικροεργαλεία, Ρ, ΝΡ, ΝΡ-πληρότητα, πιστοποιητές και πιστοποιητικά. 

  • 3 - NP-πληρότητα

    Περιγραφή θεματικής ενότητας: Ικανοποιησιμότητα Κυκλώματος (Το «πρώτο» NP-πλήρες Πρόβλημα), Επέκταση και Επιρροή της ΝΡ-πληρότητας, Προβλήματα συσκευασίας, Προβλήματα κάλυψης, Προβλήματα ικανοποίησης περιορισμών, Προβλήματα καθορισμού ακολουθίας, Προβλήματα διαμέρισης, Αριθμητικά προβλήματα. Η κλάση co-NP και η ασυμμετρία της κλάσης ΝΡ.

    Λέξεις κλειδιά: SET-PACKING, INDEPENDENT SET, SET-COVER, VERTEX-COVER, SAT, 3-SAT, HAMILTONIAN-CYCLE, TSP, 3D-MATCHING 3-COLOR, SUBSET-SUM, KNAPSACK

  • 4 - Κλάσεις Πολυπλοκότητας

    Περιγραφή θεματικής ενότητας: η κλάση PSPACE, Ποσοτικοποιημένη Ικανοποιησιμότητα, Προβλήματα σχεδιασμού, PSPACE-πληρότητα, Στρατηγικές και Θεωρία Παιγνίων. 

    Λέξεις κλειδιά: Ποσοτικοποιημένη Ικανοποιησιμότητα (Q-SAT), Παίγνια, PSACE, PSPACE-πλήρη προβλήματα

  • 5 - Επέκταση ορίων επιλυσιμότητας

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

    Λέξεις κλειδιά: Παραμετροποιημένοι αλγόριθμοι FPT, εκθετικού χρόνου αλγόριθμοι, περιορισμός της εισόδου, δενδροπλάτος (treewidth). 

  • 6 - Προσεγγιστικοί αλγόριθμοι

    Περιγραφή θεματικής ενότητας: Προσεγγιστικοί αλγόριθμοι, προσεγγιστικό σφάλμα, Επιλογή κέντρων, Η μέθοδος επανακοστολόγησης, Γραμμικός και ακέραιος προγραμματισμός, Κάλυμμα κορυφών με βάρη, PTAS, FPTAS, δυσκολία εύρεσης καλού προσεγγιστικού σφάλματος. 

    Λέξεις κλειδιά: Προσεγγιστικοί αλγόριθμοι, προσεγγιστικό σφάλμα, Γραμμικός και ακέραιος προγραμματισμός

  • 7 - Τοπική αναζήτηση

    Περιγραφή θεματικής ενότητας: Τοπική αναζήτηση, ο αλγόριθμος Metropolis, νευρωνικά δίκτυα, μέγιστη αποκοπή με τοπική αναζήτηση, Nash ισορροπία 

    Λέξεις κλειδιά: Τοπική αναζήτηση, δίκτυα Hopfield, μέγιστη αποκοπή, Nash ισορροπία 

  • 8 - Τυχαιοποιημένοι αλγόριθμοι

    Περιγραφή θεματικής ενότητας: Τυχαιοποιημένοι αλγόριθμοι, ολική ελάχιστη αποκοπή, αλγόριθμοι συρρίκνωσης, αναμενόμενη επιλογή, μέγιστη 3-ικανοποιησιμότητα, αλγόριθμοι Monte Carlo και Las Vegas, Όρια του Chernoff

    Λέξεις κλειδιά: Τυχαιοποιημένοι αλγόριθμοι, ολική ελάχιστη αποκοπή, μέγιστη 3-ικανοποιησιμότητα, αλγόριθμοι Monte Carlo και Las Vegas

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

    [KT] J. Kleinberg and E. Tardos, Σχεδιασμός Αλγορίθμων, ελληνική έκδοση, Εκδόσεις Κλειδάριθμος, 2008.

    [CLRS] T. Cormen, C. Leiserson, R. Rivest, and C. Stein, Εισαγωγή στους Αλγορίθμους, ελληνική έκδοση, Πανεπιστημιακές Εκδόσεις Κρήτης, 2012.

    [P94] C. Papadimitriou, Computational Complexity, Addison-Wesley, 1994.

    [AB] S. Arora and B. Barak, Computational Complexity: A Modern Approach,Cambridge University Press, 2009.

    [GJ] M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, Series of Books in the Mathematical Sciences, 1979