Theoretical Computer Science

Course Description: document (german)

• Lesson 1: Infinity
  • Set Theory
  • Natural Numbers
  • Countability
  • Uncountability
• Lesson 2: Functions
  • Finitary Relations
  • Total Functions
  • Partial Functions
  • Characteristic Function
  • Power Sets
  • Decidability
• Lesson 3: Computability
  • Integer-Valued Function
  • Word-Valued Function
  • Numbering
  • Computability
• Lesson 4: Logic Programming
  • First-order Logic
    • Predicates
  • Logic Programming
  • Prolog
• Lesson 5: Formal Languages
  • Formal Languages
  • Formal Grammars
  • Chomsky Hierarchy
  • Deciding Problems
  • Regular Expressions
• Lesson 6: Functional Programming
  • Lambda Calculus
  • Functional Programming
    • Anonymous Functions
    • Functions as First-Class Citizens
    • Eager and Lazy Evaluation
    • Type Inference
  • Haskell
• Lesson 7: Models of Computation
  • Turing Machines
  • Lambda Calculus
  • Register Machines
  • GOTO-Programs
  • WHILE-Programs
  • LOOP-Programs
  • Recursive functions
  • Proof by Reduction
  • Church–Turing Thesis
• Lesson 8: Computational Complexity
  • Computational Complexity
    • Time Complexity
    • Space Complexity
    • Complexity classes
  • Big O Notation
  • Algorithm Engineering
  • P versus NP Problem