Υπολογισιμότητα και Πολυπλοκότητα (ΣΕΜΦΕ, ΣΗΜΜΥ)
Μοντέλα Υπολογισμού και Πολυπλοκότητα(ΑΛΜΑ)
εαρινό εξάμηνο 2017-2018
Διδάσκοντες
- Στάθης Ζάχος, Καθηγητής ()
- Πέτρος Ποτίκας, Ε.Δι.Π. ()
Βοηθός διδασκαλίας
- Αγγελική Χαλκή, Υ.Δ. ()
Διαλέξεις
- Παρασκευή 11:45-14:45, 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων (ΣΗΜΜΥ)
- Παρασκευή 10:45-15:00, 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων (ΣΕΜΦΕ, ΑΛΜΑ)
Έναρξη
Βιβλιογραφία
- D. Sipser. Introduction to the Τheory of Computation.
- J.E. Hopcroft και J.D. Ullman. Introduction to Automata Theory, Languages and Computation.
- H. R. Lewis και C. Papadimitriou. Elements of the Theory of Computation, 2nd edition.
- M. Harrison. Introduction to Switching and Automata Theory. McGraw-Hill Book Company, New York (1965).
- D. C. Kozen. Automata and Computability (Undergraduate Texts in Computer Science).
- Martin D. Davis, Ron Sigal, Elaine J. Wayuker. Computability, Complexity, and Languages, 2nd edition.
- C. Papadimitriou. Computational Complexity.
- S. Arora, B. Barak. Computational Complexity: A modern approach.
- Αποτελέσματα Κανονικής Εξεταστικής 2018:
| Α.Μ. |
Βαθμός |
| 09113087 | 4 |
| 09114008 | 10 |
| 09114018 | 10 |
| 09114167 | 9 |
| 09114189 | 10 |
-
Μετά από συνεννόηση με τους φοιτητές, η ημερομηνία εξέτασης μεταφέρεται από τις 6/7/2018 στις 14/6/2018, 15:00, αιθ. 1.1.29, παλ. κτ. ΗΜΜΥ.
Διαφάνειες Μαθήματος
- Διάλεξη 23/2/2018: Ιστορία - Εισαγωγή (History - Intro), Μαθηματικό Υπόβαθρο (Math Foundation), LOOP
- Διάλεξη 2/3/2018: Κωδικοποίηση (Encodings), LOOP-υπολογίσιμες συναρτήσεις (LOOP-computable functions), Σταθερά Σημεία (Fixpoints), WHILE
- Διάλεξη 9/3/2018: Αναδρομικές συναρτήσεις και Σχέσεις, Γλώσσα GOTO, Μηχανές Turing, Σχήματα McCarthy, Στρατηγικές υπολογισμού
- Διάλεξη 16/3/2018: Θέση Church-Turing, Κανονική μορφή Kleene, Μη επιλυσιμότητα (Uncomputability), Θεωρία αναδρομικών συναρτήσεων
- Διάλεξη 23/3/2018: Αναδρομικά και αναδρομικά αριθμήσιμα σύνολα, Μαντεία, Σχετική Υπολογισιμότητα, Αριθμητικές Σχέσεις, Διοφαντικά Σύνολα
- Διάλεξη 30/3/2018: Aυτόματα και Τυπικές Γραμματικές, Μέρος 1
- Διάλεξη 20/4/2018: Aυτόματα και Τυπικές Γραμματικές, Μέρος 2
- Διάλεξη 27/4/2018: Aυτόματα και Τυπικές Γραμματικές, Μέρος 3
- Διάλεξη 4/5/2018: Κλάσεις πολυπλοκότητας, Τυχαιότητα
- Διάλεξη 11/5/2018: Αυτόματα και Τυπικές Γραμματικές, Τυχαιότητα, Μαντεία, Παραλληλία
- Διάλεξη 18/5/2018: Αυτόματα και Τυπικές Γραμματικές, Τυχαιότητα, Μαντεία, Παραλληλία, Διαλογική αλληλεπίδραση
- Διάλεξη 25/5/2018: Παραμετρική Πολυπλοκότητα
- Διάλεξη 1/6/2018: Μη-ομοιομόρφα κυκλώματα
- Διάλεξη 8/6/2018: Πολυπλοκότητα αναζήτησης, Κβαντική Πολυπλοκότητα
- Όλες οι διαφάνειες Υπολογισιμότητας, Αυτομάτων και Τυπικών Γραμματικών, Πολυπλοκότητας και Προσεγγιστικών αλγορίθμων.
- Διαφάνειες για μη-ομοιόμορφα κυκλώματα.
- Διαφάνειες για Πολυπλοκότητα αναζήτησης.
- Διαφάνειες για Παραμετρική Πολυπλοκότητα.
- Διαφάνειες για Κβαντική Πολυπλοκότητα.
- Σημειώσεις για παραμετρική πολυπλοκότητα.
- Σημειώσεις για κβαντική πολυπλοκότητα.
- Σημειώσεις για πολυπλοκότητα αναζήτησης.
- Σημειώσεις για μη-ομοιόμορφα κυκλώματα.
Ασκήσεις (υπάρχουν και στο βιβλίο)
Μοντέλα υπολογισμού
- 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)
Αυτόματα και Τυπικές Γραμματικές
