Randomisierte Algorithmen

Zufall ist ein erfolgreiches Mittel für Entwurf und Entwicklung vieler Systeme in Informatik und Technik. Zufallsgesteuerte Algorithmen sind oft effizienter, einfacher, preiswerter und überraschenderweise auch zuverlässiger als die besten deterministischen Programme. Warum ist die Zufallssteuerung so erfolgreich und wie entwirft man randomisierte Systeme? Einfach, intuitiv und trotzdem formal präzise gibt dieses Buch dem Leser einen Einstieg in die wunderbare Welt zufallsgesteuerter Algorithmen.

1 Einleitung.- 1.1 Was ist Zufall und gibt es überhaupt echten Zufall?.- 1.2 Zufall als Quelle der Effizienz ein Beispiel zur Motivation.- 1.3 Das Konzept des Buches.- 1.4 Für die Studierenden.- 1.5 Für die Lehrenden.- 2 Grundlagen.- 2.1 Zielsetzung.- 2.2 Elementare Wahrscheinlichkeitstheorie.- 2.3 Modellierung von randomisierten Algorithmen.- 2.4 Klassifizierung von randomisierten Algorithmen.- 2.5 Klassifizierung von randomisierten Algorithmen für Optimierungsprobleme.- 2.6 Paradigmen für den Entwurf randomisierter Algorithmen.- 2.7 Zusammenfassung.- 3 Überlisten des Gegners.- 3.1 Zielsetzung.- 3.2 Hashing.- 3.3 Universelles Hashing.- 3.4 Online-Algorithmen.- 3.5 Randomisierte Online-Algorithmen.- 3.6 Zusammenfassung.- 4 Die Methode der Fingerabdrücke.- 4.1 Zielsetzung.- 4.2 Kommunikationsprotokolle.- 4.3 Das Teilstringproblem.- 4.4 Verifikation der Matrixmultiplikation.- 4.5 Äquivalenz von zwei Polynomen.- 4.6 Zusammenfassung.- 5 Wahrscheinlichkeitsverstärkung durch Wiederholungen und die Stichprobenmethode.- 5.1 Zielsetzung.- 5.2 Effiziente Wahrscheinlichkeitsverstärkung durch Wiederholungen von Berechnungsteilen.- 5.3 Wiederholte Stichproben und Erfüllbarkeit.- 5.4 Stichproben und Generierung von nicht-quadratischen Resten.- 5.5 Zusammenfassung.- 6 Die Methode der häufigen Zeugen.- 6.1 Zielsetzung.- 6.2 Suche nach Zeugen für den Primzahltest.- 6.3 Der randomisierte Primzahltest von Solovay und Strassen.- 6.4 Generierung von zufälligen Primzahlen.- 6.5 Zusammenfassung.- 7 Optimierung und zufälliges Runden.- 7.1 Zielsetzung.- 7.2 Relaxation zur linearen Programmierung.- 7.3 Zufälliges Runden und MAX-SAT.- 7.4 Eine Kombination von Stichproben mit zufälligem Runden.- 7.5 Zusammenfassung.- A Mathematische Grundlagen.- A.1 Zielsetzung.- A.2 Algebraund Zahlentheorie.- A.3 Kombinatorik.- A.4 Zusammenfassung.