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

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

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

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

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

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

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

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

Μονάδες ECTS: 5

Ιστοσελίδα Μαθήματος: http://www.cse.uoi.gr/~cnomikos/courses/cc/cc-main.htm

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

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

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

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

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

Εξ αποστάσεως διδασκαλία μέσω της εφαρμογής MS TEAMS: Σχετικές πληροφορίες υπάρχουν σελίδα του μαθήματος  http://www.cse.uoi.gr/~cnomikos/courses/cc/cc-main.htm