Skip to main content
main-content

Über dieses Buch

Die theoretische Informatik ist älter als die praktische, angewandte oder technische Informatik. Daher ist sie als wissenschaftliche Disziplin bereits weiter ausgebaut als andere Bereiche der Informatik und ihre Ergebnisse sind schwerer zugänglich, da sie auf ein größeres und tieferes Fundament aufbauen. Stark verästelte Theorien ten­ dieren dazu, sich als Selbstzweck aufzufassen und als l'art pour l'art betrieben zu werden. In der vorliegenden Einführung in die theoretische Informatik begegnen wir dieser Gefahr, indem wir die Orientierung moderner Theorien an den Anwendun­ gen in den Mittelpunkt stellen. Schon Novalis (1772-1801) hat darauf hingewiesen, dass die Theorie häufig den Anwendungen vorauseilt: "Wenn die Theorie auf die Erfahrung warten sollte, so käme sie nie zustande. " Nicht immer sind die Anwendungen von Ergebnissen der theoretischen Informatik so direkt zu sehen wie die Anwendungen anderer Zweige der Informatik. Dies gilt insbesondere für negative Resultate. Dabei sind deren Konsequenzen klar. Wenn wir beweisen, dass es bestimmte für die Praxis wünschenswerte Werkzeuge oder Algorithmen nicht geben kann, muss die unsinnige, weil hoffnungslose Arbeit an diesen Werkzeugen oder Algorithmen eingestellt und statt dessen die Suche nach bestmöglichen Auswegen begonnen werden. Andererseits sind positive Resultate nicht automatisch anwendungsorientiert. Exis­ tenzaussagen oder Algorithmen mit exponentieller oder noch größerer Laufzeit sind häufig praktisch wertlos. Das Neue an der vorliegenden Einführung in die theore­ tische Informatik ist die konsequent algorithmenorientierte Sichtweise (zum didak­ tischen Hintergrund siehe Wegener (1995)). Stets wurde bei positiven Resultaten eine Umsetzung in praktisch und theoretisch effiziente Algorithmen angestrebt.

Inhaltsverzeichnis

Frontmatter

1. Einleitung

Zusammenfassung
Einführungen in die theoretische Informatik gehören an allen deutschen Universitäten im Studiengang Informatik zu den Pflichtvorlesungen im Grundstudium. Häufig bilden sie jedoch die ungeliebteste Grundstudiumsveranstaltung. Dies liegt nur teilweise an falschen Erwartungen an ein Informatikstudium. Die Inhalte der theoretischen Informatik sind nicht so direkt anwendbar wie viele Inhalte der Grundvorlesungen über Programmierung, Rechnerarchitektur, Hardware, Datenstrukturen und den Entwurf effizienter Algorithmen. Dafür sind die Erkenntnisse der theoretischen Informatik oft allgemeiner, umfassender und weitreichender als in den anderen Gebieten der Informatik. Mit dem vorliegenden Buch sollen die Leserinnen und Leser (wenn sie es nicht schon sind) davon überzeugt werden, dass die theoretische Informatik nicht eine lästige Pflichtvorlesung ist, sondern dass moderne Informatikerinnen und Informatiker keine qualifizierte Arbeit ohne solide Theoriekenntnisse leisten können und dass diese Kenntnisse in der praktischen Arbeit anwendbar sind.
Ingo Wegener

2. Turingmaschinen, churchsche These und Ent-scheidbarkeit

Zusammenfassung
Aussagen zur Komplexität von Problemen und zur Effizienz von Algorithmen sind nur dann von allgemeiner Bedeutung, wenn sie nur unwesentlich von der verwendeten Programmiersprache und dem zugrunde liegenden Rechnertyp abhängen. Turingma-schinen werden sich als geeignetes Modell erweisen, um zu prüfen, welche Probleme berechenbar und welche Probleme in polynomieller Zeit lösbar sind. Turingmaschi-nen sind aber im Allgemeinen um nicht zu vernachlässigende polynomielle Faktoren langsamer als reale Rechner. Weit näher an reale Rechner angelehnt ist das Modell der Registermaschinen (random access machine = RAM). Wir werden dieses Modell hier vorstellen, um in Kapitel 2.3 zu zeigen, dass Turingmaschinen und reale Rechner sich gegenseitig ohne superpolynomiellen Zeitverlust simulieren können. Die konkreten Aussagen über die Laufzeit von Algorithmen beziehen sich in diesem Buch immer auf reale Rechner, das heißt wir bewerten arithmetische Operationen, Zuweisungen, Vergleiche, usw. als elementare Rechenschritte. Der schematische Aufbau einer Registermaschine ist in Abb. 2.1.1 dargestellt.
Ingo Wegener

3. Die NP-Vollständigkeitstheorie

Zusammenfassung
Wann ist die Aufgabe, einen effizienten Algorithmus für ein bestimmtes Problem zu finden, erfolgreich gelöst? Polynomielle Algorithmen für Registermaschinen gelten als effiziente Algorithmen. Nach den Ergebnissen aus Kapitel 2 können wir hierbei Registermaschinen durch Turingmaschinen, aber auch durch C++-Programme oder Java-Programme ersetzen.
Ingo Wegener

4. Endliche Automaten

