Navigation

Abschlussaufgabe

Auf der Grundlage Ihrer Lösung der Abschlussaufgabe werden wir Ihre Noten festlegen.
Wer keine Abschlussaufgabe abgibt, kann

  • von mir entweder einen unbenoteten Teilnahmenachweis bekommen, der aber nicht als Studienleistung angerechnet werden kann
  • oder wahlweise (bei erfolgreicher Teilnahme an den Übungen) eine Benotung mit "Ausreichend" bekommen.

Spielregeln:

  • Die Abschlussaufgabe wird in Einzelarbeit gelöst.
  • Hilfsmittel (z.B. Matlab-Hilfe, Wikipedia...) sind erlaubt (solange es sich nicht um andere Kursteilnehmer, den grossen Bruder oder eine fertige aus dem Netz gezogene Lösung handelt).
  • Bei Fragen stehen die TutorInnen Leon Juarez Paz l.m.juarez.paz@uol.de (Raum W4-0-058, Tel 798 3314) und Nicole Cichon nicolecichon@hotmail.com (Raum W4-0-046, Tel 798 3339) und ich jutta.kretzberg@uol.de (Raum W4-0-058, Tel 798 3314) zur Verfügung.
  • Ich akzeptiere auch Teilloesungen und nicht in Programmcode umgesetzte Loesungsideen. Allerdings haette ich bei nicht lauffaehigen Programmen gerne eine ausfuehrliche Dokumentation, was nicht laeuft.
  • Lösungen müssen bis zum 5.10.2008 per email bei mir eingehen: jutta.kretzberg@uol.de
  • Ich melde mich per email, wenn ich die Aufgaben nachgesehen habe und vergebe dann Termine, an denen wir uns noch einmal kurz darüber unterhalten.


Kriterien für die Benotung sind:

  • Wie vollständig ist die Aufgabe gelöst?
  • Wie „elegant“ ist die Lösung?
  • Wie allgemein gehalten ist sie?
  • Ist das Programm gut kommentiert und dokumentiert?
  • Wie benutzerfreundlich ist das Programm?
  • Wieviel ist an Zusatzideen und Detailarbeit in die Programme eingeflossen? (Hier sind beliebige Erweiterungen  moeglich, aber man kann auch mit einer schlichten Loesung ein „sehr gut“ bekommen.)


... und hier die Aufgabe:

Abschlussaufgabe: Spiel des Lebens

Das "Spiel des Lebens" wurde im Jahr 1970 vom Mathematiker John Horton Conway erdacht (Hintergrundinformation: http://de.wikipedia.org/wiki/Conways_Spiel_des_Lebens). Ich möchte es hier als eine sehr einfache Simulation einer Bakterienkultur ansehen.

Der Ausgangspunkt dieser Simulation ist eine "Petrischale" mit NxM Plätzen, die  entweder leer oder mit einer lebenden Bakterie besetzt sind. Am Anfang sind P Plätze mit lebenden Bakterien besetzt, das sieht dann z.B. für eine schön symmetrisch Ausgangssituation so aus (lebende Bakterien sind blau, leere Plätze weiss dargestellt):

                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       
                                       

 

Ausgehend von dieser Startsituation wird nun der Zustand der Bakterienkultur in diskreten Zeitschritten verändert. In jedem Zeitschritt wird für jeden der Plätze in der  "Petrischale" bestimmt, ob sich dort eine lebende Zelle befindet oder nicht. In der Originalversion von Convay ist dafür ausschließlich ausschlaggebend, wieviele der 8 Nachbarplätze mit lebenden Zellen gefüllt sind. Eine Implementation von Convays deterministischer Version des "Game of Life", bei der Bakterien die sich rechts aus dem Bildschirm bewegen links wieder herauskommen, kann man in den Matlab Demos finden. (Diese dürfen Sie verwenden - müssen Sie aber nicht.)

Durch diese einfachen Regeln ergibt sich eine erstaunlich komplexe "Populationdynamik" (oder - wenn man nicht bereit ist, dieses einfache Regelwerk als biologisch zu interpretieren - zumindest sehr hübsche Muster), z.B. so:

Bild


Wir wollen eine etwas "biologischere" Simulation einer Bakterienkultur angehen, bei der der Lebensraum der Bakterien auf eine endliche "Petrischale" begrenzt ist und bei der Überleben und Teilung von Bakterien stochastisch ablaufen. (Deshalb sind die entstehenden Muster sicher nicht mehr so schön symmetrisch, können aber trotzdem interessant anzusehen sein.)

Grundaufgabe:

Programmieren Sie das Spiel des Lebens, so dass sie sich die Simulation für folgende Ausgangssituationen jeweils Z Zeitschritte lang ansehen können (in den Matrizen steht 1 für eine lebende Zelle, 0 für einen leeren Platz):

 Anordnung als Ring:  Bild  ring.mat
 Anordnung als Schachbrett:  Bild  schach.mat
 Zufällige Anordnung
 Bild  zufall.mat

 

Schreiben Sie ausserdem ein Programm, das als Startbedingung für das Spiel des Lebnes B Bakterien zufällig auf einer NxM grossen Petrischale verteilt.

Implementieren Sie die Populationsdynamik schrittweise nach den folgenden (immer komplexer werdenden) Regeln:

a) Standardregeln:

  • Eine lebende Zelle hat 90% Wahrscheinlichkeit, im nächsten Zeitschritt noch zu leben.
  • Eine lebende Zelle hat in jedem Zeitschritt 11.5% Wahrscheinlichkeit sich zu teilen. Dabei ist die Richtung der Teilung (also welcher der 8 Nachbarplätze mit einer neuen Zelle belegt wird) zufällig mit gleicher Wahrscheinlichkeit für alle Plätze. 

