Υπολογιστική Πολυπλοκότητα
Weekly outline
- General
General
Χειμερινό Εξάμηνο 2017-2018
Προσφέρεται ως "Θεωρητική Πληροφορική Ι: Αλγόριθμοι και Πολυπλοκότητα" στην ΣΗΜΜΥ.
Διδάσκοντες:
- Στάθης Ζάχος, Καθηγητής (zachos@cs.ntua.gr)
- Άρης Παγουρτζής, Αναπλ. Καθηγητής (pagour@cs.ntua.gr)
Βοηθοί Διδασκαλίας:
- Αντώνης Αντωνόπουλος, Υ/Δ (aanton@corelab.ntua.gr)
- Αγγελική Χαλκή, Υ/Δ (achalki@corelab.ntua.gr)
Διαλέξεις:
- Δευτέρα 17:00-20:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
- Πέμπτη 15:00-17:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
- 9 October - 15 October
9 October - 15 October
ΔΕΥΤΕΡΑ
- Διοικητικά - Διαδικαστικά
- Hierarchies of Complexity Classes (Course overview)
- Introduction to Complexity Theory.
- Problems, Algorithms and Languages. Decision and optimization problems.
ΠΕΜΠΤΗ
- Introduction to Turing Machines.
- Turing machines with multiple strings, linear speedup, nondeterminism.
- Equivalence of Computational Models, Turing Machines, Representation as string
You can study:
-Ch.1,2 from [1] - 16 October - 22 October
16 October - 22 October
ΔΕΥΤΕΡΑ
- Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization
You can study:
-Ch.3: p. 57-63 from [1]ΠΕΜΠΤΗ
- Complexity Classes: Complexity Measures, Time and Space Classes, Hierarchy Theorems, Gap Theorem.
- 23 October - 29 October
23 October - 29 October
ΔΕΥΤΕΡΑ
- Complexity Classes: Complexity measures, time and space classes
ΠΕΜΠΤΗ
- Space Computation:The classes L and NL, Savitch’s Theorem
- 30 October - 5 November
30 October - 5 November
ΔΕΥΤΕΡΑ
- Space Computation: Immerman-Szelepscényi Theorem, Reingold’s Theorem: L = SL &
Undirected REACHABILITY
ΠΕΜΠΤΗ
- Reductions & Completeness: Different types of reductions (logspace, Karp, Cook), Circuits,
P-completeness.
- Space Computation: Immerman-Szelepscényi Theorem, Reingold’s Theorem: L = SL &