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