7ο εξάμηνο


Μάθημα: Θεωρία πολυπλοκότητας



Τίτλος μαθήματος Θεωρία Πολυπλοκότητας
Κωδικός μαθήματος Ε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