Theoretische Informatik für Studierende der angewandten Informatik

"Theoretische Informatik für Studierende der angewandten Informatik"

Sommersemester 2006


Veranstalter:		Detlef Sieling
Termin:		Dienstag, 8.15-10.00 Uhr, OH-14, Hörsaal E23
		Donnerstag, 10.15-12.00 Uhr, OH-14, Hörsaal E23
Beginn der Vorlesung:		4. April 2006
Übungen:		Robin Nunkesser
Verteilung der Übungsgruppen:		In der ersten Vorlesung

Die Vorlesung "Theoretische Informatik für Studierende der Angewandten Informatik" bietet eine Einführung in die theoretische Informatik unter besonderer Berücksichtigung anwendungsbezogener Aspekte. Konkret werden die Teilgebiete Entscheidbarkeitstheorie, Komplexitätstheorie, Automatentheorie, Grammatiken, Syntaxanalyse und lineare Programmierung behandelt.

Während es in der Vorlesungsreihe "Datenstrukturen, Algorithmen und Programmierung" vorrangig darum geht, für konkrete Probleme effiziente Algorithmen zu finden, wollen wir uns hier stärker auf die Probleme an sich konzentrieren und sehr viel grundsätzlicher untersuchen, wie sie gelöst werden können. Dabei stehen zunächst Negativresultate im Vordergrund: Welche Probleme kann man mit einem Computer überhaupt nicht lösen, welche (vermutlich) nicht effizient? Hierbei wird sich auch die Untersuchung von randomisierten Rechnermodellen als nützlich erweisen.

Eingeschränkte Rechnermodelle wie zum Beispiel Mealy-Automaten sind schon aus der Vorlesung "Rechnerstrukturen" bekannt. Wir wollen hier systematisch eingeschränkte Rechnermodelle untersuchen und sehen, wie ihr Verständnis in der Praxis hilfreich ist. Es ergeben sich wichtige und hilfreiche Beziehungen zu Grammatiken, die zur formalen Beschreibung der Syntax von Programmiersprachen benutzt werden. Auch hier konzentrieren wir uns auf die Aspekte, die uns in der Praxis zum Beispiel beim Entwurf eigener Programmiersprachen hilfreich sein können.

In der theoretischen Informatik wird häufig von realen Problemen abstrahiert, um beweisbare Aussage zu erhalten. Auch negative Aussagen, etwa dass es für ein Problem keinen Algorithmus gibt, sind für die Praxis relevant, da man sich die Zeit für die Suche nach einem Algorithmus, den es nicht gibt, sparen kann. Andererseits sind die Zwischenschritte, um zu solchen Aussagen zu kommen, an vielen Stellen abstrakter als in früheren Vorlesungen, was eine der neuen Schwierigkeiten beim Verständnis der Vorlesung ist. Eine andere Schwierigkeit besteht darin, dass für die exakte Formulierung von Aussagen formalere Schreibweisen erforderlich sind. Insbesondere die Übungen sollen dabei helfen, im Umgang mit diesen formalen Schreibweisen Routine zu bekommen.

Literatur zur Vorlesung

Die Vorlesung richtet sich im Wesentlichen nach den folgenden Büchern:

Wegener, I. Theoretische Informatik - eine algorithmenorientierte Einführung. 2. Auflage, Teubner, 1999.
Wegener, I. Komplexitätstheorie - Grenzen der Effizienz von Algorithmen. Springer 2003.
Blum, N. Algorithmen und Datenstrukturen - eine anwendungsorientierte Einführung (Kapitel 8). Oldenbourg 2004.

Im folgenden Buch werden wichtige Ideen der Vorlesung auf eine informellere Weise dargestellt, was für das Verständnis hilfreich sein kann, aber nicht den Inhalt der Vorlesung vollständig abdeckt.

Wegener, I. Kompendium der Theoretischen Informatik - eine Ideensammlung. Teubner, 1996.

Darüber hinaus gibt es zahlreiche weitere Bücher über den Inhalt der Vorlesung, die allerdings einige Modernisierungen, die in den Büchern von Ingo Wegener enthalten sind, nicht umgesetzt haben und deren Stoffauswahl sich von dem der Vorlesung unterscheidet. Hier eine kleine Auswahl:

Hopcroft, J.E., Motwani, R. und Ullman, J.D. Introduction to Automata Theory, Languages, and Computation. Second Edition. Addison-Wesley, 2001.
Lewis, H.R. und Papadimitriou, C.H. Elements of the Theory of Computation. Prentice-Hall 1998.
Papadimitriou, C.H. Computational Complexity. Addison-Wesley 1995.
Sipser, M. Introduction to the Theory of Computation. PWS Publishing Company 1997.

23.1.2006 - Detlef Sieling