Computation Models, Formal Languages and Automata

Type
Elective
Course Description

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

Name Year Semester Taught by
Computation Models, Formal Languages and Automata 2021-2022 Spring Stathis Zachos, Petros Potikas
Computation Models, Formal Languages and Automata 2020-2021 Spring Stathis Zachos, Petros Potikas
Computation Models, Formal Languages and Automata 2019-2020 Spring Stathis Zachos
Computation Models, Formal Languages and Automata 2018-2019 Spring Stathis Zachos
Computation Models, Formal Languages and Automata 2017-2018 Spring Stathis Zachos
Computation Models, Formal Languages and Automata 2016-2017 Spring Stathis Zachos