Grundkurs theoretische Informatik

Inhaltsverzeichnis1. Grundbegriffe.1.1. Mengen, Abbildungen, Funktionen, Sprachen.1.2. Relationen.2. Automaten und Sprachen.2.1. Endliche deterministische Automaten.2.2. Endliche nichtdeterministische Automaten.2.3. Von endlichen Automaten akzeptierte Sprachen.2.4. Kontextfreie Sprachen I.2.5. Kellerautomaten.2.6. Kontextfreie Sprachen II.2.7. Deterministische Kellerautomaten.3. Turing-Maschinen.3.1. Grundbegriffe.3.2. Einige Verallgemeinerungen von Turing-Maschinen.4. Die These von Church und weitere Begriffe der Berechenbarkeit.4.1. Grammatische Berechenbarkeit.4.2. Rekursive Funktionen.4.3. Universelle Turing-Maschinen.4.4. Unberechenbarkeit (was Computer nicht können).5. Einführung in die Komplexitätstheorie.5.1. Programmiersprachen und Numerierungen.5.2. Programm- oder Beschreibungskomplexität.5.3. Berechnungskomplexität.5.4. Komplexitätsmaße für Turing-Maschinen: Ein Überblick.5.5. Das P=NP-Problem.Anhang: Einführung in die Logik.Literatur.Register.