Επαγωγικές αποδείξεις και αναδρομικοί ορισμοί. Εισαγωγή μοντέλων υπολογισμού. Πρωτογενείς αναδρομικές συναρτήσεις και σχέσεις. Μερικές αναδρομικές συναρτήσεις και ελαχιστοποίηση. Μηχανική υπολογισιμότητα. Μηχανές Turing και Turing υπολογίσιμες συναρτήσεις. Θέση Church-Turing. Τα βασικά θεωρήματα: Κανονικού τύπου, απαρίθμησης και παραμέτρων (s-m-n). Αναδρομικά απαριθμήσιμα σύνολα και ανεπίλυτα προβλήματα. Ορισιμότητα και αριθμητική ιεραρχία. Turing αναγωγισιμότητα και βαθμοί αναποκρισιμότητας. Υπολογιστική πολυπλοκότητα. Αιτιοκρατικές και μη - αιτιοκρατικές μηχανές Turing. Οι κλάσεις P και NP. Πολυωνυμικοί μετασχηματισμοί και NP - πληρότητα. Το θεώρημα του Cook. NP - πλήρη προβλήματα και αναγωγές.
Χειμ. Εξάμηνο 2014 - 2015. Μάθημα επιλογής 4ου έτους
Πρόγραμμα: Δευτέρα 16.00-18.00 (Αίθ. 4)
Τρίτη 08.00-10.00 (Αίθ. 4)
Προαπαιτούμενες γνώσεις ή/και σχετικά μαθήματα:
Διακριτά Μαθηματικά, Εισαγωγή στον Προγραμματισμό, Αντικειμενοστρεφής Προγραμματισμός, Αλγόριθμοι και Πολυπλοκότητα, Θεωρία Γράφων
Μαθησιακοί Στόχοι:
- Μοντέλα υπολογισμού και τυπικές γραμματικές
- Μηχανές Turing
- Ντετερμινισμός και μή-ντετερμινισμός
- Μή-επιλυσιμότητα
- Πολυωνυμική ιεραρχία
- Κλάσεις P και NP
Μέθοδοι Διδασκαλίας:
Διαλέξεις θεωρίας (4 ώρες/εβδομάδα) και επιπλέον φροντιστηριακά μαθήματα με επίλυση ασκήσεων (2 ώρες/ 3 εβδομάδες).
Τρόπος Εξέτασης:
Μία σειρά ασκήσεων κάθε 3 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.
Υλικό: Σημειώσεις