deutsch     english     français     Drucken

 

3.10 ZUFALL

 

 

EINFÜHRUNG

 

Im täglichen Leben spielen Zufälle eine grosse Rolle. Man versteht darunter Ereignisse, die nicht voraussehbar sind. Bittet man dich etwa, aus den Farben rot, grün und blau eine Farbe zu wählen, so kann niemand voraussagen, für welche du dich entscheidest, die Farbe ist also zufällig. Auch bei Games spielt der Zufall eine grosse Rolle: Wirft du einen Würfel, so ist die Augenzahl zwischen 1 und 6 zufällig.

Obschon die Welt vom Zufall regiert wird [mehr... Die Naturgesetze werden mit der Quantentheorie
formuliert, in welcher der Zufall die zentrale Rolle spielt
] handelt es sich nicht um ein Chaos, sondern es gibt auch beim Zufall Gesetzmässigkeiten, welche gewisse Voraussagen ermöglichen. Diese gelten aber nur "im Mittel" oder anders ausgedrückt, wenn man oftmals in der gleichen Situation ist. Um die Gesetzmässigkeiten des Zufalls zu untersuchen, führt man Zufallsexperimente durch, bei denen man die Anfangsbedingungen fest vorgibt, wo aber der Ablauf durch Zufallszahlen gesteuert wird.

Für Zufallsexperimente ist der Computer hervorragend geeignet, da es sehr einfach ist, eine grosse Anzahl  von Versuchen durchzuführen. Dazu muss der Computer eine Reihe von Zufallszahlen erzeugen, die möglichst voneinander unabhängig sind. Man verwendet meist Ganzzahlen in einem gewissen vorgegebenen Bereich, z.B. zwischen 1 und 6,  oder Dezimalzahlen zwischen 0 und 1.  Einen Algorithmus, der eine Reihe von Zufallszahlen berechnet, nennt man einen Zufallszahlengenerator. Es ist wichtig, dass die Zahlen mit gleicher Häufigkeit auftreten, wie man es von einem (nicht gezinkten) Würfel her gewohnt ist. Man nennt solche Zahlen gleichverteilt [mehr... Da ein Computer nach streng determinierten Regeln arbeitet, sind die Zahlen eigentlich vorhersehbar. Man spricht deswegen von Pseudozufallszahlen].

PROGRAMMIERKONZEPTE: Zufallszahl, Zufallsexperiment, Häufigkeit, Wahrscheinlichkeit

 

 

ZUFÄLLIGES MALEN

 

Auf eine Leinwand kleckst du 20 farbige Ellipsen mit zufälliger Grösse, zufälliger Lage und zufälliger Farbe. Ob du dies als Malerei, ja gar als Kunst auffassen willst, bleibt dir überlassen. Lustig sind die Figuren alleweil. Für die Position und Grösse der Ellipsen verwendest du die Methode random() aus dem Modul random, die bei jedem Aufruf eine neue Zufallszahl zwischen 0 und 1 liefert. Um die zufälligen Farben zu erhalten, brauchst du drei ganzzahlige Zufallszahlen zwischen 0 und 255, welche die Anteile der roten, grünen und blauenFarbe festlegen. Diese erzeugst du mit der Methode randint()

 
from gpanel import *
from random import randint, random

def randomColor():
   r = randint(0, 255)
   g = randint(0, 255)
   b = randint(0, 255)
   return makeColor(r, g, b)

makeGPanel()
bgColor(randomColor())

for i in range(20):
   setColor(randomColor())
   move(random(), random())
   a = random() / 2
   b = random() / 2
   fillEllipse(a, b)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

 

 

MEMO

 

random() liefert gleichverteilte Zufallszahlen als Float zwischen 0 (eingeschlossen) und 1 (ausgeschlossen). Du musst das Modul random importieren, um darauf zugreifen zu können.

Mit randint(start, end) erhält man eine ganzzahlige Zufallszahl zwischen start und end (beide eingeschlossen). Farben werden durch ihren Rot-, Grün- und Blauanteil (RGB) festgelegt. Die Werte sind Ganzahlen zwischen 0 und 255. Die Funktion makeColor() liefert  aus den 3 Farbwerten für Rot, Grün und Blau ein Farbobjekt.

 

 

