Vorwort

Warum und zu welchem Ende studieren wir Theoretische Informatik?

Informatik-Studenten in den ersten Semestern empfinden häufig die Vorlesungen zur Theoretischen Informatik als lästige Zumutung. Sie verstehen die Informatik als eine Wissenschaft des Handelns und Gestaltens und sehen die Theorie als ein Gebirge von Abstraktionen. Sie vergessen dabei, daß mit sinnvollem Handeln und effizientem Gestalten untrennbar das Planen und Entwerfen verbunden sind. Planen und Entwerfen geschieht aber auf der Basis von Modellen, man macht sich ein Modell und spielt seinen Plan daran durch. Geht es um ein größeres Projekt, so muß dieses Modell mitteilbar sein, damit Zusammenarbeit möglich ist. Mitteilbar sein bedeutet aber, daß ein allen Mitarbeitern gemeinsames Netz von Abstraktionen, d.h. ein gemeinsames Begriffssystem, vorhanden ist und ausschließlich genutzt werden muß. Um die angestrebten Ziele des Projektes zu erreichen, muß dieses Begriffssystem präzise Formulierungen ermöglichen. Das einzige Begriffssystem, das diese Forderung erfüllt, ist die abstrakte Begriffswelt der Mathematik. Wie die Physik nutzt die Informatik das mathematische Begriffssystem zur Formulierung ihrer Modelle und der Semantik dieser Modelle.

Deshalb führt diese Vorlesung zunächst in die Mengenlehre als Grundlage der Mathematik ein. Hier geht es auch darum, intuitiv vorhandene Begriffe (wie z.B. dem der Relation) scharf zu präzisieren, d.h. eine Sprachregelung zu treffen, genau zu definieren.

Der Informatiker unterscheidet sich vom Programmierer nicht nur darin, daß er gefundene Lösungen bewerten und gegebenfalls verbessern kann. Zur Bewertung gehört neben dem Beweis, daß das geplante System die gestellte Aufgabe auch wirklich löst, auch der Vergleich der theoretisch erreichbaren mit der praktisch realisierten Effizienz. Wir studieren also in dieser Vorlesung, wie Modelle gebildet werden (wie dieser Abstraktionsprozeß verläuft) und welche Fragen bei der Modellbildung beantwortet werden müssen, welche Hilfe uns die Theorie bei der Anwendung dieser Modelle geben kann. Das geschieht an (im wesentlichen) drei Beispielen.

In der Aussagenlogik geht es um die Wahrheit bzw. Falschheit von Aussagen und Aussagenverbindungen. Unser Modell, der Aussagenkalkül, stellt unsere Vorstellungen auf eine berechenbare Grundlage: Wir können mit Aussagen rechnen, ihre Wahrheit beweisen. Als Hauptaufgabe der Logik betrachten wir dabei, semantische (d.h. inhaltliche) Beziehungen und Begriffe syntaktisch zu charakterisieren.

In der Berechnungstheorie geht es darum, was Computer eigentlich können, also auch darum, was sie nicht können. Wir geben in dieser Vorlesung einen Abschnitt der Berechnungstheorie wieder, der uns beweist, daß es für Computer unlösbare (abstrakte) Probleme gibt. Zu diesen Problemen gehört das Entscheidungsproblem der Prädikatenlogik, d.h. die Frage nach einem Verfahren, mit dessen Hilfe von jeder Aussage über die Elemente einer gewissen Menge festgestellt werden kann, ob diese Aussage richtig ist. Wenn auch ein solches Verfahren (ein Algorithmus) nicht existiert, so kann doch ein Verfahren gefunden werden, das die Richtigkeit richtiger Aussagen bestätigt (für falsche Aussagen aber keine Information liefert).

Spätestens an dieser Stelle bemerkt der Leser, wie ungenaue Formulierungen Verwirrung erzeugen, wie notwendig also ein scharf definiertes Begriffssystem ist. Auch dazu dient uns die Logik (gibt es z.B. einen Unterschied zwischen Wahrheit und Beweisbarkeit?).


© 1995-2000 Prof. Peter H. Starke (starke@informatik.hu-berlin.de) und Stephan Roch (roch@...)

Zuletzt geändert am: 2000-07-06