ΘΕΩΡΗΤΙΚΗ ΠΛΗΡΟΦΟΡΙΚΗ Ι (ΣΗΜΜΥ)
ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ (ΑΛΜΑ)
ΕΞΕΤΑΣΤΕΑ ΥΛΗ ΜΑΘΗΜΑΤΟΣ
2018-2019
- Από το βιβλίο του Παπαδημητρίου [1]:
- Κεφ. 1 "Problems and Algorithms"
- Κεφ. 2 "Turing Machines": (όχι το section 2.6)
- Κεφ. 3 "Computability": (όχι η παράγραφος "Recursive Inseparability", σελ. 63-64)
- Κεφ. 7 "Relations between CCs"
- Κεφ. 8 "Reductions and Completeness": (όχι το θ. 8.3 [Fagin])
- Κεφ. 14 "On P vs. NP": όχι το section 14.4
- Κεφ. 16 "Logarithmic Space": μόνο το 16.1
- Κεφ. 17: "The Polynomial Hierarchy": 17.2 (χωρίς τις αποδείξεις των θ. 17.12 και 17.13)
- Κεφ. 18 "Computation that counts": (χωρίς τις αποδείξεις του θ. Valiant (18.3)) *
(*μπορείτε να δείτε και την αντίστοιχη ύλη από το κεφ. 17 του Arora-Barak, αν το προτιμάτε)
- Από το βιβλίο των Arora-Barak [2]:
- Κεφ. 6 "Boolean Circuits": όχι τo section 6.8.
- Κεφ. 7 "Randomized Computation" : μόνο τα 7.1, 7.3, 7.4, 7.5 (όχι την απόδειξη του θ. 715 [Sipser-Gacs])
- Κεφ. 8 "Interactive Proofs": όχι τα 8.2.2, 8.2.3, 8.3.2, 8.3.3, 8.6, 8.7
- Κεφ. 14 "Circuit Lower Bounds": μόνο τα 14.1, 14.2, 14.3, 14.4 (χωρίς τις αποδείξεις των θεωρημάτων)
- Οι διαφάνειες του μαθήματος
- Οι σημειώσεις "Quantifier Characterizations of Complexity Classes" (βρίσκονται εδώ)