Αυτόματα και Υπολογιστικά Μοντέλα
Section outline
-
Δείτε
http://old.corelab.ntua.gr/courses/afl/
Εαρινό εξάμηνο 2021-2022
Περιγραφή
Οι γλώσσες και οι αναπαραστάσεις τους. Γραμματικές, context-sensitive και context-free γραμματικές. Πεπερασμένα αυτόματα και κανονικές γραμματικές. Pushdown Αυτόματα. Μηχανές Turing. Αυτόματα και αναγνώριση γλωσσών. Τυπικές γραμματικές. Εφαρμογές στη σύνταξη των γλωσσών προγραμματισμού. Προβλήματα (αν)αποκρισιμότητας και πολυπλοκότητας. Υπολογισιμότητα: LOOP προγράμματα, WHILE προγράμματα. Προσεγγισιμότητα. Τυχαιότητα. Ω-αυτόματα, αυτόματα δένδρων.
Διδάσκοντες
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Πέτρος Ποτίκας, Ε.Δι.Π. (ppotik@cs.ntua.gr)
Διαλέξεις
- Τετάρτη 15:15-17:00
- Παρασκευή 15:15-17:00
Αίθουσα
- 1.1.29, παλ. κτ. ΗΜΜΥ
Τρόπος εξέτασης
Η εξέταση του μαθήματος αποτελείται από δύο μέρη: α) Μέρος Α, ερωτήσεις θεωρίας και είναι με κλειστές σημειώσεις και βιβλία και β) Μέρος Β, ασκήσεις και είναι με ανοιχτές σημειώσεις (επιτρέπεται να χρησιμοποιήσετε τις σημειώσεις σας και βιβλία).
Βιβλιογραφία
- Σ. Ζάχος, Σημειώσεις
- Σ. Ζάχος, Α. Παγουρτζής, Τα Θεμέλια της Πληροφορικής, εκδόσεις Τσότρας, 2014
- Μ. Sipser. Introduction to the Theory of Computation.
- J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation.
- H. R. Lewis and C. Papadimitriou. Elements of the Theory of Computation, 2nd edition.
- D. C. Kozen. Automata and Computability (Undergraduate Texts in Computer Science).
- M. Harrison. Introduction to Switching and Automata Theory. McGraw-Hill Book Company, New York (1965).
- C. Papadimitriou. Computational Complexity.
- S. Arora, B. Barak. Computational Complexity: A modern approach.
- E. Grädel, W. Thomas, Th. Wilke. Automata, Logics and Infinite Games.
Υλικό
Διαφάνειες μαθήματος
- Αυτόματα και Τυπικές Γραμματικές, Μοντέλα Υπολογισμού, Υπολογιστική Πολυπλοκότητα και Προσεγγιστικοί Αλγόριθμοι
- Διαφάνειες Γλωσσών προγραμματισμού
- Σημειώσεις Γλωσσών προγραμματισμού
- Διαφάνειες διαλογικής αλληλεπίδρασης
- Ω-αυτόματα, αυτόματα δέντρων
- Ehrenfeucht-Fraisse games
- Θεώρημα Parikh
Ασκήσεις
Αυτόματα και Τυπικές Γραμματικές- 1η σειρά (ps) (pdf)
- 2η σειρά (ps) (pdf)
- 3η σειρά (ps) (pdf)
- 4η σειρά (ps) (pdf)
- 5η σειρά (ps) (pdf)
- 6η σειρά (ps) (pdf)
Μοντέλα υπολογισμού
Πολυπλοκότητα
- 11η σειρά (pdf)