Μοντέλα υπολογισμού, Τυπικές Γλώσσες και Αυτόματα

Τύπος
Επιλογής
Περιγραφή μαθήματος

Υπολογισιμότητα: Λογική θεμελίωση πληροφορικής. Ιστορική αναδρομή στο πρόβλημα αποκρισιμότητας μαθηματικών προτάσεων, επιλυσιμότητας ή υπολογισιμότητας προβλημάτων με μηχανιστικό, δηλαδή αλγοριθμικό, τρόπο. Απλά ισοδύναμα υπολογιστικά μοντέλα: μηχανές Turing, προγράμματα WHILE. Επαγωγή και αναδρομή, κωδικοποίηση και σημασιολογία. Θεωρία σταθερού σημείου. Μαντεία και Αριθμητική ιεραρχία. Θεωρία αυτομάτων και τυπικών γραμματικών: Πεπερασμένα αυτόματα. Κανονικά σύνολα και ισοδύναμοι χαρακτηρισμοί. Ιεραρχία Chomsky. Αποδείξεις για το εάν L∈C ή L∉C. Εφαρμογές στο συντακτικό γλωσσών προγραμματισμού. Πολυπλοκότητα: Σχέσεις μεταξύ κλάσεων πολυπλοκότητας. Αναγωγές και Πληρότητα.  Πολυωνυμική ιεραρχία. Πιθανοτικές, διαλογικές και μετρητικές κλάσεις. Παραμετρική πολυπλοκότητα. Κβαντική πολυπλοκότητα.

Όνομα Έτος Εξάμηνο Διδάσκων/ντες
Μοντέλα υπολογισμού, Τυπικές Γλώσσες και Αυτόματα 2021-2022 Εαρινό Ευστάθιος Ζάχος, Πέτρος Ποτίκας
Μοντέλα υπολογισμού, Τυπικές Γλώσσες και Αυτόματα 2020-2021 Εαρινό Ευστάθιος Ζάχος, Πέτρος Ποτίκας
Μοντέλα υπολογισμού, Τυπικές Γλώσσες και Αυτόματα 2019-2020 Εαρινό Ευστάθιος Ζάχος
Μοντέλα υπολογισμού, Τυπικές Γλώσσες και Αυτόματα 2018-2019 Εαρινό Ευστάθιος Ζάχος
Μοντέλα υπολογισμού, Τυπικές Γλώσσες και Αυτόματα 2017-2018 Εαρινό Ευστάθιος Ζάχος
Μοντέλα υπολογισμού, Τυπικές Γλώσσες και Αυτόματα 2016-2017 Εαρινό Ευστάθιος Ζάχος