Skip to main content
main-content

Inhaltsverzeichnis

Frontmatter

1. Einleitung

Zusammenfassung
Der Begriff Zufall ist einer der fundamentalsten und meist diskutierten Begriffe der Wissenschaft. Der Definition aus Wörterbüchern folgend, bezeichnet man eine Erscheinung als zufällig, wenn sie ohne Plan und unvorhersehbar eintritt. Ein Objekt wird als zufällig eingestuft, wenn es ohne Plan und ohne jedes Muster entstanden ist oder hergestellt wird. Die grundlegende Frage ist, ob der Zufall objektiv existiert oder ob wir diesen Begriff nur benutzen, um Ereignisse mit uns unbekannter Gesetzmäßigkeit zu erklären und zu modellieren. Darüber streiten die Wissenschaftler seit der Antike. Demokrit glaubte, dass
„das Zufällige das Nichterkannte ist, und dass die Natur in ihrer Grundlage determiniert ist.“
Damit meinte er, dass in der Welt eine feste Ordnung herrscht und dass diese Ordnung durch eindeutige Gesetze bestimmt wird. Nach Demokrit benutzt man den Begriff Zufall nur im subjektiven Sinne, um den Unverstand über die Dinge und Ereignisse zu verschleiern. Somit wäre die Existenz des Begriffs der Zufälligkeit nur eine Folge der Unvollständigkeit unserer Kenntnisse. Seinen Standpunkt illustrierte Demokrit gerne mit folgendem Beispiel. Zwei Herren schicken ihre Sklaven absichtlich um die gleiche Zeit zum Brunnen, um Wasser zu holen. Die Sklaven treffen sich beim Brunnen und sagen „Oh, was für ein Zufall, dass wir uns getroffen haben.“ Doch dieses Treffen wurde durch die Entscheidung der Herren determiniert, aber ohne es zu wissen, scheint dies den Sklaven ein zufälliges Ereignis zu sein.
Juraj Hromkovič

2. Grundlagen

Zusammenfassung
Die Zielsetzung dieses Kapitels liegt darin, die grundlegenden Bausteine für den Entwurf von randomisierten Algorithmen zu vermitteln. Wir beginnen in Abschnitt 2.2 mit der Einführung in die grundlegenden Konzepte der Wahrscheinlichkeitstheorie und definieren die fundamentalen Begriffe wie elementare Ereignisse, Ereignisse, Wahrscheinlichkeitsraum, Zufallsvariable und Erwartungswerte von Zufallsvariablen. Wir beschränken uns hier auf endliche Wahrscheinlichkeitsräume, weil dies in den meisten Fällen für die Modellierung von randomisierten Berechnungen hinreichend ist. Außerdem können wir so die recht unanschaulichen Abstraktionen der Maß Theorie vermeiden.
Juraj Hromkovič

3. Überlisten des Gegners

Zusammenfassung
Die Methode des Überlistens des Gegners (Widersachers) steht im Hintergrund aller randomisierten Algorithmen. Die Zielsetzung dieses Kapitels ist es, diese Methode für einige Problemstellungen vorzustellen, für die sie sogar im Vordergrund des Algorithmenentwurfs steht. Dies geschieht gerade in den Situationen, in denen
(i)
jeder deterministische Algorithmus Worst-Case-Eingaben hat, in denen er nicht effizient zu einer korrekten Ausgabe gelangen kann,
 
(ii)
es aber eine Klasse von deterministischen Verfahren gibt, so dass für jede zulässige Eingabe die meisten Verfahren aus dieser Klasse effizient das korrekte Resultat berechnen.
 
Juraj Hromkovič

4. Die Methode der Fingerabdrücke

Zusammenfassung
Dieses Kapitel ist der Anwendung der Methode der Fingerabdrücke gewidmet. Wir haben diese Methode im Abschnitt 2.6 als einen Ansatz zur Lösung von Aquivalenzproblemen vorgestellt. Die Grundidee ist dabei, zwei vollständige zum effizienten Vergleich zu komplexe Darstellungen von Objekten durch Fingerabdrücke dieser Darstellungen zu vergleichen. Dabei können die Fingerabdrücke auf mehrere Arten erzeugt werden. Im Motivationsbeispiel aus Kapitel 1 entspricht zum Beispiel die Rechnung modulo p für jede Primzahl p < n2 einer Art, den Fingerabdruck zu gewinnen. Die Art des Fingerabdrucks wird aus einer endlichen Menge von Möglichkeiten zufällig gewählt. Wir stellen die folgenden beiden Anforderungen an die Fingerabdrücke.
Juraj Hromkovič

5. Wahrscheinlichkeitsverstärkung durch Wiederholungen und die Stichprobenmethode

Zusammenfassung
Dieses Kapitel widmen wir zwei Paradigmen des Entwurfs von randomisierten Algorithmen — nämlich der Wahrscheinlichkeitsverstärkung durch wiederholte Läufe auf der gleichen Eingabe und der Methode der Stichproben. Der Grund dafür, beide Methoden gemeinsam vorzustellen liegt darin, dass sie beim Algorithmenentwurf oft so verflochten sind, dass man nicht entscheiden kann, welche der beiden maßgeblicher für den Erfolg des entworfenen randomisierten Algorithmus ist.
Juraj Hromkovič

6. Die Methode der häufigen Zeugen

Zusammenfassung
Die Methode der häufigen Zeugen ist ein wahres Schmuckstück des Entwurfs von randomisierten Algorithmen. Nicht nur weil sie oft tiefgreifende Überlegungen und die Anwendung von nichttrivialen Resultaten erfordert, sondern insbesondere auch weil sie direkt mit der Frage verknüpft ist, ob Randomisierung effizienter als Determinismus sein kann.
Juraj Hromkovič

7. Optimierung und zufälliges Runden

Zusammenfassung
Das Problem der ganzzahligen linearen Programmierung (ILP; integer linear programming) und das Problem der 0/1-linearen Programmierung (0/1-LP) sind bekannte NP-schwere Optimierungsprobleme. Auf der anderen Seite ist das Problem der linearen Programmierung (LP) in Polynomialzeit lösbar. Dabei haben alle drei Probleme die gleichen Optimierungsziele und die gleichen linearen Einschränkungen. Der einzige Unterschied liegt in der Forderung nach ganzzahligen Lösungen für ILP und nach Booleschen Lösungen für 0/1-LP, wohingegen das Basisproblem der linearen Programmierung mit reellen Zahlen1 arbeitet.
Juraj Hromkovič

Backmatter

Weitere Informationen