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

εαρινό εξάμηνο 2020-2021

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

Δείτε τη νέα σελίδα, όπου υποβάλετε ασκήσεις

Γενικά

Νέα σελίδα

Διδάσκοντες

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

Διαλέξεις

  • Παρασκευή 11:45-14:30 (ΗΜΜΥ, ΕΜΦΕ)
  • Παρασκευή 10:00-14:30 (ΑΛΜΑ, ΕΜΕ)

Έναρξη

  • 26/2/2021.

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

  1. Σ. Ζάχος. Σημειώσεις μαθήματος.
  2. D. Sipser. Introduction to the Τheory of Computation.
  3. J.E. Hopcroft και J.D. Ullman. Introduction to Automata Theory, Languages and Computation.
  4. H. R. Lewis και C. Papadimitriou. Elements of the Theory of Computation, 2nd edition.
  5. M. Harrison. Introduction to Switching and Automata Theory. McGraw-Hill Book Company, New York (1965).
  6. D. C. Kozen. Automata and Computability (Undergraduate Texts in Computer Science).
  7. Martin D. Davis, Ron Sigal, Elaine J. Wayuker. Computability, Complexity, and Languages, 2nd edition.
  8. C. Papadimitriou. Computational Complexity.
  9. S. Arora, B. Barak. Computational Complexity: A modern approach.

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

  • Η έναρξη του μαθήματος είναι την Παρασκευή 26/2, στις 10:00 για τους φοιτητές του ΑΛΜΑ, ΕΜΕ και 11:45 για τους φοιτητές της ΗΜΜΥ και ΕΜΦΕ.
    Meeting link:
    https://centralntua.webex.com/centralntua/j.php?MTID=m0e1e5b478d58b5343f9688b5fd273b2b
    Meeting number:121 081 8607
    Password:turing@xxxx_21 (όπου xxxx το ακρωνύμιο του ΕΜΠ στα αγγλικά, όλα πεζά)
    Καλή αρχή!

Υλικό

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

Ασκήσεις

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

  • 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)
  • 9'η Σειρά (pdf)

Αυτόματα, Γλώσσες και Τυπικές Γραμματικές

  • 10η σειρά (ps) (pdf)
  • 11η σειρά (ps) (pdf)
  • 12η σειρά (ps) (pdf)
  • 13η σειρά (ps) (pdf)
  • 14η σειρά (ps) (pdf)

Πολυπλοκότητα

  • 15η σειρά (pdf)

Τελευταία ανανέωση: 23/2/2021