Vorlesung über "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.

Termine

Die Veranstaltung beginnt am Mi, 9. April 08 um 12.00 Uhr.

Literatur

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