Juraj Hromkovic - Zufall und zufallsgesteuerte Algorithmen

 entnommen aus:

Lehrstuhl für Informatik I

cs.uni-potsdam.de//Spitzenforschung

Zitat

Das erste Ziel dieses Artikels ist es, dem Leser an einem einfachen Beispiel zu zeigen, dass zufallsgesteuerte Systeme und Programme eine Leistungsfähigkeit besitzen, die deterministische nie erreichen können. 

• Das zweite Ziel ist es, anhand der "Methode der häufigen Zeugen" zum Verständnis der Berechnungsstärke zufallsgesteuerter Algorithmen beizutragen.

[...] 

 Die Physiker waren die Ersten, die auf die Idee kamen, durch zufallsgesteuerte Systeme Naturprozesse zu simulieren. 

• Der große Nutzen von Zufallssteuerung fand aber erst in der Informatik durch den Entwurf von zufallsgesteuerten Algorithmen statt. 

Was sind aber zufallsgesteuerte Algorithmen? 

• Die Programme (Algorithmen), die wir gewohnt sind, sind deterministisch. 

"Deterministisch" bedeutet, dass das Programm und die Problemeingabe die Arbeit des Programms vollständig bestimmen.  

In jedem Augenblick ist in Abhängigkeit von den aktuellen Daten eindeutig klar, was die nächste Aktion des Programms sein wird.

• Zufallsgesteuerte Programme können mehrere Möglichkeiten haben, ihre Arbeit fortzusetzen, und welcher der Möglichkeiten das Programm folgt, wird zufällig entschieden. 

Es sieht so aus,als ob ein zufallsgesteuertes Programm von Zeit zu Zeit eine Münze wirft und abhängig davon, ob Kopf oder Zahl gefallen ist, wählt es die entsprechende Strategie auf seiner Suche nach dem richtigen Resultat. 

• Auf diese Weise kann ein zufallsgesteuertes Programm mehrere unterschiedliche Berechnungen für ein und dieselbe Eingabe durchlaufen. 

• Im Unterschied zu deterministischen Programmen, wo immer eine zuverlässige Berechnung des richtigen Resultates gefordert wird, dürfen einige Berechnungen des zufallsgesteuerten Programms auch falsche Resultate liefern. 

Das Ziel ist jedoch, die Wahrscheinlichkeit einer falschen Berechnung klein zu halten, was in gewissem Sinne bedeutet, den proportionalen Anteil der Berechnungen mit falschem Resultat zu reduzieren.

[...]

 (Notiz: ... oder: ... " den proportionalen Anteil der Berechnungen mit falschem Resultat zu " erhöhen ...)

Das Galtonbrett

 

wikipedia.org//Galtonbrett

 * * *