Theoretische Informatik: -- Eine Algorithmenorientierte Einführung

ISBN-13: 9783835100336 / Niemiecki / Miękka / 2005 / 240 str.

Ingo Wegener

Opis

Die theoretische Informatik ist alter 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 zuganglich, da sie auf ein grosseres und tieferes Fundament aufbauen. Stark verastelte Theorien ten dieren dazu, sich als Selbstzweck aufzufassen und als l'art pour l'art betrieben zu werden. In der vorliegenden Einfuhrung 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 haufig den Anwendungen vorauseilt: "Wenn die Theorie auf die Erfahrung warten sollte, so kame 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 fur negative Resultate. Dabei sind deren Konsequenzen klar. Wenn wir beweisen, dass es bestimmte fur die Praxis wunschenswerte Werkzeuge oder Algorithmen nicht geben kann, muss die unsinnige, weil hoffnungslose Arbeit an diesen Werkzeugen oder Algorithmen eingestellt und statt dessen die Suche nach bestmoglichen Auswegen begonnen werden. Andererseits sind positive Resultate nicht automatisch anwendungsorientiert. Exis tenzaussagen oder Algorithmen mit exponentieller oder noch grosserer Laufzeit sind haufig praktisch wertlos. Das Neue an der vorliegenden Einfuhrung 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."

Spis treści

Churchsche These und Entscheidbarkeit - Die NP-Vollständigkeitstheorie - Approximationsprobleme - Probabilistische Algorithmen - Endliche Automaten - Die Chomsky-Hierarchie und das Wortproblem - Kontextfreie Grammatiken und Sprachen - Kellerautomaten und kontextfreie Sprachen - Deterministisch kontextfreie Sprachen - Zusammenfassung und Testfragen

O autorze

Prof. Dr. Ingo Wegener, Universität Dortmund

Blurb

Das Neue an dieser Einführung in die Theoretische Informatik ist die konsequent algorithmenorientierte Sichtweise, d.h. eine Umsetzung in praktisch und theoretisch effiziente Algorithmen wird angestrebt. Auf diese Weise bietet das Buch eine Einführung in die zentralen Gebiete der Theoretischen Informatik, wie sie in einer Einführungsvorlesung an deutschen Universitäten vorgesehen ist.