Algorithmische Konzepte der Informatik

Das Buch versteht sich als eine einfache Einführung in die grundlegenden algorithmischen Konzepte der Informatik. Die Konzepte werden in ihrer historischen Entwicklung und größeren Zusammenhängen dargestellt, um so die eigentliche Faszination der Informatik, die viel kontraintuitive Überraschungen bereithält, zu wecken.

1 Einleitung.- 1.1 Informatik als wissenschaftliche Disziplin.- 1.2 Eine faszinierende Theorie.- 1.3 Für die Studierenden.- 1.4 Aufbau des Lehrmaterials.- 2 Alphabete, Wörter, Sprachen und Aufgaben.- 2.1 Zielsetzung.- 2.2 Alphabete, Wörter und Sprachen.- 2.3 Algorithmische Probleme.- 2.4 Kolmogorov-Komplexität.- 2.5 Zusammenfassung und Ausblick.- 3 Endliche Automaten.- 3.1 Zielsetzung.- 3.2 Die Darstellungen der endlichen Automaten.- 3.3 Simulationen.- 3.4 Beweise der Nichtexistenz.- 3.5 Nichtdeterminismus.- 3.6 Zusammenfassung.- 4 Turingmaschinen.- 4.1 Zielsetzung.- 4.2 Das Modell der Turingmaschine.- 4.3 Mehrband-Turingmaschinen und Church sche These.- 4.4 Nichtdeterministische Turingmaschinen.- 4.5 Kodierung von Turingmaschinen.- 4.6 Zusammenfassung.- 5 Berechenbarkeit.- 5.1 Zielsetzung.- 5.2 Die Methode der Diagonalisierung.- 5.3 Die Methode der Reduktion.- 5.4 Satz von Rice.- 5.5 Das Post sche Korrespondenzproblem.- 5.6 Die Methode der Kolmogorov-Komplexität.- 5.7 Zusammenfassung.- 6 Komplexitätstheorie.- 6.1 Zielsetzung.- 6.2 Komplexitätsmaße.- 6.3 Komplexitätsklassen und die Klasse P.- 6.4 Nichtdeterministische Komplexitätsmaße.- 6.5 Die Klasse NP und Beweisverifikation.- 6.6 NP-Vollständigkeit.- 6.7 Zusammenfassung.- 7 Algorithmik für schwere Probleme.- 7.1 Zielsetzung.- 7.2 Pseudopolynomielle Algorithmen.- 7.3 Approximationsalgorithmen.- 7.4 Lokale Suche.- 7.5 Simulated Annealing.- 7.6 Zusammenfassung.- 8 Randomisierung.- 8.1 Zielsetzung.- 8.2 Elementare Wahrscheinlichkeitstheorie.- 8.3 Ein randomisiertes Kommunikationsprotokoll.- 8.4 Die Methode der häufigen Zeugen und der randomisierte Primzahltest.- 8.5 Zusammenfassung.- 9 Kommunikation und Kryptographie.- 9.1 Einleitung.- 9.2 Klassische Kryptosysteme.- 9.3 Public-Key-Kryptosysteme undRSA.- 9.4 Interaktive Beweissysteme und Zero-Knowledge-Beweise.- 9.5 Zusammenfassung.