Εξεταστέα ύλη μαθήματος (για το τελικό διαγώνισμα)

 
Picture of Αντώνης Αντωνόπουλος
Εξεταστέα ύλη μαθήματος (για το τελικό διαγώνισμα)
by Αντώνης Αντωνόπουλος - Monday, 17 January 2022, 8:18 PM
 

ΘΕΩΡΗΤΙΚΗ ΠΛΗΡΟΦΟΡΙΚΗ Ι (ΣΗΜΜΥ)
ΥΠΟΛΟΓΙΣΤΙΚΗ ΠΟΛΥΠΛΟΚΟΤΗΤΑ (ΑΛΜΑ)

ΕΞΕΤΑΣΤΕΑ ΥΛΗ ΜΑΘΗΜΑΤΟΣ
2021-2022

Η/Μ Κανονικής εξέτασης: 28/2/2022 στις 15:00

- Από το βιβλίο του Παπαδημητρίου [1]:

  • Κεφ. 14 "On P vs. NP": όχι το section 14.4
  • Κεφ. 17: "The Polynomial Hierarchy": 17.1 (χωρίς τις αποδείξεις-αναγωγές), 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
  • Κεφ. 11 "PCP Theorems and hardness of approximation": 11.1,11.2,11.3
  • Κεφ. 14 "Circuit Lower Bounds": μόνο τα 14.1, 14.2, 14.3 (χωρίς τις αποδείξεις των θεωρημάτων), 14.4
  • Κεφ. 20 "Derandomization": 20.1, 20.2 (χωρίς τις αποδείξεις των θεωρημάτων), 20.3 (χωρίς τις αποδείξεις των θεωρημάτων), 20.4 (χωρίς τις αποδείξεις των θεωρημάτων)
  • Κεφ. 23 "Why is clbs so difficult": 23.1, 23.2

- Από τις διαφάνειες του μαθήματος, οι ενότητες:

  • Oracles & The Polynomial Hierarchy
  • The structure of NP
  • Randomized Computation
  • Non-Uniform Complexity
  • Interactive Proofs
  • Derandomization of Complexity Classes
  • Counting Complexity

- Οι σημειώσεις "Quantifier Characterizations of Complexity Classes" (βρίσκονται εδώ)