Theoretische Informatik

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 zugnglich, da sie auf ein greres und tieferes Fundament aufbauen. Stark verstelte Theorien tendieren dazu, sich als Selbstzweck aufzufassen und als l'art pour l'art betrieben zu werden. In der vorliegenden Einfhrung 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 hufig den Anwendungen vorauseilt: "Wenn die Theorie auf die Erfahrung warten sollte, so kme 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 fr negative Resultate. Dabei sind deren Konsequenzen klar. Wenn wir beweisen, da es bestimmte fr die Praxis wnschenswerte Werkzeuge oder Algorithmen nicht geben kann, mu die unsinnige, weil hoffnungslose Arbeit an diesen Werkzeugen oder Algorithmen eingestellt und statt dessen die Suche nach bestmglichen Auswegen begonnen werden. Andererseits sind positive Resultate nicht automatisch anwendungsorientiert. Exi stenzaussagen oder Algorithmen mit exponentieller oder noch grerer Laufzeit sind hufig praktisch wertlos. Das Neue an der vorliegenden Einfhrung 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 effizienteAlgorithmen angestrebt.