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

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

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

Γενικά

Διδάσκοντες

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

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

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

Διαλέξεις

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

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

  1. Σ. Ζάχος, Α. Παγουρτζής, Τα Θεμέλια της Πληροφορικής, εκδόσεις Τσότρας, 2014
  2. Μ. Sipser. Introduction to the Theory of Computation.
  3. J.E. Hopcroft and J.D. Ullman. Introduction to Automata Theory, Languages and Computation.
  4. H. R. Lewis and C. Papadimitriou. Elements of the Theory of Computation, 2nd edition.
  5. D. C. Kozen. Automata and Computability (Undergraduate Texts in Computer Science).
  6. M. Harrison. Introduction to Switching and Automata Theory. McGraw-Hill Book Company, New York (1965).

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

  • Διεθνές Συνέδριο Ελλήνων Μαθηματικών
  • Την Τετάρτη 28/3/18 το μάθημα θα πραγματοποιηθεί 13:00-15:00, αντί για 15:00-17:00.
  • Αλλαγή ώρας την Παρασκευή: 15:30-17:30 αντί 15:00-17:00.
  • Αλλαγή ώρας την Τετάρτη: 15:00-17:00 αντί 17:00-19:00.
  • Το πρώτο μάθημα θα γίνει την Τετάρτη, 21/2/18, και θα αρχίσει στις 17:00.

Υλικό

Διαλέξεις

  • Διάλεξη 21/2/2018: Αυτόματα και Τυπικές Γραμματικές: Εισαγωγή, DFA/NFA, κανονικές παραστάσεις
  • Διάλεξη 23/2/2018: Αυτόματα και Τυπικές Γραμματικές: pumping lemma, γραμματικές χωρίς συμφραζόμενα, συντακτικά δέντρα, PDA, γενικές γραμματικές, μηχανές Turing, γραμματικές με συμφραζόμενα, LBA
  • Διάλεξη 28/2/2018: Αυτόματα και Τυπικές Γραμματικές: παραλλαγές και επεκτάσεις, FA με έξοδο
  • Διάλεξη 2/3/2018: Αυτόματα και Τυπικές Γραμματικές: ισοδυναμία μηχανών Mealy και Moore, pumping lemma για κανονικά σύνολα, ιδιότητες κλειστότητας για κανονικά σύνολα, αλγόριθμοι απόφασης για κανονικά σύνολα
  • Διάλεξη 7/3/2018: Αυτόματα και Τυπικές Γραμματικές: αλγεβρική περιγραφή κανονικών συνόλων, ελαχιστοποίηση DFA, τυπικές γραμματικές, ιεραρχία Chomsky, κανονικές γραμματικές
  • Διάλεξη 14/3/2018: Αυτόματα και Τυπικές Γραμματικές: κανονικές γραμματικές, κανονική μορφή Chomsky, κανονική μορφή Greibach
  • Διάλεξη 16/3/2018: Αυτόματα και Τυπικές Γραμματικές: αυτόματα στοίβας
  • Διάλεξη 21/3/2018: Αυτόματα και Τυπικές Γραμματικές: αυτόματα στοίβας
  • Διάλεξη 23/3/2018: Αυτόματα και Τυπικές Γραμματικές: ιδιότητες c.f. γλωσσών
  • Διάλεξη 28/3/2018: Μοντέλα Υπολογισμού
  • Διάλεξη 30/3/2018: Μοντέλα Υπολογισμού
  • Διάλεξη 18/4/2018: Μοντέλα Υπολογισμού

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

Ασκήσεις

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