Τμήμα Μηχανικών Ηλεκτρονικών Υπολογιστών και Πληροφορικής

Πολυτεχνική Σχολή - Πανεπιστήμιο Ιωαννίνων

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

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

Κωδικός μαθήματος: ΜΥΕ036

Εβδομαδιαίες ώρες διδασκαλίας: 3,2,0

Εξάμηνο σπουδών: >=6ο

Διδακτικές Μονάδες: 4

Μονάδες ECTS: 5

Ιστοσελίδα Μαθήματος:

Προσφερόμενο: NAI

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

Περιεχόμενο:

Τύποι υπολογιστικών προβλημάτων. Ντετερμινιστικές και μη ντετερμινιστικές μηχανές Turing. Μέτρα πολυπλοκότητας. Χρόνος εκτέλεσης και χώρος εργασίας μίας μηχανής Turing. Κλάσεις πολυπλοκότητας. Σχέσεις εγκλεισμού μεταξύ κλάσεων. Οι κλάσεις P, NP και coNP. Πολυωνυμικές αναγωγές και πληρότητα. Το θεώρημα του Cook. NP-πλήρη προβλήματα. Η κλάση PSPACE και το θεώρημα του Savitch. Η κλαση NSPACE(n) και το θεώρημα του Kuroda. Πιθανοτικές κλάσεις πολυπλοκότητας: RP, BPP και ZPP.

Παρατηρήσεις: