Vorlesung über "Theoretische Informatik"

Nichts ist praktischer als eine gute Theorie! 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, Kryptografie) behandelt. Die Vorlesung folgt nicht dem klassischen "Definition-Satz-Beweis"-Stil und probiert, diese Thematik aus algorithmenorientierter Sichtweise zu behandeln.

Bei weiteren Fragen, die Sie auf diesen Seiten nicht beantwortet sehen, können Sie sich per E-Mail an Bert Randerath wenden.

Termine

• Mittwochs 13.30-15.00 und Donnerstags 10.15-11.45 im Hörsaal 301, Pohlighaus.
• Übungen: nach Vereinbarung, im Pohlighaus; Betreuer: Zülfükar Genç.

Literatur

• Juraj Hromkovic, Theoretische Informatik, B.G. Teubner Stuttgart, 2004
• Ingo Wegner, Theoretische Informatik - eine algorithmenorientierte Einführung, B.G. Teubner Stuttgart, 1999
• John E. Hopcroft, Rajeev Motwani, Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, 2001
• Uwe Schöning, Theoretische Informatik - kurz gefasst, Spektrum Akademischer Verlag Heidelberg Berlin, 1999