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