Υπολογισιμότητα και Πολυπλοκότητα (ΣΕΜΦΕ, ΣΗΜΜΥ)
Μοντέλα Υπολογισμού και Πολυπλοκότητα(ΑΛΜΑ)

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

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

Γενικά

Διδάσκοντες

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

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

  • Αγγελική Χαλκή, Υ.Δ. ()

Διαλέξεις

  • Παρασκευή 11:45-14:45, 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων (ΣΗΜΜΥ)
  • Παρασκευή 10:45-15:00, 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων (ΣΕΜΦΕ, ΑΛΜΑ)

Έναρξη

  • 23/2/2018.

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

  1. D. Sipser. Introduction to the Τheory of Computation.
  2. J.E. Hopcroft και J.D. Ullman. Introduction to Automata Theory, Languages and Computation.
  3. H. R. Lewis και C. Papadimitriou. Elements of the Theory of Computation, 2nd edition.
  4. M. Harrison. Introduction to Switching and Automata Theory. McGraw-Hill Book Company, New York (1965).
  5. D. C. Kozen. Automata and Computability (Undergraduate Texts in Computer Science).
  6. Martin D. Davis, Ron Sigal, Elaine J. Wayuker. Computability, Complexity, and Languages, 2nd edition.

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

Υλικό

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

Ασκήσεις (υπάρχουν και στο βιβλίο)

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

  • 1η Σειρά Προκαταρκτικά (ps) (pdf)
  • 2η Σειρά LOOP (ps) (pdf)
  • 3η Σειρά Κωδικοποίηση (ps) (pdf)
  • 4η Σειρά Πρωταρχικές αναδρομικές συναρτήσεις (ps) (pdf)
  • 5η Σειρά Σχήματα McCarthy - Στρατηγικές (ps) (pdf)
  • 6η Σειρά GOTO - Μηχανές Turing (ps) (pdf)
  • 7η Σειρά Καθολικότητα - Αναδρομικότητα (ps) (pdf)
  • 8η Σειρά Αναδρομικά αριθμήσιμα σύνολα (ps) (pdf)
  • 9η Σειρά Μαντεία - Αριθμητικά κατηγορήματα (ps) (pdf)