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

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

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

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

Γενικά

Διδάσκοντες

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

Διαλέξεις

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

Έναρξη

  • 28/2/2020.

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

  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.

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

  • Το link για το αυριανό μάθημα και για τις ημέρες που έχουμε μάθημα είναι το παρακάτω και θα συνδεόμαστε την ώρα του μαθήματος. Αύριο θα αρχίσουμε από τη διαφάνεια 113 (μεταπτυχιακοί) και 81 (προπτυχιακοί). Θα πρέπει να έχετε μελετήσει τις προηγούμενες διαφάνειες. Επίσης, σας παροτρύνουμε να ασχοληθείτε με τις ασκήσεις που υπάρχουν στη σελίδα του μαθήματος. Σύντομα θα δοθούν οδηγίες για την υποβολή τους.
    https://meetingsemea.webex.com/meet/ppotik
  • Λαμβάνοντας υπόψη τη νέα κατάσταση, που ελπίζουμε να μην διαρκέσει πάρα πολύ, θα προσπαθήσουμε να συνεχίσουμε τα μαθήματα διαδικτυακά. Θα λάβετε νέα ανακοίνωση σύντομα για την πλατφόρμα που θα χρησιμοποιήσουμε και οδηγίες για το μάθημα της Παρασκευής 20/3 που θα γίνει ώρα 11:30πμ-14:30μμ.
  • Έναρξη: 28/2/2020

Υλικό

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

Ασκήσεις

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

  • 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)