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

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

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

Γενικά

Διδάσκων

  • Στάθης Ζάχος, Καθηγητής ()

ΕΔΙΠ

  • Πέτρος Ποτίκας ()

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

Διαλέξεις

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

Έναρξη

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

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

  • [1/03/2017] Το εναρκτήριο μάθημα είναι την Παρασκευή 3 Μαρτίου. Η παρουσία σας σε αυτό είναι απαραίτητη.

Υλικό

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

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

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

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

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

  • 1η σειρά (ps) (pdf)
  • 2η σειρά (ps) (pdf)
  • 3η σειρά (ps) (pdf)
  • 4η σειρά (ps) (pdf)
  • 5η σειρά (ps) (pdf)
  • 6η σειρά (ps) (pdf)