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