Wir beschäftigen uns mit der Frage, wie sich die verschiedenen Aspekte des Zufalls bei dem Entwurf und der Analyse von Algorithmen auswirken. Ein Ansatz sind hier diskrete stochastische Modelle, die eine Wahrscheinlichkeitsverteilung auf dem Raum aller möglichen Inputs eines Algorithmus darstellen. Sie ermöglichen es einerseits, ein Verfahren nach seiner durchschnittlichen Leistung zu beurteilen und vermeiden auf diese Weise den übertriebenen Pessimismus von worst-case Paradigmen. Andererseits erfordern sie eine genaue Kenntnis von Struktureigenschaften, die Eingaben mit hoher Wahrscheinlichkeit besitzen.
Bei der Untersuchung dieser typischen Eigenschaften sind häufig Phasenübergänge zu beobachten. Verändert man das Wahrscheinlichkeitsmodell entlang einer (imaginären) "Zeitachse", so tauchen plötzlich neue Eigenschaften auf, während andere verschwinden. Das Verständnis einer derartigen "Evolution" ist eine wesentliche Voraussetzung für die Anpassung der Modelle an reale Fragestellungen, wie beispielsweise bei der Simulation von komplexen Netzwerken in der Informationstechnologie oder großen Datenbanken in der Bioinformatik.
English