Grundkurs Theoretische Informatik [Paperback]

1. 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.Springer Book Archives