Υπολογισιμότητα και Πολυπλοκότητα (ΣΗΜΜΥ)εαρινό εξάμηνο 2018-2019
Διδάσκοντες
Στάθης Ζάχος, Καθηγητής (zachos/a/cs/d/ntua/d/gr )
Πέτρος Ποτίκας, Ε.Δι.Π. (ppotik/a/cs/d/ntua/d/gr )
Διαλέξεις
Παρασκευή 11:45-14:30 , 1.1.29, Παλαιό Κτίριο Ηλεκτρολόγων (ΣΗΜΜΥ, ΣΕΜΦΕ)
Παρασκευή 11:30-14:30 , 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.
Η εξέταση του μαθήματος για την κανονική περιόδο θα πραγματοποιηθεί την Παρασκευή 5/7, στις 12:00, στην αιθ. 1.1.29, του παλ. κτ. ΗΜΜΥ, αντί της προγραμματισμένης εξέτασης. Οι διαφάνειες του μαθήματος ενημερώθηκαν. Στο σύνδεσμο παρακάτω οι παλιές έχουν αντικατασταθεί με τις καινούργιες. Οι αλλαγές αφορούν τυπογραφικά λάθη στην Ενότητα σχήματα McCarthy, το σχήμα της πολυωνυμικής ιεραρχίας και διάγραμμα Hasse αντί Venn στους προσεγγιστικούς αλγόριθμους.
Έναρξη: 22/2/2019
Διαφάνειες Μαθήματος
Διάλεξη 22/2/2019: Ιστορία - Εισαγωγή (History - Intro), Μαθηματικό Υπόβαθρο (Math Foundation)
Διάλεξη 1/3/2019: Κωδικοποίηση (Encodings), LOOP-υπολογίσιμες συναρτήσεις (LOOP-computable functions), Σταθερά Σημεία (Fixpoints), WHILE
Διάλεξη 8/3/2019: Αναδρομικές συναρτήσεις και Σχέσεις, Γλώσσα GOTO, Μηχανές Turing
Διάλεξη 15/3/2019: Σχήματα McCarthy, Στρατηγικές υπολογισμού, Θέση Church-Turing, Κανονική μορφή Kleene, Μη επιλυσιμότητα (Uncomputability)
Διάλεξη 22/3/2019: Θεωρία αναδρομικών συναρτήσεων, Αναδρομικά και αναδρομικά αριθμήσιμα σύνολα, Μαντεία, Σχετική Υπολογισιμότητα, Αριθμητικές Σχέσεις, Διοφαντικά Σύνολα
Διάλεξη 29/3/2019: Aυτόματα και Τυπικές Γραμματικές, Μέρος 1 (11-99)
Διάλεξη 5/4/2019: Aυτόματα και Τυπικές Γραμματικές, Μέρος 2
Διάλεξη 12/4/2019: Aυτόματα και Τυπικές Γραμματικές, Μέρος 3
Διάλεξη 19/4/2019: Κλάσεις πολυπλοκότητας (σελ. 326)
Διάλεξη 10/5/2019: Κλάσεις πολυπλοκότητας, Τυχαιότητα, Μαντεία, Παραλληλία, Διαλογική αλληλεπίδραση
Διάλεξη 17/5/2019: Μετρητικές κλάσεις, προσεγγιστικοί αλγόριθμοι, παραμετρική πολυπλοκότητα
Διάλεξη 24/5/2019: PCP theorem , Πολυπλοκότητα αναζήτησης
Διάλεξη 31/5/2019: Μη-ομοιόμορφα κυκλώματα , Κβαντική πολυπλοκότητα
Όλες οι διαφάνειες Υπολογισιμότητας, Αυτομάτων και Τυπικών Γραμματικών, Πολυπλοκότητας και Προσεγγιστικών αλγορίθμων.
Διαφάνειες για μη-ομοιόμορφα κυκλώματα (ΝΕΟ).
Διαφάνειες για PCP θεώρημα (ΝΕΟ).
Διαφάνειες για Πολυπλοκότητα αναζήτησης.
Διαφάνειες για Παραμετρική Πολυπλοκότητα.
Διαφάνειες για Κβαντική Πολυπλοκότητα.
Σημειώσεις για παραμετρική πολυπλοκότητα.
Σημειώσεις για κβαντική πολυπλοκότητα.
Σημειώσεις για πολυπλοκότητα αναζήτησης.
Σημειώσεις για μη-ομοιόμορφα κυκλώματα (ΝΕΟ).
Ασκήσεις (υπάρχουν και στο βιβλίο)
Μοντέλα υπολογισμού
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 )
Αυτόματα και Τυπικές Γραμματικές
