9ο εξάμηνο
Μάθημα: Θεωρία πολυπλοκότητας
| Τίτλος μαθήματος |
Θεωρία Πολυπλοκότητας |
| Κωδικός μαθήματος |
Ε10 |
| Είδος μαθήματος |
Επιλεγόμενο |
| Επίπεδο μαθήματος |
Προπτυχιακό |
| Έτος σπουδών |
4ο, 5ο |
| Εξάμηνο |
7ο, 9ο |
| Πιστωτικές μονάδες ECTS |
5 |
| Ιστοσελίδα |
eclass.uowm.gr/courses/ICTE160/ |
| Ώρες ανά εβδομάδα |
4 |
| Διδάσκων |
Δημήτριος Τσαλικάκης |
| Περιεχόμενο μαθήματος |
Προβλήματα, αλγόριθμοι και υπολογιστική πολυπλοκότητα, Μηχανές Turing, Αναδρομικές και αναδρομικά αριθμήσιμες γλώσσες, Ειδικοί τύποι και συνδυασμοί μηχανών Turing, Μη ντετερμινιστικές μηχανές Turing, Καθολικές μηχανές Turing, Η θέση του Church, Μη αποκρισιμότητα, Το πρόβλημα του τερματισμού, Το θεώρημα του Rice, Κλάσεις πολυπλοκότητας και σχέσεις μεταξύ τους, Οι κλάσεις L, NL, P, NP, PSPACE και EXPTIME, Αναγωγές, Η έννοια της Πληρότητας, Το θεώρημα των Cook-Levin, Πληρότητα κατά NP, Το συμπλήρωμα της κλάσης NP |
| Αναμενόμενα μαθησιακά αποτελέσματα και δεξιότητες |
Με την επιτυχή ολοκλήρωση του μαθήματος, οι φοιτητές θα:
- κατανοούν απόλυτα τον σχεδιασμό και την λειτουργία των μηχανών Τuring
- κατανοούν προβλήματα τερματισμού
- κατανοούν τις κλάσεις πολυπλοκότητας και τον τρόπο κατάταξης των προβλημάτων σε κλάσεις
- κατανοούν την έννοια της πληρότητας και θα είναι σε θέση να επιλύσουν προβλήματα
- κατανοούν τις έννοιες της πληρότητας κατά ΝΡ και το συμπλήρωμα κλάσης κατά ΝΡ
|
| Προαπαιτούμενα μαθήματα |
Κανένα |
| Μέθοδοι διδασκαλίας |
Σημειώσεις, Παρουσιάσεις, Ασκήσεις |
| Αξιολόγηση |
Γραπτό (70%), Εργασίες (30%) |
| Γλώσσα διδασκαλίας |
Ελληνική |
| Βιβλιογραφία |
- SIPSER MICHAEL, ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ, ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΚΡΗΤΗΣ, 2009
- Lewis Harry R.,Παπαδημητρίου Χρίστος Χ., Στοιχεία θεωρίας υπολογισμού, ΕΚΔΟΣΕΙΣ ΚΡΙΤΙΚΗ, 2005
|
