Vossen / Witt Grundkurs Theoretische Informatik

Eine anwendungsbezogene Einführung - Für Studierende der Informatik, Wirtschaftsinformatik, Technik
3., überarbeitete und erweiterte Auflage 2004
ISBN: 978-3-322-94309-5
Verlag: Vieweg & Teubner
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Deutsch, 406 Seiten, eBook

lungen das passende Werkzeug findet. Wir versuchen daher, die Ausführungen und Entwicklungen stets von den Anwendungen her zu motivieren, und wir bemühen uns, Fragestellungen, zu denen die Automatentheorie ein Werkzeug liefert, dann auch mit diesem anzugehen. Im Vergleich zu anderen Theorie-Lehrbüchern stehen somit also nicht nur die Präsentation der grundlegenden Begriffe der Theoretischen Informatik und deren Analyse im Mittelpunkt des Buches, sondern insbesondere auch die Kon struktion von Problemlösungen. Naturgemäß endet das nicht in Komplettlösungen, aber die Leserschaft wird nahe genug an solche herangeführt. Inhaltlich folgen wir einem klassischen Präsentationsschema des Stoffes, welches vielfach in Lehrbüchern und Kursen bewährt ist: vom einfachen Automaten zum kom plizierteren. Wir beginnen also mit endlichen Automaten und regulären Sprachen und arbeiten uns von dort die Chomsky-Hierarchie"hinauf" und schließen mit den Themen Berechenbarkeit und Komplexität. Dieser Strang wird laufend durch Anwendungen und Anwendungsbeispiele begleitet, denn diese sollen nicht erst dann behandelt wer den, wenn die Theorie eingigermaßen komplett vorgestellt und durchgearbeitet ist. Münster und St. Augustin, im März 2000 G.V. und K.U.W. Vorwort zur 2. Auflage In der zweiten Auflage wurde eine Reihe von kleineren Fehlern verbessert; für Hin weise auf solche danken wir insbesondere unserem aufmerksamen Leser Dirk Hofmann. Darüber hinaus haben wir an verschiedenen Stellen Überarbeitungen vorgenommen und das Literaturverzeichnis aktualisiert.

Zielgruppe

Upper undergraduate

Autoren/Hrsg.

Vossen, Gottfried

Witt, Kurt-Ulrich

Inhaltsverzeichnis

1 Einführung und Übersicht.- 1.1 Ausgangspunkte für das Themengebiet.- 1.2 Anwendungen theoretischer Erkenntnisse.- 1.3 Stoffübersicht und -abgrenzung.- 1.4 Externe Lernhilfen und Web-Seiten.- 1.5 Allgemeine Bibliographische Hinweise.- I Endliche Automaten und reguläre Sprachen.- 2 Endliche Automaten.- 3 Reguläre Sprachen.- 4 Endliche Maschinen und Automatennetze.- II Kontextfreie Sprachen und Kellerautomaten.- 5 Kontextfreie Sprachen.- 6 Kellerautomaten.- 7 Anwendungen kontextfreier Sprachen.- III Berechenbarkeit und Komplexität.- 8 Typ-1- und Typ-0-Sprachen.- 9 Berechenbarkeit.- 10 Entscheidbarkeit.- 11 Komplexität.- 12 Approximative und probabilistische Ansätze und deren Anwendungen.

Über Autor(innen)

Prof. Dr. Gottfried Vossen lehrt und forscht am Institut für Wirtschaftsinformatik bzw. dem europäischen Forschungszentrum ERCIS, Universität Münster. Vizepräsident der Gesellschaft für Informatik e.V., Bonn. Prof. Dr. Kurt-Ulrich Witt lehrt Grundlagen der Informatik am Fachbereich Informatik der Fachhochschule Bonn-Rhein-Sieg. Direktor des Bonn-Aachen International Center for Information Technology - b-it.