| Κωδικός Μαθήματος | 23Υ302 |
| Τίτλος | Υπολογιστική Πολυπλοκότητα |
| Τύπος | Υποχρεωτικά Μαθήματα |
| Ιστοσελίδα | http://lca.ceid.upatras.gr/courses/cc/index.html |
| Περιγραφή | Μηχανές Turing. Ειδικοί τύποι και συνδυασμοί μηχανών Turing. Μη ντετερμινιστικές μηχανές Turing. Καθολικές μηχανές Turing. Αλγοριθμικά επιλύσιμα προβλήματα. Η θέση του Church. Αλγοριθμικά μη επιλύσιμα προβλήματα. Το πρόβλημα της περάτωσης. Η έννοια της υπολογιστικής πολυπλοκότητας αλγορίθμων. Προβλήματα επιλύσιμα με αποδοτικό τρόπο. Κλάσεις πολυπλοκότητας. Οι κλάσεις P και NP. Αναγωγές μεταξύ προβλημάτων. Προβλήματα πλήρη στην κλάση NP. Η σχέση των κλάσεων P και NP. Η πολυωνυμική ιεραρχία κλάσεων πολυπλοκότητας. Πολυπλοκότητα ως προς χώρο. |
| Αρμοδιότητα Διδασκαλίας | Τομέας Εφαρμογών και Θεμελιώσεων της Επιστήμης των Υπολογιστών |
| Εξάμηνο | 6 |
| Διδακτικές Μονάδες | 4 |
| Ώρες Διδασκαλίας | 2 |
| Ώρες Φροντιστηρίου | 2 |
| Ώρες Εργαστηρίου | |
| Καθηγητές | |
