Kompendium Theoretische Informatik -- Eine Ideensammlung

ISBN-13: 9783519021452 / Niemiecki / Miękka / 1996 / 189 str.

Ingo Wegener

Opis

Der Physiker Stephen Hawking, der bekannt fUr seine anschaulichen Beschreibun gen komplexer, physikalischer Phanomene ist, leitet eines seiner Biicher mit fol gender Bemerkung ein. Ihm sei gesagt worden, daB jede Gleichung in einem Buch 2 die Verkaufszahlen halbiert. Daher wolle er sich auf die Gleichung E = mc be schranken. Nun wissen wir spatestens seit der Geschichte mit den Reiskornern auf dem Schachbrett, deren Anzahl sich auf jedem Feld verdoppeln solI, daB exponen tielles Wachstum nicht beherrschbar ist. So kenne ich kein Buch iiber Theoretische Informatik, das nach der obigen Regel auch nur einmal verkauft werden kann. Das gilt auch ffir die hier vorgelegte Ideensammlung, deren Hauptziel es dennoch ist, die wesentlichen Konzepte, Ideen und Methoden, die in einer Einfiihrung in die Theore tische Informatik vermittelt werden, so informal wie moglich darzustellen. Die vielen guten Lehrbiicher zu diesem Thema haben ihr Hauptziel in der Wissensvermittlung und der formal korrekten Darstellung des Stoffes. Sie alle sollen durch diese Ideen sammlung erganzt und keinesfalls ersetzt werden. Der Themenkatalog umfaBt den iiblichen Kanon einer vierstiindigen Einfiihrungsveranstaltung in die Theoretische Informatik mit den Gebieten Entscheidbarkeit, NP-Vollstandigkeit, Automatentheo rie, Grundlagen der Programmiersprachen und Syntaxanalyse. Es ist haufig einfacher, ein Resultat formal korrekt zu beweisen, als die wesentlichen Ideen und Methoden herauszuarbeiten. In formalen Beweisen haben wir sicheren Boden unter den FiiJ3en, aber es fant uns schwer, aus derartigen Beweisen das Ge meinsame und Wesentliche verschiedener Ansatze herauszufiltern und zu einem Netz zu verkniipfen."

Spis treści

Rechner, Churchsche These und unlösbare Probleme - NP-Vollständigkeitstheorie - Endliche Automaten - Grammatiken als Grundlage von Programmiersprachen - Kontextfreie Sprachen, kontextfreie Grammatiken und Kellerautomaten

O autorze

Prof. Dr. Ingo Wegener, Universität Dortmund

Blurb

Das "Kompendium Theoretische Informatik - eine Ideensammlung" ergänzt das Lehrbuch "Theoretische Informatik - eine algorithmenorientierte Einführung" vom gleichen Autor. An Stelle von formalen Beweisen werden die wesentlichen Ideen herausgearbeitet und vorgestellt. Die Vertiefung und Auffrischung von Kenntnissen in Theoretischer Informatik wird unterstützt. Die Ideensammlung wird ergänzt durch Übungsaufgaben mit Lösungen und Lösungsmethoden sowie Testfragen mit knappen Antworten.