Weekly outline

  • Χειμερινό Εξάμηνο 2018-2019

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

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

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

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

  • 8 October - 14 October

    ΔΕΥΤΕΡΑ

    • Διοικητικά - Διαδικαστικά
    • Problems, Algorithms and Languages. Decision and optimization problems.
    • Equivalence of Computational Models, Turing Machines.


    ΠΕΜΠΤΗ

    • Time and Space bounds, multiple strings, linear speedup, nondeterminism.
    • Equivalence of Computational Models, Turing Machines, Representation as string
    • The Universal Turing Machine, Simulation, Diagonalization The Halting Problem, Recursive and Recursive Enumerable Sets, Rice’s Theorem.

    Μπορείτε να διαβάσετε:
    -Ch.1,2,3 from [1]

  • 15 October - 21 October

    ΔΕΥΤΕΡΑ

    • Complexity Classes: Complexity Measures, Time and Space Classes, Hierarchy Theorems, Gap Theorem, Succinct Certificates.



    ΠΕΜΠΤΗ

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


    Μπορείτε να διαβάσετε:
    -Ch.7 from [1]

    • 22 October - 28 October

      ΔΕΥΤΕΡΑ

      • Space Computation: Immerman-Szelepscényi Theorem, Reingold’s Theorem: L = SL & Undirected REACHABILITY.



      ΠΕΜΠΤΗ

      • Different types of reductions (logspace, Karp, Cook), Circuits, P-completeness. NP-completeness, Cook’s Theorem, NP-complete problems, Logical Characterizations.


      Μπορείτε να διαβάσετε:
      -Ch.8 from [1]

      • 29 October - 4 November

        ΔΕΥΤΕΡΑ

        • Oracles & The Polynomial Hierarchy: Oracles and oracle classes. Oracle worlds.



        ΠΕΜΠΤΗ

        • Oracles & The Polynomial Hierarchy: The polynomial-time hierarchy and related theorems.


        Μπορείτε να διαβάσετε:
        -Section 14.3, Ch.17 from [1]
        • 5 November - 11 November

          ΔΕΥΤΕΡΑ

          • The Structure of NP: Ladner’s Theorem, padding.



          ΠΕΜΠΤΗ

          • The Structure of NP: NP-isomorphism, The “Berman-Hartmanis” conjecture, density, sparse sets.


          Μπορείτε να διαβάσετε:
          -Sections 14.1, 14.2 from [1]

          • This week

            12 November - 18 November

            ΔΕΥΤΕΡΑ

            • Randomized Computation: Randomized Algorithms,  BPP, RP, coRP, ZPP.



            ΠΕΜΠΤΗ

            • Randomized Computation: Quantifier notation and related results, semantic and syntactic classes, the “P vs BPP” question.