Υπολογισιμότητα και Πολυπλοκότητα


Κωδικός 3.4.3254.8
Εξάμηνο 8o
Ροή Λ - Λογισμικό Η/Υ
Κατηγορία Κατ' επιλογήν υποχρεωτικό
Ώρες Διδασκαλίας - Ώρες Εργαστηρίου 3 - 0
Διδάσκοντες Ευστάθιος Ζάχος, Πέτρος Ποτίκας (Ε.ΔΙ.Π.)
Σύνδεσμοι MyCourses, Ιστοσελίδα Μαθήματος
Πλατφόρμα Διδασκαλίας Τμήμα 1: Webex

Περιγραφή

Υπολογισιμότητα, Λογική θεμελίωση πληροφορικής, Ιστορική αναδρομή στο
πρόβλημα αποκρισιμότητας μαθηματικών προτάσεων, Eπιλυσιμότητα ή
υπολογισιμότητα προβλημάτων με μηχανιστικό, δηλαδή αλγοριθμικό, τρόπο. Απλά
ισοδύναμα υπολογιστικά μοντέλα: μηχανές Turing, προγράμματα WHILE. Επαγωγή
και αναδρομή, κωδικοποίηση και σημασιολογία. Θεωρία σταθερού σημείου. Θεωρία
Tarski και υπολογιστικών στρατηγικών. Αριθμητική ιεραρχία. Προχωρημένα
θέματα από την θεωρία τυπικών. Γραμματικών. Υπολογιστική
Πολυπλοκότητα. Σχέσεις μεταξύ κλάσεων πολυπλοκότητας (L --> NL --> P --> NP
--> PSPACE = NPSPACE --> EXPTIME). Co-κλάσεις, Αναγωγές και
Πληρότητα. Μαντεία. Πολυωνυμική ιεραρχία. Πιθανοτικές, τυχαιότητα
(randomness). Διαλογικές/αλληλεπίδραση, PCP. Μετρητικές
κλάσεις. Προσεγγιστική Πολυπλοκότητα. Πολυπλοκότητα αναζήτησης. Παραμετρική
πολυπλοκότητα. Κβαντική πολυπλοκότητα.