Advanced topics in theoretical computer science

Slides

  • 27.10.2021:
  • 3.11.2021: Turing Machines and Computability (Part 1) [recap-tm.pdf]
  • 10.11.2021: Turing Machines and Computability (Part 2) [recap-tm2.pdf] ( Updated version: 16.11.2021 )
  • 10.11.2021: Register Machines (Part 1) [register-machines1.pdf]

  • 17.11.2021: Register Machines (Part 2) [register-machines2.pdf]
  • Slides about structural induction: [structural-induction.pdf]

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

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

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

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

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

  • 05.01.2022: Computability and (Un-)Decidability, Part I [computability1.pdf]
  • 12.01.2022 and 19.01.2022 Computability and (Un-)Decidability, Part II [computability2.pdf]
  • 19.01.2022: Complexity, Part I [complexity1.pdf]
  • 26.01.2022: Complexity, Part II [complexity2.pdf] (Online: 26.01.2022)

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

  • 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)
    • Other direction in complexity theory
  • Other models for computability [other-models-of-computability.pdf] (Online: 2.02.2022)

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

  • 9.02.2022: Overview: List of topics [summary.pdf]
  • Audio-Commented Slides (Online: 9.02.2022)