Description
Book SynopsisEinleitung.- 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.
