Section outline

  • ΔΕΥΤΕΡΑ

    • Διοικητικά - Διαδικαστικά
    • 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]