Grundvorlesung Grundbegriffe der theoretischen Informatik

Grundvorlesung

"Grundbegriffe der theoretischen Informatik"

Sommersemester 2005


Veranstalter:		Detlef Sieling
Termin:		Dienstag, 10.15-12.00 Uhr, EF50, HS1
		Donnerstag, 10.15-12.00 Uhr, Audimax
Beginn der Vorlesung:		12.4.2005
Übungen:		André Gronemeier, Martin Scholz, Tobias Storch, Philipp Wölfel
Verteilung der Übungsgruppen:		in der ersten Vorlesung

Die Vorlesung "Grundbegriffe der theoretischen Informatik" ist eine Einführung in die Gebiete Komplexitätstheorie, Entscheidbarkeitstheorie, Automatentheorie, Grammatiken und Syntaxanalyse.

Das Ziel der Komplexitätstheorie besteht darin, den Ressourcenbedarf, insbesondere die Rechenzeit, die nötig ist, um ein gegebenes Problem zu lösen, möglichst genau zu bestimmen. Als ersten Schritt werden wir überlegen, wie man die Rechenzeit unabhängig vom betrachteten Rechnermodell und der benutzten Programmiersprache untersuchen kann. Um zu zeigen, dass eine bestimmte Rechenzeit zur Lösung des Problems ausreicht, genügt es, einen Algorithmus mit dieser Rechenzeit anzugeben. In der Komplexitätstheorie möchte man aber zeigen, dass eine bestimmte Rechenzeit nicht unterschritten werden kann. Dazu muss man zeigen, dass alle möglichen Algorithmen für dieses Problem mindestens diese Rechenzeit haben. Offensichtlich ist es viel schwieriger, Aussagen über alle Algorithmen für das Problem zu machen.

Viele wichtige Probleme lassen sich durch triviale Algorithmen lösen, die alle möglichen Lösungen ausprobieren und die beste auswählen. Dieser Ansatz führt meistens zu exponentieller Rechenzeit. Für viele Probleme sind allerdings keine wesentlichen besseren Algorithmen als diese Probieralgorithmen bekannt. Eine Klasse von solchen Problemen sind die so genannten NP-vollständigen Probleme. Wir zeigen, dass es entweder für alle Probleme dieser Klasse effiziente Algorithmen gibt oder für alle Probleme dieser Klasse keine wesentlich besseren Algorithmen als die Probieralgorithmen. Es wird allgemein vermutet, dass die zweite Möglichkeit zutrifft.

In der Entscheidbarkeitstheorie wird untersucht, für welche Probleme es keine Algorithmen gibt, welche Probleme also niemals mit Rechnerhilfe gelöst werden können. Auch hier ist das verwendete Rechnermodell unerheblich. Ein Beipiel für ein nicht berechenbares Problem ist der Test, ob zwei gegebene Programme dieselbe Funktion berechnen, ein Test, der offensichtlich für die Verifikation von Programmen wichtig ist. Für die Praxis bedeutet ein Resultat, dass das betrachtete Problem nicht berechenbar ist, dass wir untersuchen müssen, ob es für die betrachtete Anwendung reicht, ein Teilproblem, das berechenbar ist, zu lösen.

Endliche Automaten sind Rechner mit beschränktem Speicher, die in Rechnerkomponenten, Cola-Automaten, aber auch bei der Analyse von Programmiersprachen vorkommen. Damit ist die Analyse von endlichen Automaten grundlegend für viele andere Teilbereiche der Informatik.

Programmiersprachen werden durch Grammatiken beschrieben. Es sollte effizient möglich sein, die syntaktische Korrektheit von Programmen zu überprüfen und die Programme zu compilieren; andererseits sollten die Grammatiken auch ausdrucksstark genug sein, um die verwendeten Programmkonstrukte beschreiben zu können. Es wird gezeigt, dass kontextfreie Grammatiken als Grundlage von Programmiersprachen geeignet sind.

In der theoretischen Informatik wird häufig von realen Problemen abstrahiert, um beweisbare Aussage zu erhalten. Viele der Aussagen in der Vorlesung sind negative Aussagen, etwa dass es für ein Problem keinen Algorithmus gibt. Auch eine solche Aussage ist 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 beiden 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.

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.

11.4.2005 - Detlef Sieling