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