b) Nachbarregeln:

  • Eine lebende Zelle hat 90% Wahrscheinlichkeit, im nächsten Zeitschritt noch zu leben.
  • Ein leerer Platz mit genau zwei oder drei lebenden Nachbarn hat 15% Wahrscheinlichkeit, im nächsten Zeitschritt gefüllt zu werden.

c) Überbevölkerungsregeln:

  • Eine lebende Zelle hat
    • 95% Überlebenswahrscheinlichkeit, wenn sie 0 oder 1 lebenden Nachbarn hat.
    • 80% Überlebenswahrscheinlichkeit, wenn sie 2 oder 3 lebende Nachbarn hat.
    • 30% Überlebenswahrscheinlichkeit, wenn sie mehr als 3 lebende Nachbarn hat.
  • Eine lebende Zelle teilt sich zufällig in eine der 8 Richtungen mit 
    • 25% Wahrscheinlichkeit, sich zu teilen, wenn sie 0 oder 1 lebenden Nachbarn hat.
    • 10% Wahrscheinlichkeit, sich zu teilen, wenn sie 2 oder 3 lebende Nachbarn hat.
    • 3% Wahrscheinlichkeit, sich zu teilen, wenn sie mehr als 3 lebende Nachbarn hat.

Schreiben Sie ein Programm, das eine Statistik darüber erstellt, wie sich die Populationsgröße (Anzahl lebender Zellen) für eine vom Benutzer definierte (festgelete oder zufällig erstellte) Ausgangssituation über die Zeit ändert. Stellen Sie diese Statistik grafisch dar.

Achten Sie dabei auf folgende Aspekte:

  • Flexibilität: Achten Sie darauf, dass Ihre Simulation und Statistik möglichst flexibel auf verschiedene Simulationsbedingungen anwendbar ist, z.B. verschieden grosse Matrizen, variable Anzahl Simulationsschritte etc.
  • Benutzerfreundlichkeit: Überlegen Sie, welche Möglichkeiten Sie dem Benutzer geben wollen, die Simulationsbedingungen festzulegen und wie sie diese Umsetzen möchten. (Z.B. fuer die Erstellung der Startverteilung sind im Prinzip sehr aufwändige Lösungen denkbar). Denken Sie daran, aussagekräftige Hilfetexte zu verfassen, damit der Benutzer (also im Zweifelsfall ich) weiss, wie er Ihr Programm bedienen soll.
  • Statistische Relevanz: Auch wenn Sie Ihr Statistikprogramm allgemein und vom Benutzer manipulierbar gestalten sollten, sollten Sie sich Gedanken darüber machen, wie groß ihre statistische Basis (Anzahl Durchläufe, Anzahl Zeitschritte) sein muss, damit Sie relevante Aussagen treffen können. (Diese könnten z.B. als Defaultwerte verwendet werden oder in einem Hilfetext für den Benutzer auftauchen.)
  • Randeffekte: Zellen mit lebenden Nachbarn und Zellen, die am Rand der Matrix angesiedelt sind, haben weniger als 8 Möglichkeiten, sich auf einen freien Platz zu teilen. Es gibt verschiedene Möglichkeiten, wie man mit diesem Problem umgehen kann. Überlegen Sie sich, was Sie für sinnvoll halten und kommentieren Sie Ihre Lösung entsprechend.

