Weekly outline

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

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

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

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

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

  • 30 September - 6 October

    ΠΕΜΠΤΗ

    • Διοικητικά - Διαδικαστικά
    • Problems, Algorithms and Languages. Decision and optimization problems, Representation as strings.
    • Equivalence of Computational Models, Turing Machines.
    Μπορείτε να διαβάσετε:
    -Ch.1,2,3 from [1]

  • 7 October - 13 October

    ΔΕΥΤΕΡΑ

    • Time and Space bounds, multiple strings, linear speedup, nondeterminism.
    • The Universal Turing Machine, Simulation, Diagonalization The Halting Problem, Recursive and Recursive Enumerable Sets, Rice’s Theorem.



    ΠΕΜΠΤΗ

    • 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]

    • 14 October - 20 October

      ΔΕΥΤΕΡΑ

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



      ΠΕΜΠΤΗ

      • Different types of reductions (logspace, Karp, Cook), Circuits.


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

      • 21 October - 27 October

        ΔΕΥΤΕΡΑ

        • P-completeness, NP-completeness, Cook’s Theorem, NP-complete problems, Logical Characterizations.



        ΠΕΜΠΤΗ

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


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

          ΔΕΥΤΕΡΑ

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



          ΠΕΜΠΤΗ

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


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

          • 4 November - 10 November

            ΔΕΥΤΕΡΑ

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



            ΠΕΜΠΤΗ

            • Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice.


            Μπορείτε να διαβάσετε:
            -Sections 7.1, 7.2, 7.3 from [2]

            • This week

              11 November - 17 November

              ΔΕΥΤΕΡΑ

              • Non-Uniform Complexity: Boolean circuits, the class P/poly and related results, Turing Machines with advice, Parallel computation (classes NC, RNC, AC, TC).



              ΠΕΜΠΤΗ




              Μπορείτε να διαβάσετε:
              -Sections 7.4, 7.5 from [2]
              - Sections 6.1 - 6.7 from [2]