HÄUFIGKEIT VON WÜRFELZAHLEN

 
Das Zufallsexperiment besteht darin, dass du 100 Mal würfelst und dann herausfinden willst,  wie oft die Augenzahlen 1, 2, ...6, vorgekommen sind.  

Mit einem Computerprogramm kannst du das Experiment viel schneller durchführen. Anstelle des Würfelns verwendest du Zufallszahlen von 1 bis 6. Die Häufigkeitsverteilung kannst du in einem GPanel grafisch darstellen.

 


from gpanel import *
from random import randint

NB_ROLLS = 100

makeGPanel(-1, 8, -0.1 * NB_ROLLS / 2, 1.1 * NB_ROLLS / 2)
title("# Rolls: " + str(NB_ROLLS))
drawGrid(0, 7, 0, NB_ROLLS // 2, 7, 10)
setColor("red")

histo = [0, 0, 0, 0, 0, 0, 0]
# hist = [0] * 7  # short form

for i in range(NB_ROLLS):
    pip = randint(1, 6)
    histo[pip] += 1

lineWidth(5)
for n in range(1, 7):
    line(n, 0, n, histo[n])
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

 

 

MEMO

 

Die Häufigkeit, mit der die einzelnen Augenzahlen (pip) vorkommen, müssen gespeichert werden. Du verwendest dazu die Liste histo, in der du die Vorkommnisse beim entsprechenden Index aufsummierst. Du benötigst eine Liste mit 7 Elementen, da der Index von 1 bis 6 läuft.

Wie du durch einige Experimente feststellen kannst, sind die Häufigkeiten bei grösser werdenden Wurfzahlen NB_ROLLS immer besser ausgeglichen und erreichen immer genauer 1/6 der Wurfzahl. Diese Tatsache drückt man so aus: Die Wahrscheinlichkeit, beim Würfelwerfen eine der Augenzahlen zu erhalten, ist 1/6.

Für das Koordinatengitter rufst du drawGrid(xmin, xmax, ymin, ymax, xticks, yticks) mit 6 Parametern auf. Die zwei letzten Parameter bestimmen die Anzahl der Unterteilungen. Ist xmax oder ymax ein Float so erfolgt die Achsenbeschriftung ebenfalls in Floats, sonst sind es Integer.

 

 

MONTE-CARLO-SIMULATION

 

Das Fürstentum Monaco ist durch sein Casino im Stadtteil Monte-Carlo weltberühmt. Das Casino hat nicht nur seit 150 Jahren eine magische Anziehungskraft auf Berühmtheiten, sondern auch auf Mathematiker, die versuchen, die Spiele zu analysieren und Gewinnstrategien zu entwickeln. Zum Test der Strategien eignet sich der Computer besser als das reale Spiel, da man bei Computerexperimenten kein Geld verliert.

Beim folgenden "Spiel" wirfst du Punkte auf eine quadratische Fläche, auf der ein Polygon liegt. Die Punkte kannst du anschaulich auch als Regentropfen auffassen. Wie dies beim Regen üblich ist, fallen in einer gewissen Zeit ungefähr immer gleich viel Tropen auf jede Flächeneinheit. Die Tropfen sind also gleichverteilt. Du lässt eine bestimmte totale Zahl von Regentropfen fallen und zählst, wie viele davon auf die Polygonfläche fallen. Es ist offensichtlich, dass diese Zahl mit zunehmendem Flächeninhalt des Polygons zunimmt und im Mittel proportional zum Flächeninhalt ist. Beispielsweise fallen auf ein Polygon mit einem Flächeninhalt von ¼ des Flächeninhalts des umgebenden Quadrats ja wohl (im Mittel) ¼ aller Regentropfen. Aus dieser Erkenntnis kannst du nun umgekehrt durch Zählen der Tropfen den Flächeninhalt herausfinden. Ist das nicht elegant?

Das Programm ist modern und benutzerfreundlich  gestaltet. Du kannst zu Laufzeit mit einem linken Mausklicks die Eckpunkte  des Polygons  erzeugen. Klickst du dann mit der rechten Maustaste in Fläche, die du berechnen willst, so wird das Polygon gezeichnet und es beginnt zu regnen.

Das Ergebnis wird in der Titelleiste angezeigt.

 

 
from gpanel import *
from random import random

NB_DROPS = 10000

def onMousePressed(x, y):
    if isLeftMouseButton():
        pt = [x, y]
        move(pt)
        circle(0.5)
        corners.append(pt)
    if isRightMouseButton():
        wakeUp()

def go():
    global nbHit
    setColor("gray")
    fillPolygon(corners)
    setStatusText("Working. Please wait...")
    for i in range(NB_DROPS):
        pt = [100 * random(), 100 * random()]
        color = getPixelColorStr(pt)
        if color == "black":
            setColor("green")
            point(pt)
        if color == "gray" or color == "red":
            nbHit += 1
            setColor("red")
            point(pt)
    setStatusText("All done. #hits: " + str(nbHit) + " of " + str(NB_DROPS))

makeGPanel(0, 100, 0, 100, mousePressed = onMousePressed)
addStatusBar(30)
setStatusText("Select corners with left button. Start dropping with right button")
bgColor("black")
setColor("white")
corners = []
nbHit = 0
putSleep()
go()
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

 

 

MEMO

 

Beim Klicken der linken Maustaste speicherst du die Eckpunkte des Polygons in einer Liste corners und zeichnest als Markierung kleine Kreise.

Die eigentliche Regensimulation wird in der Funktion go() durchgeführt. Sie beginnt beim Klicken der rechten Maustaste und dauerst eine gewisse Zeit. Dabei machst du mit verschieden farbigen Punkten die fallenden Regentropfen sichtbar. Rufst du, wie es eigentlich auf der Hand liegt, go() im pressCallback() direkt auf, so siehst du nichts, bis die Simulation zu Ende ist. Das System unterbindet nämlich aus systeminternen Gründen das Auffrischen der Grafik in einem Maus-Callback. Willst du also in einem Callback eine länger dauernde Aktion sichtbar machen, so muss dies in einem anderen Teil des Programms geschehen. Oft wird der Hauptblock des Programms dazu verwendet. Die Ausführung wird mit putSleep() vorübergehend angehalten. Der Press-Event weckt das schlafende Hauptprogramm mit wakeUp() auf und dieses führt nun die Simulation mit dem Aufruf von go() aus.

Um Schwierigkeiten zu vermeiden, solltest du dich in Zukunft unbedingt an das folgende Prinzip halten:

Callbacks müssen immer rasch zurückkehren. Es dürfen darin keine lange dauernde Aktionen ausgeführt werden.

Um herauszufinden, ob ein Regentropfen auf die grau gefärbte Polygonfläche gefallen ist, wendest du folgenden Trick an:  Du holt dir mit getPixelColorStr() die Farbe der Auftreffstelle. Ist die Farbe grau (oder rot, wenn bereits ein anderer Tropf dort hingefallen ist), so erhöhst du nbHit um 1 und färbst die Stelle rot.

Du kannst das Verfahren testen, indem du einige einfache Polygone (z.B. Rechtecke, Dreiecke) erzeugst und mit dem Massstab den Bildschirm ausmisst. Du erkennst dann, dass es sehr viele Regentropfen braucht, um ein einigermassen exaktes Resultat zu erhalten [mehr... Es gilt etwa: Für 1 Kommastelle bessere Genauigkeit (Faktor 10),
brauchst du 100 mal mehr Punkte
].

 

 

CHAOS-SPIEL

 

Es ist auf den ersten Blick erstaunlich, dass sich mit Zufallsexperimenten regelmässige Muster erzeugen lassen. Dies hängt damit zusammen, dass sich die statistischen Schwankungen bei grossen Zahlen ausgleichen. [mehr... Obschon die zu Grund liegenden Naturgesetze auf der Quantentheorie basieren
und darum statistisch sind, bemerken wir davon im täglichen Leben wenig
]. Michael Barnsley hat 1988 im Rahmen der Chaos-Theorie den folgenden Algorithmus erfunden, der auf einer zufälligen Auswahl der Eckpunkte eines Dreiecks aufbaut:

1. Konstruiere ein gleichseitiges Dreieck mit den Ecken A, B, C
2. Wähle einen Punkt P im Innern
3. Wähle zufällig einen der Eckpunkte
4. Halbiere die Verbindungsstrecke von P zum Eckpunkt. Dies gibt den neuen Punkt P
5. Zeichne den Punkt P
6. Wiederhole Schritt 2, 3, 4, 5

Eine solche Formulierung ist umgangssprachlich üblich, lässt sich aber nicht direkt in Programmcode übersetzen, da der Punkt 6 verlangt, dass man wieder zum zu Punkt 3 springen soll. In vielen modernen Programmiersprachen, so auch in Python, gibt es aber keine Sprung-Struktur (kein goto). Sprünge müssen mit einer der Wiederholstrukturen implementiert werden. [mehr... Der bekannte Informatiker E. Dijkstra hat bereits 1968 in einem
vielzitierten Artikel vor der Verwendung von goto gewarnt.
[Lit: Dijkstra: Go To Statement Considered Harmful, Communications of the ACM]
].

 
from gpanel import *
from random import randint

MAXITERATIONS = 100000
makeGPanel(0, 10, 0, 10)

pA = [1, 1]
pB = [9, 1]
pC = [5, 8]

triangle(pA, pB, pC)
corners = [pA, pB, pC]
pt = [2, 2]

title("Working...")
for iter in range(MAXITERATIONS):
   i = randint(0, 2)
   pRand = corners[i]
   pt = getDividingPoint(pRand, pt, 0.5)
   point(pt)
title("Working...Done")
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)

 

 

