Start Inhaltsverzeichnis Vorwort Errata Downloads

Inhaltsverzeichnis

1 Grundlagen

1.1 Beweistechniken

1.1.1 Indirekter Beweis

1.1.2 Beweis durch Widerspruch

1.1.3 Induktion

1.1.4 Diagonalisierung

1.1.5 Häufige Fehler

1.1.6 Wie findet man einen Beweis?

1.2 Aussagenlogik

1.3 O-Notation und Landau-Symbole

1.4 Graphen

1.4.1 Grundbegriffe

1.4.2 Bäume

1.4.3 Graphenisomorphie

1.4.4 Ein Zero-Knowledge-Protokoll

1.4.5 Repräsentation von Graphen

1.4.6 Breitensuche und Tiefensuche

1.4.7 Binäre Relationen

1.5 Prüfungsfragen

2 Automaten und formale Sprachen

2.1 Sprachen und Mengenoperationen

2.2 Grammatiken

2.2.1 Die Chomsky-Hierarchie

2.2.2 Mehrdeutigkeit

2.3 Reguläre Sprachen

2.3.1 Endliche Automaten

2.3.2 Verwandte Automatenmodelle

2.3.3 Das Pumping-Lemma

2.3.4 Reguläre Ausdrücke

2.3.5 Lexikalische Analyse

2.4 Kontextfreie Sprachen

2.4.1 Kellerautomaten

2.4.2 Das Wortproblem bei kontextfreien Sprachen

2.4.3 Das Pumping-Lemma für kontextfreie Sprachen

2.4.4 Syntaxanalyse

2.5 Abschlusseigenschaften von Sprachen

2.6 Turing-Maschinen

2.6.1 Deterministische und nichtdeterministische Turing-Maschinen

2.6.2 Mehrband Turing-Maschinen

2.7 Prüfungsfragen

3 Berechenbarkeit, Entscheidbarkeit und Komplexität

3.1 Berechenbarkeit

3.1.1 Turing-Berechenbarkeit und Programmiersprachen

3.1.2 Goto- und While-Programme

3.1.3 Loop-Berechenbarkeit

3.2 Entscheidbarkeit

3.2.1 Das Halteproblem

3.2.2 Reduzierbarkeit

3.3 Komplexitätstheorie

3.3.1 Die Klassen P und NP

3.3.2 Eine andere Charakterisierung von NP

3.3.3 NP-Vollständigkeit

3.3.4 Weitere NP-vollständige Probleme

3.4 Prüfungsfragen

4 Lösungen der Aufgaben

4.1 Grundlagen

4.1.1 Beweistechniken

4.1.2 Aussagenlogik

4.1.3 O-Notation und Landau-Symbole

4.1.4 Graphen

4.1.5 Prüfungsfragen

4.2 Formale Sprachen

4.2.1 Sprachen und Mengenoperationen

4.2.2 Grammatiken

4.2.3 Reguläre Sprachen

4.2.4 Kellerautomaten und kontextfreie Sprachen

4.2.5 Abschlusseigenschaften von Sprachen

4.2.6 Turing-Maschinen

4.2.7 Prüfungsfragen

4.3 Berechenbarkeit, Entscheidbarkeit und Komplexität

4.3.1 Berechenbarkeit

4.3.2 Entscheidbarkeit

4.3.3 Komplexitätstheorie

4.3.4 Prüfungsfragen