Θεωρία Υπολογισμού

Όσοι προτίθενται να παρακολουθήσουν τη «Θεωρία Υπολογισμού», παρακαλώ να εγγραφούν στο μάθημα στο eclass πριν την έναρξη του εαρινού εξαμήνου.

Ώρες διδασκαλίας του μαθήματος

Δευτέρα 9:00 – 11:00

Πέμπτη 9:00 – 11:00

Ύλη του μαθήματος

Κανονικές γραμματικές και γλώσσες - πεπερασμένα αυτόματα. Γραμματικές και γλώσσες ανεξάρτητες συμφραζόμενων - αυτόματα στοίβας.

Αναδρομικές γλώσσες - μηχανές Turing. Αποφασισιμότητα (decidability). Ντετερμινισμός. Αναγωγές προβλημάτων (reductions).

Συγγράμματα

· H. Lewis, Χ. Παπαδημητρίου. Στοιχεία Θεωρίας Υπολογισμού, εκδόσεις Κριτική, 2005.

· M. Sipser, Εισαγωγή στη Θεωρία Υπολογισμού, Πανεπιστημιακές Εκδόσεις Κρήτης, 2007.

Διδακτικές Ενότητες

1. Εισαγωγή - Γλώσσες

2. Κανονικές Γλώσσες

3. Πεπερασμένα Αυτόματα

4. Ιδιότητες Κανονικών Γλωσσών – Pumping Lemma

5. Γραμματικές χωρίς Συμφραζόμενα – Αυτόματα Στοίβας

6. Ιδιότητες Γραμματικών χωρίς Συμφραζόμενα – Pumping Lemma

7. Μηχανές Turing

8. Υπολογισμοί με μηχανές Turing

9. Επεκτάσεις της Μηχανής Turing

10. Μη Επιλυσιμότητα

11. Εισαγωγή στην Υπολογιστική Πολυπλοκότητα

Εξετάσεις

Η ύλη για τις τελικές εξετάσεις βρίσκεται εδώ.

---