Dieses Buch zeigt, dass Theoretische Informatik nicht schwer sein muss. Über 80 Beispiele und 100 Abbildungen helfen beim Verständnis des Stoffes, der die zentralen Gebiete einer Grundvorlesung Theoretische Informatik umfasst. Jedes Kapitel enthält zahlreiche, darauf abgestimmte Aufgaben und Prüfungsfragen mit vollständigen Lösungen. Ohne sich in Details zu verlieren, werden wichtige Beweisideen ausführlich dargestellt, formale Definitionen zuerst anschaulich erläutert. Aus dem Inhalt:
- Grundlegende Beweistechniken
- Graphen und Algorithmen
- Automaten, formale Sprachen und Grammatiken
- Berechenbarkeit und Entscheidbarkeit
- NP-vollständige Probleme
- Anwendungen und Programmierbeispiele Dieses Buch richtet sich besonders an Studenten im Grundstudium, die eine Vorlesung Theoretische Informatik hören oder sich auf eine Prüfung vorbereiten.

Vorwort

1 Grundlagen
1.1 Beweistechniken
1.2 Aussagenlogik
1.3 O-Notation und Landau-Symbole
1.4 Graphen
1.5 Prüfungsfragen

2 Automaten und formale Sprachen
2.1 Sprachen und Mengenoperationen
2.2 Grammatiken
2.3 Reguläre Sprachen
2.4 Kontextfreie Sprachen
2.5 Abschlusseigenschaften von Sprachen
2.6 Turing-Maschinen
2.7 Prüfungsfragen

3 Berechenbarkeit, Entscheidbarkeit und Komplexität
3.1 Berechenbarkeit
3.2 Entscheidbarkeit
3.3 Komplexitätstheorie
3.4 Prüfungsfragen

4 Lösungen der Aufgaben
4.1 Grundlagen
4.2 Formale Sprachen
4.3 Berechenbarkeit, Entscheidbarkeit und Komplexität

Anhang A
A.1 Übersicht Automaten
A.2 Reguläre Ausdrücke unter Unix
A.3 Notationen

Literaturverzeichnis
Index

Dr. Boris Hollas war viele Jahre Assistent in der Abteilung Theoretische Informatik der Universität Ulm und arbeitet jetzt bei Bosch Corporate Research.

Dr. Boris Hollas war viele Jahre Assistent in der Abteilung Theoretische Informatik der Universität Ulm und arbeitet jetzt bei Bosch Corporate Research.