MEMO

 

Benötigst du ein zufälliges Objekt, so fügst du alle Objekte in eine Liste und holst mit einem zufälligen Index eines davon heraus.

Es ist erstaunlich, dass du mit zufällig gewählten Punkten eine regelmässige Figur, nämlich ein Sierpinski-Fraktal, erzeugen kannst.

 

 

AUFGABEN

 

1.


5 Kinder treffen sich auf dem Pausenhof und fragen sich nach dem  Monat, in welchem sie Geburtstag haben. Es ist erstaunlich, dass die Wahrscheinlichkeit, dass mindestens zwei den gleichen Geburtstagsmonat haben, relativ gross ist.

Erstelle eine Simulation mit 100 Zufallsversuchen, um diese Wahrscheinlichkeit experimentell zu bestimmen. Zeige zur Veranschaulichung für jeden Versuch in einem GPanel zwölf rechteckige Monatsbehälter und zeichne die Kinder durch Kugeln dargestellt ein. Das Resultat der Versuchsreihe kann in der Titelzeile ausgeschrieben werden.

 



2.


Beim Ballspiel werfen 10 Kinder einer ersten Mannschaft gleichzeitig den Ball auf 10 Kinder der zweiten Mannschaft und treffen immer ein Kind. (Die Bälle sollen sich nicht gegenseitig beeinflussen.) Die getroffenen müssen ausscheiden. Wie viele der zweiten Mannschaft bleiben im Mittel im Spiel?

Erstelle eine Simulation mit 100 Zufallsversuchen, um diese Zahl experimentell zu bestimmen. Zeige zur Veranschaulichung für jeden Versuch in einem GPanel die beiden Mannschaften als gefüllte Kreise und zeichne die Ballrichtungen als Strecken ein. Das Resultat der Versuchsreihe kann in der Titelzeile ausgeschrieben werden.



 



3.
Du kannst mit der Monte-Carlo-Simulation sogar die Fläche von beliebigen Figuren zu bestimmen. Mit gedrückter linker Maustaste zeichnest du die Umrandung als Freihandlinie. Durch Klicken mit der rechten Maustaste auf einen Punkt im Inneren wird die Fläche gefüllt und die Simulation durchgeführt.

 

4.

Führe das Chaos-Spiel mit einem Quadrat aus. Wähle die Eckpunkte pA(0, -10), pB(10, 0), pC(0, 10), pD(-10, 0) und einen beliebigen Punkt pt im Innern.

Teile die Strecken von einem beliebig gewählten Eckpunkt zu pt mit dem Teilungsfaktor 0.45
(pt = getDividingPoint(corner, pt, 0.45)).