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