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