Erweiterungen:

Es sind zahlreiche Erweiterungen für das Spiel des Lebens möglich. Hier sind einige Vorschläge, wie sie es erweitern können - aber Ihrer Phantasie ist keine Grenze gesetzt. Sie können sich gerne auch andere Regeln, Grafik- oder Benutzerelemente ausdenken, wenn sie diese gut kommentieren, so dass ich weiss, worauf Ihre Programme hinauslaufen sollen.

Diese Aufzählung ist NICHT so gemeint, dass sie alle Vorschläge bearbeiten müssen. Für ein glattes "sehr gut" erwarte ich jedoch mindestens eine Erweiterung zusätzlich zur kompletten Lösung der Grundaufgabe.

  • Hindernisse: Bauen Sie in ihre Petrischale "Hindernisse" ein, auf denen keine Bakterien wachsen können. Dies kann die Populationsdynamik erheblich beeinflussen. Geben Sie dem Benutzer die Möglichkeit, Hindernisse an beliebigen Stellen der Petrischale einzusetzen.
  • Alter: Bestimmen Sie das jeweilige Alter einer Zelle (also die Anzahl der Zeitschritte, an denen ein bestimmter Platz durchgehend von einer lebenden Zelle besetzt war) und stellen Sie dieses farbig dar. Dadurch ergeben sich hübsche Farbeffekte in den Mustern. Wenn Sie Lust haben, können Sie Ihre Simulation noch etwas realistischer gestalten, indem Sie die Überlebenswahrscheinlichkeit in Abhängigkeit vom Alter verändern.
  • Erweiterung der Regeln: Beispielsweise könnten Sie in Abwandlung der oben verwendeten Regeln definieren, dass die Richtung einer Teilung um so wahrscheinlicher wird, je weniger lebende Nachbarn das betreffende freie Feld hat. (Aber es sind auch viele andere Möglichkeiten denkbar.)
  • Nährstoffgehalt: Ebenfalls eine schöne Erweiterungsrichtung ist es, den Feldern in den Startbedingungen einen Nährstoffgehalt zuzuweisen, von dem die Wahrscheinlichkeit abhängt, ob das Feld gefüllt wird.
  • Variation der Wahrscheinlichkeiten: Spielen Sie für einen der oben angegebenen Regelsätze mit den Wahrscheinlichkeiten und mit den Startbedingungen. In welchem Bereich entwickelt sich eine "gesunde" Populationsdynamik? Wann stirbt die Population grundsätzlich in kurzer Zeit? Wann gibt es ungebremstes Wachstum?
  • Systematische Auswertung der Populationsdynamik: (Für Auswertungs-Liebhaberinnen und Liebhaber) Führen Sie für einen der Regelsätze genügend Simulationen durch, um eine Funktion zu bestimmen, die die Populationsdyanamik über die Zeit beschreibt. Wählen Sie dafür am besten eine feste Größe der Petrischale und eine feste Anzahl der Zellen, mit denen Sie starten, aber wählen Sie jeweils eine neue Zufallsverteilung der Zellen. Wie hängt die von Ihnen bestimmte Funktion von der Anzahl der Zeitschritte ab, die die Simulation läuft? Wie hängt sie von der Anzahl der Zellen in der Startbedingung ab?
  • Grafische Benutzeroberfläche: Wenn Sie Lust haben, sich in grafische Benutzeroberflächen einzuarbeiten, können Sie überlegen, die Game of Life Simulation von Matlab als Grundlage für ihre Darstellung zu nehmen und diese zu erweitern. Ich würde aber dringend dazu raten, zuerst die Grundaufgabe ohne grafische Oberfläche zu lösen und dann erst an der Darstellung zu arbeiten. 

Viel Spaß!

Webmaster:5yj Jutk8h/ta Kplcq3retzbergh4j (juttaok.kretzigdrbe3b0srg@uol.de) (Stand: 07.11.2019)