Το μάθημα καλύπτει βασικά και προχωρημένα θέματα της Θεωρίας Υπολογισμού που αποτελούν απαραίτητο υπόβαθρο σε διάφορους κλάδους της Θεωρητικής Πληροφορικής. Τυπικές γλώσσες. Ντετερμινιστικά και μη-ντετερμινιστικά πεπερασμένα αυτόματα. Κανονικές γλώσσες. Γλώσσες χωρίς συμφραζόμενα. Μη-ντετερμινιστικά αυτόματα στοίβας. Μηχανές Turing. Αναδρομικές γλώσσες. Αναδρομικά απαριθμήσιμες γλώσσες. Η Θέση των Church-Turing. Αποφασισιμότητα. Εισαγωγή στην υπολογιστική πολυπλοκότητα.
Βασικά συγγράμματα: H. Lewis, Χ. Παπαδημητρίου. Στοιχεία Θεωρίας Υπολογισμού, εκδόσεις Κριτική.
M. Sipser, Εισαγωγή στη Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης.
Επιπλέον παρέχονται διαφάνειες του Π. Ροντογιάννη, οι οποίες βρίσκονται στη σελίδα του μαθήματος, καθώς και συνιστώμενη ξενόγλωσση βιβλιογραφία.