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