Αυτόματα και Υπολογιστικά Μοντέλα (Αυτόματα και Τυπικές Γραμματικές) (ΣΕΜΦΕ)

εαρινό εξάμηνο 2018-2019

● Γενικά ● Ανακοινώσεις ● Υλικό ●

Γενικά

Διδάσκοντες

  • Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
  • Πέτρος Ποτίκας, Ε.Δι.Π. (ppotik@cs.ntua.gr)

Βοηθοί διδασκαλίας

  • Γιάννης Παπαϊωάννου, Υ.Δ. (ipapaioannou@corelab.ntua.gr)

Διαλέξεις

  • Τετάρτη 15:00-17:00, 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων
  • Παρασκευή 15:00-17:00, 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων

Βιβλιογραφία

  1. Σ. Ζάχος, Σημειώσεις
  2. Σ. Ζάχος, Α. Παγουρτζής, Τα Θεμέλια της Πληροφορικής, εκδόσεις Τσότρας, 2014
  3. Μ. Sipser. Introduction to the Theory of Computation.
  4. J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation.
  5. H. R. Lewis and C. Papadimitriou. Elements of the Theory of Computation, 2nd edition.
  6. D. C. Kozen. Automata and Computability (Undergraduate Texts in Computer Science).
  7. M. Harrison. Introduction to Switching and Automata Theory. McGraw-Hill Book Company, New York (1965).
  8. C. Papadimitriou. Computational Complexity.
  9. S. Arora, B. Barak. Computational Complexity: A modern approach.
  10. E. Grädel, W. Thomas, Th. Wilke. Automata, Logics and Infinite Games.

Ανακοινώσεις

  • Στο μάθημα της Παρασκευής 31/5 στις 15:00 θα λυθούν ασκήσεις και θα απαντηθούν απορίες.
  • Οι διαφάνειες του μαθήματος ενημερώθηκαν. Στο σύνδεσμο παρακάτω οι παλιές έχουν αντικατασταθεί με τις καινούργιες. Οι αλλαγές αφορούν την ισοδυναμία LOOP-προγραμμάτων και πρωταρχικά αναδρομικών συναρτήσεων, το σχήμα της πολυωνυμικής ιεραρχίας, μερικές προσθήκες για recursive και r.e. sets, μαντεία και αριθμητική ιεραρχία και διάγραμμα Hasse αντί Venn στους προσεγγιστικούς αλγόριθμους.
  • Η ώρα του μαθήματος αλλάζει την Τετάρτη από 15-17 σε 13-15.
  • Το πρώτο μάθημα θα γίνει την Τετάρτη 20/2/19, 15:00-17:00.

Υλικό

Διαλέξεις

Διαφάνειες μαθήματος

Ασκήσεις

Αυτόματα και Τυπικές Γραμματικές

  • 1η σειρά (ps) (pdf)
  • 2η σειρά (ps) (pdf)
  • 3η σειρά (ps) (pdf)
  • 4η σειρά (ps) (pdf)
  • 5η σειρά (ps) (pdf)
  • 6η σειρά (ps) (pdf)
  • 7η σειρά (ps) (pdf)
  • 8η σειρά (ps) (pdf)

Μοντέλα υπολογισμού

  • 9η σειρά (pdf)
  • 10η σειρά (pdf)
  • 11η σειρά (pdf)(όχι το GOTO)