Θεωρία Υπολογισμών και Αυτομάτων

Το μάθημα εξετάζει τι μπορεί να υπολογίσει ένας υπολογιστής, ανάλογα με την αρχιτεκτονική του. Εξετάζει τρία αφηρημένα μοντέλα υπολογιστών, καθώς και αντίστοιχες κλάσεις προβλημάτων που αυτοί μπορούν να λύνουν. Για την περιγραφή των υπολογιστών χρησιμοποιούνται τα αυτόματα, ενώ για την περιγραφή των προβλημάτων χρησιμοποιούνται οι γλώσσες (σύνολα λέξεων που κατασκευάζονται από πεπερασμένα αλφάβητα).

Στόχοι Μαθήματος

Να είναι σε θέση ο φοιτητής (α) να αναγνωρίζει τα διάφορα αφηρημένα μοντέλα υπολογιστών, (β) να διακρίνει τις διάφορες κλάσεις προβλημάτων, (γ) να αποκτήσει ικανότητα τυπικής περιγραφής των προβλημάτων.

Προαπαιτούμενες Γνώσεις

Δεν υπάρχουν προαπαιτούμενα.

Περιεχόμενα

Αλφάβητα και γλώσσες. Κανονικές εκφράσεις. Κανονικές γλώσσες. Μη-κανονικές γλώσσες. Γραμματικές χωρίς συμφραζόμενα. Γραμματικές χωρίς περιορισμούς. Αυτόματα. Πεπερασμένα αυτόματα. Ντετερμινιστικά και μη-ντετερμινιστικά αυτόματα. Αυτόματα στοίβας. Μηχανές Turing. Θέση του Church. Turing αποφασίσιμες και αποδεκτές γλώσσες. Παγκόσμια μηχανή Turing. Μη υπολογισιμότητα. Μη επιλύσιμα προβλήματα. Κλάσεις πολυπλοκότητας.