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

εαρινό εξάμηνο 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).
  7. C. Papadimitriou. Computational Complexity.
  8. S. Arora, B. Barak. Computational Complexity: A modern approach.
  9. E. Grädel, W. Thomas, Th. Wilke. Automata, Logics and Infinite Games.

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

  • Αποτελέσματα Επαναληπτικής Εξεταστικής 2018
    Α.Μ. Βαθμός
    09115012 3
    09115057 3
    09115112 2
    09115703 1
    09115706 1
  • H επαναληπτική εξέταση του μαθήματος θα γίνει την Τετάρτη 12/9/2018 στις 15:00, στην αίθ. 1.1.29, στο παλαιό κτ. Ηλεκτρολόγων.
  • Διεθνές Συνέδριο Ελλήνων Μαθηματικών
  • >Την Τετάρτη 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: Προγράμματα LOOP, Πρωταρχική αναδρομή
  • Διάλεξη 18/4/2018: Προγράμματα WHILE, Μερικές αναδρομικές συναρτήσεις
  • Διάλεξη 20/4/2018: Μηχανές Turing και άλλα υπολογιστικά μοντέλα
  • Διάλεξη 25/4/2018: Ιδιότητες r.e. γλωσσών, Αποκρισιμότητα, Ιεραρχία Chomsky, Κλάσεις Πολυπλοκότητας
  • Διάλεξη 27/4/2018: Θεωρήματα ιεραρχίας, Αναγωγές, Μοντέλα δέντρων υπολογισμού για ΤΜ, Τυχαιότητα
  • Διάλεξη 2/5/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)

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

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