Η έννοια του υπολογισμού. Μοντέλα υπολογισμού. Πεπερασμένα αυτόματα, κανονικές εκφράσεις, γλώσσες και γραμματικές. Μή-κανονικές γλώσσες, το λήμμα της άντλησης για κανονικές γλώσσες. Αυτόματα στοίβας, γλώσσες και γραμματικές χωρίς συμφραζόμενα. Η ιεραρχία του Chomsky. Μηχανές Turing, θέση Church-Turing. Η έννοια του ντετερμινισμού. Ντετερμινιστικές και μή-ντετερμινιστικές μηχανές Turing. Η έννοια της υπολογισιμότητας. Το θεώρημα της μή-πληρότητας του Godel. Αναδρομικές, αναδρομικά αριθμήσιμες και μή-αριθμήσιμες γλώσσες. Αποκρίσιμες, καταγράψιμες και μή-αποκρίσιμες γλώσσες. Το πρόβλημα του Τερματισμού. Κωδικοποίηση κατά Cantor, Godel, κλπ. Η έννοια της αυτοαναφοράς. Μή-επιλύσιμα προβλήματα, η μέθοδος της διαγωνιοποίησης. Υπολογιστική πολυπλοκότητα. Οι κλάσεις P και NP. Η έννοια της αναγωγής, NP - πληρότητα. Το θεώρημα του Cook. NP - πλήρη προβλήματα και αναγωγές. Άλλες κλάσεις πολυπλοκότητας. Πολυωνυμική ιεραρχία.
Χειμ. Εξάμηνο 2023 - 2024. Μάθημα επιλογής 3ου έτους
Πρόγραμμα: Παρασκευή 11.00-14.00, Αίθ. 2
Προαπαιτούμενες γνώσεις ή/και σχετικά μαθήματα:
Διακριτά Μαθηματικά, Εισαγωγή στον Προγραμματισμό, Αντικειμενοστρεφής Προγραμματισμός, Αλγόριθμοι και Πολυπλοκότητα, Θεωρία Γραφημάτων
Μαθησιακοί Στόχοι:
Σκοπός του μαθήματος είναι η εξοικείωση των φοιτητών με την έννοια του υπολογισμού, των διαφορετικών μοντέλων υπολογισμού και τους περιορισμούς τους. Η κατανόηση της αντιστοιχίας μεταξύ των μοντέλων υπολογισμού, και των αλγορίθμων. Η εξοικείωση με την έννοια της (μή-) υπολογισιμότητας. Η παρουσίαση προβλημάτων χωρίς γνωστούς αποδοτικούς αλγόριθμους και η σημασία των κλάσεων πολυπλοκότητας. Μετά την επιτυχή παρακολούθηση του μαθήματος ο φοιτητής θα μπορεί:
- να μοντελοποιήσει σωστά κάποιο πρόβλημα σε μία γλώσσα (σύνολο συμβολοακολουθιών)
- να σχεδιάσει το κατάλληλο αυτόματο που επιλύει (ή γραμματική που παράγει) κάποια γλώσσα
- να αποδείξει την αδυναμία κάποιου μοντέλου υπολογισμού να αναγνωρίσει κάποια γλώσσα
- να αποδείξει ότι ένα πρόβλημα είναι μή-επιλύσιμο
- να αποδείξει ότι ένα πρόβλημα είναι NP-πλήρες (που σημαίνει ότι το πιο πιθανό είναι να μην έχει αποδοτικό αλγόριθμο)
Μέθοδος Διδασκαλίας:
Διαλέξεις (3 ώρες/εβδομάδα).
Τρόπος Εξέτασης:
Tελικές γραπτές εξετάσεις.
Υλικό: Σημειώσεις