Spiele,
Simulation und dynamische Systeme
|
Fibonaccis Kaninchenaufgabe
Die Zahlenfolge 1, 1, 2, 3, 5, 8, 13, ... heißt Fibonacci-Folge. Sie löst
die folgende "Kaninchenaufgabe" des Leonardo Pisano (genannt
Fibonacci) aus dem Jahre 1202 (Knuth, 1973, S. 78):
Wieviele Kaninchenpaare kann ein Kaninchenpaar im Laufe eines Jahres erzeugen?
Angenommen wird dabei, dass jedes fruchtbare Kaninchenpaar nach jedem Monat ein
Paar Nachkommen hat. Die Kaninchenpaare werden einen Monat nach ihrer Geburt
fruchtbar und sterben nicht. Wir haben es hier mit einem frühen Beispiel für
Populationsdynamik zu tun.
Die „Kaninchenaufgabe“ läßt sich übersetzen (genaue Erklärung s. lösungen.doc)
in die Rekursionsformel: an+1 = an + an-1 für
n>1, die auf die Fibonacci-Folge führt.
Wir wollen die Erzeugung dieser Folge als ein einfaches Simulationsexperiment ansehen und daran die Anwendung des Werkzeugs Tabellenkalkulation studieren. Aber vorab wollen wir eine Prognose - ganz im Sinne der negativen Methode - wagen. Wir fragen uns, wie groß ein ebener Kaninchenstall wohl sein muss, wenn er alle Kaninchen aufnehmen soll, die am Ende von drei Jahren existieren. Reicht ein Fußballfeld aus? Bitte notieren Sie - ohne viel herumzurechnen - Ihre Einschätzung.
Und nun zur Simulation: Wir legen ein Arbeitsblatt an - beispielsweise mit dem Programm Excel. Ein Arbeitsblatt ist eine zweidimensionale Matrix aus Zellen, die eindeutig mit einer Buchstaben-Zahlenkombination adressierbar sind: C5 ist die Adresse der Zelle in der Spalte C (das ist die dritte Spalte) und in der 5. Zeile.
Einträge in diese Zellen sind Texte, Werte (Zahlen) oder Formeln. Texte und Zahlen werden im Arbeitsblatt direkt dargestellt. Formeln hingegen werden im Hintergrund gehalten; die Formel einer Zelle wird in einer gesonderten Zeile nur dann sichtbar, wenn die Zelle mit dem Zeiger (auch: Zellzeiger, Cursor) ausgewählt ist. Man kann auch die Ansicht Formeln wählen, dann erscheinen in den Zellen anstelle der Zahlenwerte die Formeln (Dazu wählt man im Excel-Menü Extras/Optionen/Ansicht und setzt dort die Auswahl Formeln).
Formeln werden von Texten durch das erste Zeichen unterschieden. In Excel beginnen die Formeln mit dem Gleichheitszeichen.
|
A |
B |
C |
D |
E |
F |
G |
1 |
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
4 |
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
Aufbau des Arbeitsblattes
(markiert ist die Zelle C5)
Zur Simulation der Kaninchenaufgabe schreiben wir in die Zellen A1 und A2 jeweils die Zahl 1, sie steht für das erste Kaninchenpaar, das nach einem Monat fruchtbar wird und deshalb im zweiten Monat noch keine Nachkommen haben kann. In die Zelle A3 kommt die Formel =A1+A2. Dieser Formel besagt, dass die Kaninchenpaare, die bereits vor zwei Monaten da waren, jetzt jeweils ein Paar Nachkommen hat, dieses Paar Nachkommen wird gezählt. Dazu kommen alle die Kaninchen, die bereits im Vormonat da waren.
Die Zelleneinträge können mit Kopier- und Verschiebeoperationen in andere Zellen transportiert werden. Wir kopieren den Inhalt der Zelle A3 in die darunterliegenden Zellen A4, A5, ..., A100. In A4 steht nun nicht dieselbe Formel wie in A3, sondern dort finden wir die Formel =A2+A3. Der Rechner hat uns also die Arbeit abgenommen, die Formel an die neue Umgebung anzupassen. Analog in den Zellen weiter untern: In den Formeln sind die Bezüge auf die Zeilenadressen mit verschoben worden. In den Zellen A1 bis A100 werden nun die ersten hundert Zahlen der Fibonacci-Folge sichtbar.
Nun sehen wir uns die Programmierung des Arbeitsblattes noch etwas genauer an: Wenn sich die Adressbezüge entsprechend einer Verschiebung ändern, spricht man von relativer Adressierung. Ist eine Änderung der Adressbezüge beim Kopieren oder Verschieben nicht erwünscht, muss der entsprechende Adressbestandteil (Spalten- oder Zeilenadresse) durch Vorstellen eines $-Zeichens absolut gemacht werden. Wird im obigen Arbeitsblatt zur Erzeugung von Fibonaccizahlen in die Zelle A3 die Formel =A$1+A$2 geschrieben und der Inhalt dann in die darunterliegenden Zellen kopiert, erscheint in allen Zellen ab A3 stets derselbe Wert, nämlich 2. Das ist die Summe der Inhalte der ersten beiden Zellen.
|
A |
B |
C |
1 |
1 |
|
|
2 |
1 |
|
|
3 |
=A1+A2 |
|
|
4 |
=A2+A3 |
|
|
5 |
=A3+A4 |
|
|
6 |
=A4+A5 |
|
|
Arbeitsblatt zur Erzeugung der
Fibonacci-Zahlen: Die Formeln im Hintergrund
|
A |
B |
C |
1 |
1 |
|
|
2 |
1 |
|
|
3 |
2 |
|
|
4 |
3 |
|
|
5 |
5 |
|
|
6 |
8 |
|
|
Arbeitsblatt zur Erzeugung der
Fibonacci-Zahlen: Die sichtbaren Werte
Man kann weiterhin "wichtigen" Zellen im Namenfeld (oben links über dem Arbeitsblatt) einen "sprechenden" Namen geben: Zelle anklicken – Namensfeld anklicken und Namen eingeben – Return.
Über die Berechnungsreihenfolge der Formeln braucht sich der Anwender heutiger Tabellenkalkulationsprogramme keine Gedanken mehr zu machen. Wird irgendeine Zelle mit einem neuen Wert oder einer neuen Formel versehen, erfolgt im allgemeinen eine Neuberechnung des Arbeitsblattes. Dabei nimmt sich das Tabellenkalkulationsprogramm die Formeln in einer Reihenfolge vor derart, dass bei jeder Auswertung grundsätzlich nur auf bereits aktualisierte Werte zurückgegriffen wird (topologische Sortierung der Zellen). Ausnahme von dieser Regel bilden die sogenannten zirkulären Verweise, die wir aber vermeiden wollen.
Weitere Excel-Hinweise:
o
Mit dem Funktionsassistenten () erhält man
einen Überblick und Hilfe zu den verfügbaren Excel-Funktionen
o Mit F9 erzwingt man eine Neuberechnung (auch Neu-Würfeln aller Zufallszahlen)
o
Mit dem Diagrammassistenten () kann man
recht schnell eine Grafik erstellen
o Einen Bereich mit Formeln ausfüllen: auf eine Formelzelle klicken, mit Cursor am Quadrat unten rechts aufziehen.
Übung: In einem
Tabellenblatt sollen – bei parametrierbarer Schrittweise x im Bogenmaß – 100 Werte der Funktion berechnet werden,
startend bei einem parametrierbaren Startwert x0. Dies ist zu
vergleichen mit der Taylor-Näherung 1 - (K1x)2/2 + (K1x)4/24
und der relative Fehler zu berechnen. K1 soll als "sprechender
Name" in den Formeln erscheinen. Die Funktionen und der Fehler sind
graphisch zu visualisieren.
Beurteilung des Simulationswerkzeugs
Tabellenkalkulation
Anwendungsbereich: Die Tabellenkalkulation ist das "Taschenmesser unter den Simulationswerkzeugen". Auf praktisch jedem Rechner ist ein Tabellenkalkulationsprogramm verfügbar; Tabellenkalkulationsprogramme sind leicht zu bedienen; Simulationsaufgaben lassen sich ohne Umschweife und unnötigen Ballast lösen, und für die Ergebnispräsentation steht die eingebaute - meist sehr komfortable - Grafik zur Verfügung.
Man wird die Tabellenkalkulation für den ersten Einstieg in eine Simulationsproblematik nutzen und auch zur Demonstration von Simulationsmethoden in der Ausbildung. Auf diesen Gebieten ist die Tabellenkalkulation wegen ihrer Einfachheit und Transparenz nahezu unschlagbar.
Systeme geringer Ordnung, beispielsweise Ökosysteme mit einer, zwei oder drei Populationen, lassen sich ohne weiteres bewältigen. Damit erfasst der Anwendungsbereich beispielsweise sämtliche Systeme, die im Buch von Bossel (1992) untersucht werden.
Lassen sich die Beziehungen zwischen den Zustandsgrößen des Systems nach einheitlichen Regeln formulieren, dann kann man auch noch umfangreichere Systeme mit der Tabellenkalkulation angehen. Die Eingabe lässt sich dann durch geschicktes Jonglieren mit relativer und absoluter Adressierung auf ein Mindestmaß reduzieren. Es entstehen dabei zwar umfangreiche aber gleichförmige Arbeitsblätter. Ein Arbeitsblatt gilt als gleichförmig, wenn seine Zellinhalte im Wesentlichen durch Kopieroperationen auseinander hervorgehen (Hayes, 1984).
Programmiertechnik: Bereits das obige Arbeitsblatt zur Fibonacci-Zahlenfolge zeigt:
Dass die Arbeitsblätter schlecht lesbar sind,
liegt zum einen an der Adressierungsmethode: Beispielsweise steht
"$C$5" anstelle eines mnemotechnisch günstig gewählten Parameter-
oder Variablennamens. Dem kann man allerdings abhelfen, indem man
"wichtigen" Zellen im Namenfeld
(oben links über dem Arbeitsblatt) einen "sprechenden"
Namen gibt.
Das Hauptproblem ist aber, dass die Formeln im
Hintergrund gehalten werden und der Algorithmus nicht als fortlaufender Text
wie bei einer höheren Programmiersprache erscheint. Der zugrunde liegende
Algorithmus lässt sich im fertigen Arbeitsblatt nur noch schwer entdecken. Die
Struktur oder der Ablaufplan (welche Reihenfolge, beeinflußt Zelle A5 die Zelle
A2 oder ist es umgekehrt?) läßt sich nur schwer erschließen. Große
Arbeitsmappen werden so leicht zu "Formeltapeten".
Modularität im Sinne der höheren Programmiersprachen
oder der allgemeinen Simulationssysteme gibt es nicht. Strukturänderungen
verlangen normalerweise eine komplette Überarbeitung des Arbeitsblattes. Das
bestätigt erneut, dass die Tabellenkalkulation für die Simulation großer
Systeme (das sind Systeme mit vielen Zustandsgrößen) nicht geeignet ist.
Die Frage nach der Speichereffizienz ist nicht
losgelöst vom gewählten mathematisch-numerischen Verfahren zur Lösung der
Systemgleichungen zu beantworten, ebenso die Fragen nach der Verlässlichkeit
der Ergebnisse. Aufwand und Rechengenauigkeit werden bei den Experimenten zur
Populationsdynamik kurz angesprochen.
Durchführung von Experimenten: Das Experimentieren mit Tabellenkalkulationsprogrammen ist
recht einfach. Parameteränderungen werden direkt in den entsprechenden
Speicherzellen durchgeführt. Die automatische Neuberechnung des Arbeitsblattes
sorgt dafür, dass sofort ein neues Berechnungsexperiment gestartet wird.
Allerdings lässt sich das vollautomatische Abspulen von Experimentsequenzen
nicht realisieren. Auch Optimierungen sind nur "von Hand" möglich.
Dokumentation: Die Ergebnisdarstellung und die Protokollierung werden
durch die Grafikfunktionen der Tabellenkalkulation gut unterstützt.
Schließlich wollen wir die anfangs gestellte Frage beantworten: Nach drei Jahren sind rund 15 Mio. Hasen im Stall (Zelle A36). Selbst wenn jeder Hase nur Anspruch auf eine Fläche von 50 cm mal 25 cm hat, benötigt man wenigstens 262 Fußballfelder (der Größe 68m x 105m), um alle unterzubringen. Haben Sie das erwartet? Wenn nein: Was lässt sich daraus lernen?
Diskussion und Übungen
Denken Sie bei allen Übungen an die negative Methode: erst
Erwartung an die Simulation formulieren und festhalten, dann simulieren!
1.
Die
Rekursion konvergiert, abhängig vom Startwert a0,
gegen
oder
. Überprüfen
Sie dies durch eine Simulation mit Tabellenkalkulation. Für welche Startwerte
ergeben sich welche Fixpunkte?
2. Allgemeiner führt die Rekursion auf den Fixpunkt
.
Überprüfen Sie auch das durch Simulation mit Tabellenkalkulation. Führen Sie
dabei für die Konstanten "sprechende"
Namen ein, damit die Formeln übersichtlich bleiben. Ist auch die Variante geeignet, die
zu berechnen?
Prüfen Sie es durch Simulation mit
verschiedenen Startwerten nach. Erklärung?
3. Simulation
mit Zufall: Mit der Formel
=RUNDEN(ZUFALLSZAHL()*6+0.5;0)
erzeugt man eine Zufallszahl zwischen 1 und 6. Mit der Formel
=WENN(UND(B6=3;C6<=3);1;0)
schreibt man eine 1 genau dann, wenn der Inhalt der Zelle B6 3 und der der
Zelle C6<=3 ist, sonst 0. Mit der Formel
=SUMME(D6:D20)/ANZAHL(D6:D20)
zählen Sie die Häufigkeit der 1 im Bereich D6:D20 im Vgl. zur Anzahl der Zellen
im Bereich, die nicht leer sind (Nichtleere Zellen sollten 1 oder 0 enthalten).
Lösen Sie mit diesen Informationen folgende Fragestellung durch Simulation mit
Tabellenkalkulation: Wie groß ist die Wahrscheinlichkeit, mit 2 Würfeln
einen 1er-, 2er- oder 3er-Pasch zu würfeln?
Wieviel Versuche braucht man, damit die Simulation im Schnitt auf 1% genau an
das wahre Ergebnis herankommt (erst schätzen, dann ausprobieren!). Eine grobe
Schätzung genügt: 10, 100, 1000, 5000, ...
(würfel.xls.zip,
Blatt Würfel)
4. (optional,
anspruchsvoller) Halbkreis: Simulieren Sie das Halbkreis-Problem
aus der Einführung mittels Tabellenkalkulation. Die
Tabellenkalkulation soll dabei ermöglichen, dass Sie viele Experimente auf
einen Schlag durchführen können. Wieviele Versuche braucht man, um die exakte
Erfolgswahrscheinlichkeit im Schnitt auf 1% genau anzunähern?
(HINWEIS: Betrachten Sie die Differenzwinkel zwischen zwei benachbarten
Punkten. Welche Bedingung an die Differenzwinkel ermöglicht die
Halbkreisüberdeckung?)
(würfel.xls.zip,
Blatt Halbkreis. Mathematische Analyse s. Halbkreis-loesung.doc
und ungerade_gewinnt.doc.)
Zurück zur Gliederung editieren
|
© Timm Grams, 6.7.1999
© W. Konen, 2004 – 2009