Περιγραφή εβδομάδας

  • Χειμερινό Εξάμηνο 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]

          • 12 November - 18 November

            ΔΕΥΤΕΡΑ

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



            ΠΕΜΠΤΗ


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


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

            • 19 November - 25 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, Parallel computation (classes NC, RNC, AC, TC).


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

              • 26 November - 2 December

                ΔΕΥΤΕΡΑ

                • Circuit Lower Bounds: Håstad’s Switching Lemma and applications to lower bounds for parity, oracle worlds and computational learning.



                ΠΕΜΠΤΗ

                • Circuit Lower Bounds: Counting Circuits (ACC) and lower bounds, non-uniform lower bound for NEXP, Natural Proofs.


                Μπορείτε να διαβάσετε:
                - Chapter 14 from [2]

                • 3 December - 9 December

                  ΔΕΥΤΕΡΑ

                  • Hierarchies of Complexity Classes (Survey Talk)



                  ΠΕΜΠΤΗ

                  ΔΕΝ ΕΓΙΝΕ ΜΑΘΗΜΑ.

                  • 10 December - 16 December

                    ΔΕΥΤΕΡΑ

                    • Hierarchies of complexity classes (survey talk cont'd)



                    ΠΕΜΠΤΗ

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


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

                    • 17 December - 23 December

                      ΔΕΥΤΕΡΑ

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



                      ΠΕΜΠΤΗ

                      • Derandomization of Complexity Classes: Pseudorandom Generators, the Nisan-Wigderson Construction, Derandomization vs. Circuit Lower Bounds, The Easy Witness Lemma,
                        Satisfiability vs Circuit Lower Bounds.



                      Μπορείτε να διαβάσετε:
                      -Sections 8.3, 8.4 from [2]
                      - Chapter 20 from [2]

                      • 7 January - 13 January

                        ΔΕΥΤΕΡΑ

                        • Counting Complexity: The class #P and #P-completeness, The class ⊕P, Valiant-Vazirani Theorem.



                        ΠΕΜΠΤΗ

                        • Counting Complexity: Toda’s Theorem.

                        Μπορείτε να διαβάσετε:
                        - Chapter 18 from [1] OR Chapter 17 from [2]


                        • Παρουσιάσεις Φοιτητών