Inhalt
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.
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.
Titel
Grundkurs Theoretische Informatik
Autor
Ghostwriter
EAN
9783322954442
Format
E-Book (pdf)
Hersteller
Genre
Veröffentlichung
09.03.2013
Digitaler Kopierschutz
Wasserzeichen
Dateigrösse
16.36 MB
Anzahl Seiten
220
Auflage
1992
Lesemotiv
Unerwartete Verzögerung
Ups, ein Fehler ist aufgetreten. Bitte versuchen Sie es später noch einmal.