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

Επαγωγικές αποδείξεις και αναδρομικοί ορισμοί. Εισαγωγή μοντέλων υπολογισμού. Πρωτογενείς αναδρομικές συναρτήσεις και σχέσεις. Μερικές αναδρομικές συναρτήσεις και ελαχιστοποίηση. Μηχανική υπολογισιμότητα. Μηχανές Turing και Turing υπολογίσιμες συναρτήσεις. Θέση Church-Turing. Τα βασικά θεωρήματα: Κανονικού τύπου, απαρίθμησης και παραμέτρων (s-m-n). Αναδρομικά απαριθμήσιμα σύνολα και ανεπίλυτα προβλήματα. Ορισιμότητα και αριθμητική ιεραρχία. Turing αναγωγισιμότητα και βαθμοί αναποκρισιμότητας. Υπολογιστική πολυπλοκότητα. Αιτιοκρατικές και μη - αιτιοκρατικές μηχανές Turing. Οι κλάσεις P και NP. Πολυωνυμικοί μετασχηματισμοί και NP - πληρότητα. Το θεώρημα του Cook. NP - πλήρη προβλήματα και αναγωγές.

Χειμ. Εξάμηνο 2018 - 2019. Μάθημα επιλογής 3ου έτους

Πρόγραμμα: Δευτέρα 18.00-21.00, Αίθ. 4


Προαπαιτούμενες γνώσεις ή/και σχετικά μαθήματα: 

Διακριτά Μαθηματικά, Εισαγωγή στον Προγραμματισμό, Αντικειμενοστρεφής Προγραμματισμός, Αλγόριθμοι και Πολυπλοκότητα, Θεωρία Γράφων


Μαθησιακοί Στόχοι:

- Μοντέλα υπολογισμού και τυπικές γραμματικές

- Μηχανές Turing

- Ντετερμινισμός και μή-ντετερμινισμός

- Μή-επιλυσιμότητα

- Πολυωνυμική ιεραρχία

- Κλάσεις P και NP


Μέθοδοι Διδασκαλίας: 

Διαλέξεις θεωρίας (3 ώρες/εβδομάδα) και επιπλέον φροντιστηριακά μαθήματα με επίλυση ασκήσεων (2 ώρες/ 3 εβδομάδες).

Τρόπος Εξέτασης:

Μία σειρά ασκήσεων κάθε 3 εβδομάδες, ενδιάμεση γραπτή εξέταση (πρόοδος), τελικές γραπτές εξετάσεις.

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



Δείτε εδώ την περιγραφή των θεμάτων που έχουμε συζητήσει.



Ενημέρωση: 12-Οκτ-2023                                                                                                                            email: e<lastname>@dib.uth.gr