Theoretische Informatik

Verständlich und gut lesbar: Diese fundierte Einführung eignet sich insbesondere für Anfänger, da sie Beweise im Detail ausführt und insofern auch in die Technik des Beweisens einführt. Zusätzlich stellen die Autoren Nicht-Standard-Berechnungsmodelle vor...

Autorentext

Lutz Priese: Studium der Mathematik an der Westfälischen Wilhelms-Universität Münster, Promotion 1974; Habilitation in Informatik 1979 an der Universität Dortmund; C3-Professor für Informatik an der Universität-Gesamthochschule Paderborn 1980 - 1991; seit 1991 C4-Professor für Theoretische Informatik an der Universität Koblenz-Landau, Gründungsleiter des Instituts für Computervisualistik, Gründung einer Firma zur industriellen Bildverarbeitung, 1. Innovationspreis des Landes Rheinland-Pfalz 2000.Katrin Erk: Studium der Informatik an der Universität Koblenz-Landau, Promotion an der Universität des Saarlandes 2002; wissenschaftliche Mitarbeiterin am Institut für Computerlinguistik, Universität des Saarlandes 2002 - 2006; seit 2006 Professorin für Computerlinguistik an der University of Texas at Austin im Linguistics Department.

Inhalt
Begriffe und Notationen.- Eine kurze Einführung in die Aussagenlogik.- Grammatiken und formale Sprachen.- Reguläre Sprachen und endliche Automaten.- Kontextfreie Sprachen.- Turing-Maschinen.- Die Sprachklassen , 0 und 1.- Abschlusseigenschaften von Sprachklassen.- Berechenbarkeit.- Registermaschinen.- Rekursive Funktionen.- Unentscheidbare Probleme.- Alternative Berechnungsmodelle.- Komplexität.