Θεωρία Υπολογισμού

Επαγωγικές αποδείξεις και αναδρομικοί ορισμοί. Εισαγωγή μοντέλων υπολογισμού. Πρωτογενείς αναδρομικές συναρτήσεις και σχέσεις. Μερικές αναδρομικές συναρτήσεις και ελαχιστοποίηση. Μηχανική υπολογισιμότητα. Μηχανές 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 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.

Υλικό: Σημειώσεις



Ενημέρωση: 10-Νοε-2017                                                                                                                            email: emarkou@ucg.gr