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