Μαθηματικές Θεμελιώσεις της Θεωρίας Υπολογισμού
Μέρος πρώτο: Λογική και απόδειξη. Επανάληψη στην Προτασιακή Λογική: Αλφάβητο, συντακτικό και σημασιολογία. Επανάληψη στην Κατηγορηματική Λογική: Αλφάβητο, συντακτικό και σημασιολογία, Βασικές μέθοδοι αποδείξεων: Ευθεία απόδειξη, Απόδειξη με αντιθετοαντιστροφή, Απόδειξη ύπαρξης (με κατασκευή και χωρίς κατασκευή), Μη-ευθεία απόδειξη, Απόδειξη με μαθηματική επαγωγή (ασθενής και ισχυρή μορφή της επαγωγής). Τυπικά συστήματα παραγωγής συμπερασμάτων: Hilbert-style συστήματα, Σημαντικοί πίνακες. Αναδρομές και επαγωγή. Επιβεβαίωση προγραμμάτων με τη χρήση της Λογικής Hoare: Μερική Ορθότητα κώδικα, Ολική ορθότητα κώδικα. Σχέσεις-Σχεσιακές βάσεις δεδομένων (στοιχειώδης παρουσίαση της Prolog).
Μέρος δεύτερο. Αυτόματα και τυπικές γλώσσες. Αλφάβητα και γλώσσες. Κανονικές εκφράσεις και κανονικές γλώσσες. Ντετερμινιστικά και μη Ντετερμινιστικά πεπερασμένα Αυτόματα. Λήμμα άντλησης για κανονικές γλώσσες. Γραμματικές και γλώσσες ανεξάρτητες συμφραζομένων. Κανονικές γραμματικές. Απλούστευση και αναγωγή γραμματικών. Λήμμα άντλησης για γλώσσες ανεξάρτητες συμφραζομένων. Αυτόματα στοίβας. Συντακτική ανάλυση. Μηχανές Turing. Υπολογισμοί με μηχανές Turing. Γραμματικές χωρίς περιορισμούς. Υπολογισιμότητα. Μη αποφασίσιμες γλώσσες. Αναδρομικά αριθμήσιμες γλώσσες. Τα όρια της υπολογισιμότητας. Θεώρημα του Rice.