Algorithmics II

Some topics:

  • Fast Fourier transformation
  • Randomized algorithms
  • Parallel algorithms
  • Streaming algorithms

Advanced Logic

The lecture continues the course Computability and Logic (B.Sc. Computer Science). Topics are:

  • Undecidability in predicate logic
  • The theorems of Church and Trakhtenbrot
  • Undecidability of arithmetics and Gödel's theorem
  • Automatic Structures
  • Monadic second order logic and regular languages (Büchi's theorem)
  • Existential second-order logic (Fagin's theorem)

Formale Sprachen und Automaten

Die Vorlesung ist eine Einführung in die Theorie der Automaten und formalen Sprachen. Wichtige Inhalte der Vorlesun sind:

Endliche Automaten und reguläre Sprachen

  • Formale Sprachen und Grammatiken, Chomsky-Hierarchie,
  • Endliche Automaten (deterministische und nichtdeterministe endliche Automaten, deren Äquivalenz, Minimierung),
  • Reguläre Sprachen (regulärer Ausdrücke, Äquivalenz zu endlichen Automaten, Scanner-Generatoren),
  • Eigenschaften regulärer Sprachen (Abschlusseigenschaften, Pumping-Lemma) Kontextfreie Sprachen

Kontextfreie Grammatiken und ihre Normalformen

  • Eigenschaften kontextfreier Sprachen (Pumping-Lemma, Abschlusseigenschaften, CYK-Algorithmus),
  • Kellerautomaten (nichtdeterministische Kellerautomaten und deren Äquivalenz zu kontextfreien Grammatiken, deterministische Kellerautomaten), Anwendungen im Compilerbau (syntaktische Analyse)

Turingmaschinen und linear beschränkte Automaten

Quantum Complexity Theory

The lecture gives an introduction into quantum complexity theory. Some topics are:

  • Introduction into quantum computing
  • Bounded error quantum polynomial time (BQP)
  • BQP-complete problems
  • Quantum Merlin Arthur (QMA)
  • The quantum Cook-Levin theorem
  • quantum interactive protocols

Cutting Edge Research