Theoretische Informatik - kurzgefasst.

von Uwe Schöning Kategorie: Allgemein ISBN: 3827410991 Kommentar abgeben

Kurzbeschreibung Der Autor führt den Leser in kompakter Form, jedoch mit durchweg vollständig ausgeführten Beweisen, in die wesentlichen Grundlagen der Theoretischen Informatik ein. Das Buch ist nach den drei Hauptgebieten Automatentheore und formale Sprachen, Berechenbarkeitstheorie, Komplexitätstheorie gegliedert: Der erste Teil gibt einen Überblick über die Sprachklassen der Chomsky-Hierarchie, deren Grammatik- und Automatencharakterisierung und deren Abschluß- und Entscheidbarkeitseigenschaften. Der Berechenbarkeitsteil stellt unterschiedliche Ansätze der Berechenbarkeitsdefinition sowie deren Äquivalenzbeweise zur Unterstützung der Churchschen These vor. Verschiedene Unentscheidbarkeitsnachweise, z.B. vom Halteproblem und auch von Problemen der Theorie der Formalen Sprachen und der Logik werden geführt.Die Besprechung der Komplexitätstheorie konzentriert sich auf die Theorie der NP-Vollständigkeit und entwicklet diesen Begriff aus der Berechenbarkeit, speziell dem Turingmaschinenmodell. Ein Anliegen des Buches ist es, die vielfältigen Querbezüge zwischen den drei Gebieten aufzuzeigen.Prof. Dr. Uwe Schöning ist Leiter der Abteilung Theoretische Informatik der Universität Ulm.

Autorenportrait Prof. Dr. Uwe Schöning ist Leiter der Abteilung Theoretische Informatik der Universität Ulm.

• Theoretische Informatik
• Algorithmik
• Diskrete Strukturen, 2 Bde., Bd.1, Kombinatorik, Graphentheorie, Algebra
• Diskrete Strukturen, 2 Bde., Bd.2, Wahrscheinlichkeitstheorie und Statistik