Theoretische Informatik - kurz gefasst [Paperback]

Dieses in der 5. Auflage vorliegende Standardwerk macht Studierende in kompakter Form mit den wesentlichen Grundz?gen der Theoretischen Informatik vertraut. Der erste und gr??te Teil behandelt Formale Sprachen, Grammatiken und Automaten. Es schlie?t sich die Behandlung der Berechenbarkeitstheorie und der Komplexit?tstheorie an. Dem Autor gelingt durch seinen verst?ndlichen Beweisstil und viele Beispiele eine ?bersichtliche und im Detail gut nachvollziehbare Darstellung der Theoretischen Informatik.

Einleitung.- 1 Automatentheorie und Formale Sprachen.- 1.1 Allgemeines. 1.2 Regul?re Sprachen. 1.3 Kontextfreie Sprachen. 1.4 Kontextsensitive und Typ 0-Sprachen. 1.5 Tabellarischer ?berblick.- 2 Berechenbarkeitstheorie.- 2.1 Intuitiver Berechenbarkeitsbegriff und Churchsche These. 2.2 Turing-Berechenbarkeit. 2.3 LOOP-, WHILE- und GOTO-Berechenbarkeit. 2.4 Primitiv rekursive und m?-rekursive Funktionen. 2.5 Die Ackermannfunktion. 2.6 Halteproblem, Unentscheidbarkeit, Reduzierbarkeit. 2.7 Das Postsche Korrespondenzprinzip. 2.8 Unentscheidbare Grammatik-Probleme. 2.9 Der G?delsche Satz.- 3 Komplexit?tstheorie.- 3.1 Komplexit?tsklassen und P-NP-Problem. 3.2 NP-Vollst?ndigkeit. 3.3 Weitere NP-vollst?ndige Probleme.- Anhang: Mathematische Grundlagen.- Literaturverzeichnis.- Index

Prof. Dr. Uwe Sch?ning ist Leiter des Instituts f?r Theoretische Informatik der Universit?t Ulm. Von Prof. Sch?ning sind ebenfalls bei Spektrum Akademischer Verlag erschienen: Logik f?r Informatiker und Algorithmik

Dieses in der 5. Auflage vorliegende Standardwerk macht Sie in kompakter Form mit den wesentlichen Grundz?gen der Theoretischen Informatik vertraut. Der erste und gr??te Teil behandelt Formale Sprachen, Grammatiken und Automaten. Prof. Sch?ning gelingt durch seinen verst?ndlichen Beweisstil und viellC%