Zusammenfassung
Auf Hardwareebene können boolesche Funktionen wie die Addition oder Multiplikation zweier Binärzahlen durch Schaltkreise realisiert werden. Diese feste Verdrahtung von Befehlen der Assemblersprache lässt jedoch nicht die gewünschte Miniaturisierung der Hardware zu. Daher werden auch Addition und Multiplikation häufig nicht durch Schaltkreise, sondern durch Schaltwerke wie zum Beispiel das von-Neumann-Addierwerk realisiert. Um Probleme wie Instabilität oder Hazards auszuschließen, sollten Schaltwerke mit Flip-Flops getaktet werden. Derartig gezähmte sequenzielle Schaltwerke arbeiten nach dem Huffman-Modell (Huffman (1954)). Ihr Verhalten kann schematisch durch Abb. 4.1.1 beschrieben werden.
Ingo Wegener

5. Grammatiken, die Chomsky-Hierarchie und das Wortproblem

Zusammenfassung
Wir nehmen nun eine ganz neue Sichtweise ein. Wir wollen Regelsysteme entwerfen, mit denen sich genau die Wörter einer vorgegebenen Sprache erzeugen lassen. Für Programmiersprachen bedeutet dies, dass wir Regeln suchen, mit denen sich genau die syntaktisch korrekten Programme aufbauen lassen. Derartige Systeme werden in Anlehnung an natürliche Sprachen Grammatiken genannt. Wir wollen auf weitergehende Analogien zu natürlichen Sprachen nicht eingehen, da alle Vergleiche hinken. Natürliche Sprachen sind nicht so regelbasiert aufgebaut, wie es Programmiersprachen sind.
Ingo Wegener

6. Kontextfreie Grammatiken und Sprachen

Zusammenfassung
Von den vier Klassen der Chomsky-Hierarchie bleibt nur noch die Klasse der kontextfreien Sprachen als Basis für den Entwurf von Programmiersprachen übrig. Zunächst überzeugen wir uns davon, dass diese Klasse viel ausdrucksstärker als die Klasse der regulären Sprachen ist. Dafür entwerfen wir für drei Sprachen, die wir bereits als nicht regulär nachgewiesen haben, kontextfreie Grammatiken.
Ingo Wegener

7. Kellerautomaten und kontextfreie Sprachen

Zusammenfassung
Für die Klasse rekursiv aufzählbarer und die Klasse regulärer Sprachen haben wir zunächst maschinenorientierte Definitionen benutzt und erst später zugehörige Grammatiken kennen gelernt. Die Klasse kontextfreier Sprachen ist dagegen, da sie eine Basis zur Entwicklung von Programmiersprachen bilden soll, durch kontextfreie Grammatiken definiert worden. Da wir aber bereits die vielen Vorteile einer maschinenorientierten Sichtweise kennengelernt haben, wollen wir ein Maschinenmodell, das genau die kontextfreien Sprachen akzeptieren kann, entwickeln.
Ingo Wegener

8. Deterministisch kontextfreie Sprachen

Zusammenfassung
Wenn wir uns für kontextfreie Grammatiken als Regelsysteme für Programmiersprachen entscheiden, haben wir Regelsysteme, die mächtig genug sind, um moderne Programmiersprachen (zumindest bis auf Details von untergeordneter Bedeutung) beschreiben zu können. Die besten von uns behandelten Algorithmen für das Wort-und das Syntaxanalyseproblem haben kubische Laufzeit und sind daher für praktische Zwecke zu langsam. Ein Algorithmus von Valiant (1975) kommt mit Zeit O(nlog7) = O(n2.81) aus, ist aber aus praktischer Sicht kaum eine Verbesserung. Der praktisch beste Algorithmus geht auf Earley (1970) zurück. Zwar kann seine Rechenzeit allgemein nur durch O(n3) abgeschätzt werden, für eindeutige kontextfreie Grammatiken sinkt die Rechenzeit jedoch auf O(n2). Für viele Grammatiken ist die Rechenzeit sogar linear. Dennoch sind wir an Grammatikklassen interessiert, die einerseits noch die modernen Programmiersprachen beschreiben können, andererseits aber stets Linearzeitalgorithmen für das Wort- und das Syntaxanalyseproblem ermöglichen. Dies wird die Klasse der deterministisch kontextfreien Grammatiken sein. Bisher haben wir nur Rechner, Maschinen und Automaten als deterministisch oder nichtdeterministisch klassifiziert und nicht Grammatiken. Es fällt uns zu diesem Zeitpunkt auch schwer, uns vorzustellen, wann wir eine kontextfreie Grammatik oder Sprache deterministisch nennen können. Einfacher ist dies für Kellerautomaten. Deterministische Kellerautomaten (DPDAs) „sind“ deterministische Algorithmen für das Wortproblem für die von ihnen akzeptierten Sprachen, und die Rechenzeit auf der Eingabe ω ist „bis auf die ε-Schritte“ linear.
Ingo Wegener

9. Zusammenfassung und Testfragen

Zusammenfassung
Die Ergebnisse, die vor allem im Kernbereich (siehe Vorwort) dieses Buches erarbeitet worden sind, sollen hier noch einmal zusammengefasst werden. Durch diese knappe Nebeneinanderstellung von Resultaten sollen Querverbindungen verdeutlicht werden. Außerdem kann dieser Abschnitt als Nachschlagewerk dienen. Eine ausführliche, stärker intuitive und weniger formale Beschreibung der Inhalte dieses Buches findet sich in dem Kompendium zu diesem Buch Wegener (1996b)).
Ingo Wegener

Backmatter

Weitere Informationen