Θεωρία υπολογισμών και αυτομάτων
Πανεπιστήμιο Μακεδονίας
Τμήμα Εφαρμοσμένης Πληροφορικής
Έτος: 2013-2014
Διδάσκων: Ρεφανίδης Ιωάννης
Περιγραφή Μαθήματος
Το μάθημα είναι προπτυχιακό, διδάσκεται στο 7ο εξάμηνο σπουδών και εξετάζει τι μπορεί να υπολογίσει ένας υπολογιστής, ανάλογα με την αρχιτεκτονική του. Εξετάζει τρία αφηρημένα μοντέλα υπολογιστών, καθώς και αντίστοιχες κλάσεις προβλημάτων που αυτοί μπορούν να λύνουν. Για την περιγραφή των υπολογιστών χρησιμοποιούνται τα αυτόματα, ενώ για την περιγραφή των προβλημάτων χρησιμοποιούνται οι γλώσσες (σύνολα λέξεων που κατασκευάζονται από πεπερασμένα αλφάβητα). Μαθησιακοί στόχοι του μαθήματος είναι να είναι σε θέση ο φοιτητής (α) να αναγνωρίζει τα διάφορα αφηρημένα μοντέλα υπολογιστών, (β) να διακρίνει τις διάφορες κλάσεις προβλημάτων, (γ) να αποκτήσει ικανότητα τυπικής περιγραφής των προβλημάτων.
Video-Διαλέξεις
Διάλεξη 01: Εισαγωγή (2013-10-08)
Αλφάβητα και γλώσσες. Κανονικές εκφράσεις.
Διάλεξη 02: Ντετερμιμιστικά πεπερασμένα αυτόματα (2013-10-15)
Διάλεξη 03: Μη-ντετερμιμιστικά πεπερασμένα αυτόματα (2013-10-22)
Μετατροπή σε ισοδύναμα ντετερμινιστικά.
Διάλεξη 04: Μη-ντετερμινιστικά πεπερασμένα αυτόματα με ε-μεταβάσεις (2013-10-29)
Ιδιότητες των γλωσσών των πεπερασμένων αυτομάτων. Ισοδυναμία γλωσσών πεπερασμένων αυτομάτων και κανονικών εκφράσεων.
Διάλεξη 05: Μη κανονικές γλώσσες (2013-11-05)
Θεώρημα άντλησης. Γραμματικές χωρίς συμφραζόμενα.
Διάλεξη 06 (2013-11-12)
Διάλεξη 07: Αυτόματα στοίβας (2013-11-19)
Γλώσσες χωρίς συμφραζόμενα.
Διάλεξη 08: Ιδιότητες γραμματικών χωρίς συμφραζόμενα (2013-11-26)
Θεώρημα άντλησης για γραμματικές χωρίς συμφραζόμενα. Ντετερμινιστικά αυτόματα στοίβας. Μηχανές Turing. Υπολογισμοί. Παραλλαγές της βασικής μηχανής.
Διάλεξη 09 (2013-12-03)
Διάλεξη 10: Συνδυασμοί μηχανών Turing (2013-12-10)
Θέση του Church. Turing αποφασίσιμες γλώσσες. Turing αποδεκτές γλώσσες. Γραμματικές χωρίς περιορισμούς.
Διάλεξη 11: Καθολική μηχανή Turing (2013-12-17)
Το πρόβλημα του τερματισμού. Μη-αποφασίσιμα προβλήματα.
Διάλεξη 12: Μη ντετερμινιστικές μηχανές Turing (2014-01-14)
Μη ντετερμινισμός και αποφασισιμότητα. Αναγωγές. Απαριθμήσιμες γλώσσες. Θεώρημα του Rice. Υπολογιστική πολυπλοκότητα. Παραδείγματα προβλημάτων. Οι κλάσεις P, NP και EXP.
Διάλεξη 13: Πολυωνυμική αναγωγή (2014-01-21)
NP-πληρότητα. Το θεώρημα του Cook. P vs NP. Αντιμετώπιση NP προβλημάτων.