Αυτόματα και Υπολογιστικά Μοντέλα (ΣΕΜΦΕ)
Section outline
-
Δείτε πρώτα
http://old.corelab.ntua.gr/courses/afl/
Εαρινό εξάμηνο 2020-2021
Περιγραφή
Οι γλώσσες και οι αναπαραστάσεις τους. Γραμματικές, context-sensitive και context-free γραμματικές. Πεπερασμένα αυτόματα και κανονικές γραμματικές. Pushdown Αυτόματα. Μηχανές Turing. Αυτόματα και αναγνώριση γλωσσών. Τυπικές γραμματικές. Εφαρμογές στη σύνταξη των γλωσσών προγραμματισμού. Προβλήματα (αν)αποκρισιμότητας και πολυπλοκότητας. Υπολογισιμότητα: LOOP προγράμματα, WHILE προγράμματα. Προσεγγισιμότητα. Τυχαιότητα. Ω-αυτόματα, αυτόματα δένδρων.
Διδάσκοντες
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Πέτρος Ποτίκας, Ε.Δι.Π. (ppotik@cs.ntua.gr)
Διαλέξεις
- Τετάρτη 15:00-17:00, εξ αποστάσεως
- Παρασκευή 15:00-17:00, εξ αποστάσεως
Σύνδεσμος
Meeting link:
https://centralntua.webex.com/centralntua/j.php?MTID=m2710044577fcb1aaff4569c196308c66
Meeting number:121 090 8900
Password:automata@xxxx_21 (όπου xxxx το ακρωνύμιο του ΕΜΠ στα αγγλικά, όλα με πεζά)
Τρόπος εξέτασης
Η εξέταση του μαθήματος αποτελείται από δύο μέρη: α) Μέρος Α, ερωτήσεις θεωρίας και είναι με κλειστές σημειώσεις και βιβλία και β) Μέρος Β, ασκήσεις και είναι με ανοιχτές σημειώσεις (επιτρέπεται να χρησιμοποιήσετε τις σημειώσεις σας και βιβλία).
Βιβλιογραφία
- Σ. Ζάχος, Σημειώσεις
- Σ. Ζάχος, Α. Παγουρτζής, Τα Θεμέλια της Πληροφορικής, εκδόσεις Τσότρας, 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.
Υλικό
Διαφάνειες μαθήματος
- Αυτόματα και Τυπικές Γραμματικές, Μοντέλα Υπολογισμού, Υπολογιστική Πολυπλοκότητα και Προσεγγιστικοί Αλγόριθμοι
- Αυτόματα και Τυπικές Γραμματικές, Μοντέλα Υπολογισμού, Υπολογιστική Πολυπλοκότητα και Προσεγγιστικοί Αλγόριθμοι (NEO)
- Διαφάνειες Γλωσσών προγραμματισμού
- Σημειώσεις Γλωσσών προγραμματισμού
- Διαφάνειες διαλογικής αλληλεπίδρασης
- Ω-αυτόματα, αυτόματα δέντρων (νέες διαφάνειες)
- Ehrenfeucht-Fraisse games
- Θεώρημα Parikh
Ασκήσεις
Αυτόματα και Τυπικές Γραμματικές
- 1η σειρά (ps) (pdf)
- 2η σειρά (ps) (pdf)
- 3η σειρά (ps) (pdf)
- 4η σειρά (ps) (pdf)
- 5η σειρά (ps) (pdf)
- 6η σειρά (ps) (pdf)
Μοντέλα υπολογισμού
Πολυπλοκότητα
- 11η σειρά (pdf)