Die Theoretische Informatik ist älter als die Praktische, Angewandte
oder Techni- sche 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 tendieren
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, daß 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, daß es bestimmte für die Praxis wünschenswerte Werkzeuge oder
Algorithmen nicht geben kann, muß 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. Exi- stenzaussagen 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 (1992)). Stets wurde bei
positiven Resultaten eine Umsetzung in praktisch und theoretisch
effiziente Algorithmen angestrebt.
