zum Inhalt springen

Theoretische Informatik

"Nichts ist praktischer als eine gute Theorie." (Tódor Kármán)

Zwar sind im Gegensatz zu anderen Zweigen der Informatik die Anwendungen der Ergebnisse der Theoretischen Informatik nicht immer direkt zu sehen, aber dennoch sind sie von großer Bedeutung. Können wir zum Beispiel beweisen, dass es bestimmte für die Praxis wünschenswerte Werkzeuge oder Algorithmen nicht geben kann, so kann die hoffnungslose Arbeit an diesen Werkzeugen oder Algorithmen eingestellt werden und stattdessen die Suche nach bestmöglichen Auswegen begonnen werden. Umgekehrt sind positive Resultate, e. g. Existenzaussagen oder Algorithmen mit exponentieller Laufzeit, nicht automatisch anwendungsorientiert.

Die Vorlesung beinhaltet eine Einführung in die zentralen Gebiete der Theoretischen Informatik. Neben den klassischen Gebieten (z.B. Formale Sprachen, Automatentheorie, Berechenbarkeit und Komplexität) werden auch modernere Gebiete (z.B. approximierende Algorithmen, randomisierte Algorithmen, Algorithmik hartnäckiger Probleme) behandelt. Die Vorlesung folgt nicht dem klassischen "Definition-Satz-Beweis"-Stil und versucht diese Thematik aus algorithmenorientierter Sichtweise zu behandeln.

Literatur:

  • Hromkovic, J.: Theoretische Informatik. 3.Auflage, B.G. Teubner Stuttgart, 2007.
  • Schöning, U.: Theoretische Informatik - kurz gefasst. 4.Auflage, Spektrum Akademischer Verlag Heidelberg Berlin, 2001.