Section outline

  • Collapse Expand

    Χειμερινό Εξάμηνο 2015-2016

    Collapse all Expand all

    Προσφέρεται ως "Θεωρητική Πληροφορική Ι: Αλγόριθμοι και Πολυπλοκότητα" στην ΣΗΜΜΥ, και ως "Αλγόριθμοι και Πολυπλοκότητα ΙΙ" στο ΜΠΛΑ.

    Διδάσκοντες:

    Βοηθοί Διδασκαλίας:

    Διαλέξεις:

    • Δευτέρα 17:00-18:30 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)
    • Πέμπτη 15:00-17:00 (Παλιά Κτίρια Ηλεκτρολόγων ΕΜΠ, Αίθουσα 1.1.31)

    Έναρξη: Δευτέρα, 12 Οκτωβρίου 2015

    Ώρες Γραφείου:

    • ΤΒΑ
  • Collapse Expand

    12 October - 18 October

    ΔΕΥΤΕΡΑ

    • Διοικητικά - Διαδικαστικά
    • Introduction to Complexity Theory.
    • Problems, Algorithms and Languages. Decision and optimization problems.
    • Turing machines with multiple strings, linear speedup, nondeterminism.
    • Equivalence of Computational Models, Turing Machines, Representation as strings.
    • Computability & Undecidability: The Universal Turing Machine, Simulation, Diagonalization

    ΠΕΜΠΤΗ

    • The Halting Problem, Recursive and Rec. Enumerable sets, Rice's Theorem
    • Complexity Classes: Complexity Measures, Time and Space Classes, Hierarchy Theorems, Gap Theorem.

    Προτεινόμενη Μελέτη:
    -Ch.1,2 από το [1]
    -Ch.3: p. 57-63 από τo [1]
    -Ch. 7: p.139-146 από το [1]
    - Ch.1 από το [2]

  • Collapse Expand

    19 October - 25 October

    ΔΕΥΤΕΡΑ

    • Space Computation: The classes L and NL, Savitch's Theorem, NL-completeness

    ΠΕΜΠΤΗ

    • Space Computation: Immerman-Szelepscényi Theorem

    Προτεινόμενη Μελέτη:
    - Ch.7:  p. 146-153 από το [1]
    -Ch.4 από το [2]

  • Collapse Expand

    26 October - 1 November

    ΔΕΥΤΕΡΑ

    • Reductions & NP-Completeness: Different types of reductions and relations among them, NP-completeness

    ΠΕΜΠΤΗ

    • Oracles & Optimization Problems (1/2), Relativizations.

    Προτεινόμενη Μελέτη:
    -Ch.8,9 από το [1]
    -Ch. 14: Section 14.3 από το [1]
    - Ch. 17: Section 17.1 από το [1]
    - Ch.3: Section 3.4 από το [2]

  • Collapse Expand

    2 November - 8 November

    ΔΕΥΤΕΡΑ

    • Oracles & Optimization Problems (2/2), The Limits of Diagonalization

    ΠΕΜΠΤΗ

    • The Polynomial Hierarchy (1/2)

    Προτεινόμενη Μελέτη:
    -Ch.17: Section 17.2 από το [1]

  • Collapse Expand

    9 November - 15 November

    ΔΕΥΤΕΡΑ

    • The Polynomial Hierarchy (2/2)

    ΠΕΜΠΤΗ

    Δεν έγινε μάθημα

  • Collapse Expand

    16 November - 22 November

    ΔΕΥΤΕΡΑ

    Δεν έγινε μάθημα

    ΠΕΜΠΤΗ

    • Randomized Computation: The classes BPP, RP, coRP

    Προτεινόμενη Μελέτη:

    • Ch 7: Sections 7.1,7.2 από το [2]
    • Section 1 από εδώ.

  • Collapse Expand

    23 November - 29 November

    ΔΕΥΤΕΡΑ

    • Randomized Computation: The classes ZPP, RP, coRP, and relations among them, Quantifier Notation ane related results, The BPP-Theorem, the "P vs BPP Question".

     

    ΠΕΜΠΤΗ

    • Randomized Computation: Syntactic and semantic classes, Error Reduction, The Class PP, Relativized Results.

    Προτεινόμενη Μελέτη:

    • Ch 7: Sections 7.1,7.2 από το [2]
    • Section 1 από εδώ.
  • Collapse Expand

    30 November - 6 December

    ΔΕΥΤΕΡΑ

    • Non-Uniform Complexity: Boolean Circuits, the class P/poly, Advice Turing Machines, Circuit Lower Bounds, Natural Proofs, Advice Turing Machines, Circuit Lower Bounds, Natural Proofs

     

    ΠΕΜΠΤΗ

    • Interactive Proofs: Deterministic verifiers, probabilistic verifiers and the class IP, Public and private coins, Arthur-Merlin Games

     

    Προτεινόμενη Μελέτη:

    • Ch 6: Sections 6.1-6.5 από το [2]
  • Collapse Expand

    7 December - 13 December

    ΔΕΥΤΕΡΑ

    • Interactive Proofs: The Class AM, Quantifier Notation, Perfect Completeness for AM, Collapsion of AM[k] hierarchy to AM=AM[2], Relativized results

     

    ΠΕΜΠΤΗ

    • Interactive Proofs: Shamir's Theorem (IP=PSPACE)

     

  • Collapse Expand

    14 December - 20 December

    ΔΕΥΤΕΡΑ

    • Interactive Proofs: Shamir's Theorem (IP=PSPACE) (cont'd), Probabilistically Checkable Proofs, The Class PCP[r(n),q(n)].

     

    ΠΕΜΠΤΗ

    • Interactive Proofs: The PCP Theorem ( NP=PCP[logn,1] ), Dinur's Proof (guest lecture by M. Zampetakis)

     

  • Collapse Expand

    21 December - 27 December

    ΔΕΥΤΕΡΑ

    • 1o Quiz
  • Collapse Expand

    4 January - 10 January

    ΠΕΜΠΤΗ

    • Counting Complexity: Counting vs Decision Problems, the class #P
  • Collapse Expand

    11 January - 17 January

    ΔΕΥΤΕΡΑ

    Δεν έγινε μάθημα, οι φοιτητές προσκλήθηκαν στην ημερίδα AtheCrypt 2016

    ΠΕΜΠΤΗ

    • Counting Complexity: Counting Problems, #SAT, PERMANENT, Parsimonious, Cook and Cook[1] (metric) reductions for Counting Problems, Valiant-Vazirani Theorem, Quantifiers vs Counting: Toda's Theorem.
  • Collapse Expand

    18 January - 24 January

    ΔΕΥΤΕΡΑ

    • Uniform and Non-Uniform Derandomization of Complexity Classes (guest lecture by A. Antonopoulos)

    ΠΕΜΠΤΗ (21/1)

    Δεν θα γίνει μάθημα

  • Collapse Expand

    25 January - 31 January

    ΔΕΥΤΕΡΑ (25/1)

    • Ομιλίες Φοιτητών: 
      -- Ορέστης Παπαδιγενόπουλος
      -- Δημήτρης Καλημέρης

    ΠΕΜΠΤΗ (28/1)

    • Ομιλίες Φοιτητών: 
      -- Σταύρος Πετσαλάκης
      -- Κυριάκος Αξιώτης
  • Collapse Expand

    1 February - 7 February

    ΔΕΥΤΕΡΑ (1/2)

    • Ομιλίες Φοιτητών: 
      -- Βασίλης Παπαϊωάννου
      -- Μάκης Αρσένης