Advanced topics in theoretical computer science

Slides

  • 26.10.2022:
  • 2.11.2022: Turing Machines and Computability (Part 1) [recap-tm.pdf]
  • 9.11.2022: Turing Machines and Computability (Part 2) [recap-tm2.pdf]
  • 9.11.2022: Register Machines (Part 1) [register-machines1.pdf]

  • Slides about structural induction: [structural-induction.pdf]

  • 16.11.2022: Register Machines (Part 2) [register-machines2.pdf]

  • 23.11.2022: Register Machines (Part 3) [register-machines3.pdf]
  • 23.11.2022: Register Machines: Wrapping up [register-machines-recap.pdf]

  • 30.11.2022: Recursive functions (Part 1) [recursive-functions1.pdf]

  • 7.12.2022: Recursive functions (Part 2) [recursive-functions2.pdf]

  • 14.12.2022: Recursive functions (Part 3) [recursive-functions3.pdf]
  • Examples simultaneous recursion [pdf]

  • 21.12.2022: Recursive functions (Part 4) [recursive-functions4.pdf]

  • 04.01.2023: Computability and (Un-)Decidability, Part I [computability1.pdf]
  • 11.01.2023 and 18.01.2023 Computability and (Un-)Decidability, Part II [computability2.pdf]
  • 18.01.2023: Complexity, Part I [complexity1.pdf]
  • 25.01.2023 and 1.02.2023: Complexity, Part II [complexity2.pdf] (Online: 25.01.2023)

  • Important for the exam: pages 1-69
  • Audio-Commented Slides for this part (Online: 25.01.2023)

  • Additional information, not important for the exam
  • Proofs NP-completeness colorability (external links)
  • Coloring is NP-complete: Proof [coloring-np-complete-proof.pdf]
  • 3-colorability is NP-complete: Proof [External Link]

    • Not important for the exam

  • 2.02.2022: Additional informations: complexity, computability
  • Complexity, Part III [complexity3.pdf]
    • The structure of PSPACE (some explanations): complexity2.pdf, pages 70-87
    • Other direction in complexity theory: complexity2.pdf, pages 88-96
  • Other models for computability [other-models-of-computability.pdf] (Online: 25.01.2023)

  • Audio-Commented Slides for this part (Complexity: Parts 1 and 2; Computability: Part 3)
    (Online: 25.01.2023)

  • Overview: List of topics [summary.pdf]