9ο εξάμηνο

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



Κωδικός Μαθήματος: Ε10
Επίπεδο Μαθήματος: Προπτυχιακό
Τύπος Μαθήματος: Ειδικού Υποβάθρου
Εξάμηνο: 9
Κατεύθυνση: Κατεύθυνση Υπολογιστών και Ηλεκτρονικής
Πιστωτικές Μονάδες: 5
Εβδομαδιαίες Ώρες διδασκαλίας: 4
Erasmus:
Ιστοσελίδα: eclass.uowm.gr/courses/ICTE160/
Γλώσσα διδασκαλίας:Ελληνική
Γενικές Ικανότητες:
Περιεχόμενο:

Προβλήματα, αλγόριθμοι και υπολογιστική πολυπλοκότητα, Μηχανές 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