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

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

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

Γενικά

Διδάσκοντες

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

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

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

Διαλέξεις

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

Έναρξη

  • 3/3/2017.

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

  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 Yor k (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.

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

  • Η εξέταση του μαθήματος θα γίνει στις 7/7/2017, στις 12:00, αιθ. 1.1.29, παλ. κτ. ΗΜΜΥ
  • [1/03/2017]Το εναρκτήριο μάθημα είναι την Παρασκευή 3 Μαρτίου. Η παρουσία σας σε αυτό είναι απαραίτητη.
  • Αποτελέσματα Επαναληπτικής Εξεταστικής 2017:
    Α.Μ. Βαθμός
    Α00108
    091110429
    091130599
    031111388
    031124050
  • Αποτελέσματα Κανονικής Εξεταστικής 2017:
    Α.Μ. Βαθμός
    Α00034
    Α00079
    Α00106
    091110421
    091130209
    091130593
    031107396
    031130097
    0311302810
    031131107
    031131489

Υλικό

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

Τα παρακάτω έγγραφα είναι σε μορφή PostScript, εκτυπώσιμα από τους περισσότερους laser εκτυπωτές. Μπορείτε να τα τυπώσετε σε οποιονδήποτε εκτυπωτή, καθώς και να τα δείτε στην οθόνη του υπολογιστή σας, χρησιμοποιώντας λογισμικό που βρίσκεται στο http://www.cs.wisc.edu/~ghost/ (οι χρήστες Windows χρειάζονται το GSView και το ghostscript από τον παραπάνω δικτυακό τόπο). Επίσης, τα έγγραφα δίνονται και σε μορφή .pdf, αλλά ο Acrobat Reader δεν τα παρουσιάζει τόσο καλά.

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

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

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

Αυτόματα και Τυπικές Γραμματικές

  • 10η σειρά (ps) (pdf) Παράδοση 2/6/2017
  • 11η σειρά (ps) (pdf) Παράδοση 2/6/2017
  • 12η σειρά (ps) (pdf) Παράδοση 2/6/2017
  • 13η σειρά (ps) (pdf) Παράδοση 9/6/2017
  • 14η σειρά (ps) (pdf) Παράδοση 9/6/2017

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

Τελευταία ανανέωση: 20 Ιουνίου 2017