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

Όσοι προτίθενται να παρακολουθήσουν τη «Θεωρία Υπολογισμού», παρακαλώ να εγγραφούν στο μάθημα στο 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. Εισαγωγή στην Υπολογιστική Πολυπλοκότητα

Εξετάσεις

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

Hall of Fame

Από το ακαδημαϊκό έτος 2023-2024, τη δημιουργία του λεγόμενου Mega-Quiz (του μεγάλου Quiz που διεξάγεται μία εβδομάδα μετά τις διακοπές του Πάσχα) ανέλαβαν φοιτητές/φοιτήτριες με εξαιρετική επίδοση και/ή ενεργή συμμετοχή κατά την προηγούμενη ακαδημαϊκή χρονιά, οι οποίοι προσφέρθηκαν εθελοντικά να συνεισφέρουν. Ως ελάχιστη ένδειξη εκτίμησης για τη συμβολή τους, παρατίθενται στη συνέχεια τα ονόματά τους:

· 2023-2024: Γιώργος Νικολάου (ο οποίος ξεκίνησε και το θεσμό του Mega-Quiz)

· 2024-2025: to be announced

---