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%)

Γλώσσα διδασκαλίας

Ελληνική

Βιβλιογραφία

[1]      SIPSER MICHAEL, ΕΙΣΑΓΩΓΗ ΣΤΗ ΘΕΩΡΙΑ ΥΠΟΛΟΓΙΣΜΟΥ, ΠΑΝΕΠΙΣΤΗΜΙΑΚΕΣ ΕΚΔΟΣΕΙΣ ΚΡΗΤΗΣ, 2009

[2]      Lewis Harry R.,Παπαδημητρίου Χρίστος Χ., Στοιχεία θεωρίας υπολογισμού, ΕΚΔΟΣΕΙΣ ΚΡΙΤΙΚΗ, 2005