Aufgabenblatt 4

Die Bewertungsgrundlage ist auch hier anders. Bitte beachten Sie dies.

Update: Neuer Abgabetermin ist der 19.06.2018 Beachtet die neuen Hinweise zur Wahrscheinlichkeitsrechnung am Ende der Seite

Aufgabe 0

Um die Stimmung während eines Konzerts in einer Halle zu haben, hat sich der Veranstalter etwas ausgedacht: Wenn die Grundfläche der Halle sich in 30x30 Quadrate aufteilen lässt, so wurde in jedes Quadrat ein Strandball, also insgesamt 900 Bälle abgeworfen. Auf sein Zeichen in einem Lied sollen die Konzertbesucher den Ball in ein benachbartes Quadrat werfen - sie haben in der Regel 4 Nachbarn, außer die Quadrate am Rand (3 Nachbarn) und in der Ecke (2 Nachbarn). Am Ende des Liedes wird das Zeichen insgesamt 50x gegeben worden sein. Ein Quadrat kann beliebig viele Strandbälle aufnehmen.

Wie hoch ist der Erwartungswert an Quadraten ohne einen Strandball nach Ende des Lieds? Geben Sie die Lösung mit 10 Nachkommastellen an.

Test und Eingabeformat

Ihr Programm soll in der Lage sein, die folgenden Parameter von der Standardeingabe zu lesen:

• Seitenlänge der Halle in Quadraten
• Anzahl Signale

Beispiel:

3
4

Hierbei handelte es sich um eine Hallt von 3x3 Quadraten und das Lied endet mit 4 Signalen.

Messen Sie das Laufzeitverhalten Ihrer Lösung mit wachsender Anzahl Schritte.

Beispiel

5
50

Der Erwartungswert für ein 5x5 Feld, nach 50 Signalen freie Felder zu haben beträgt

9.0448005505 

Noch ein Beispiel zum Erwartungswert

Bei einer Halle mit 2x2 Feldern existieren nach einer Runde 16 mögliche Folgezustände der Halle Seien die Bälle durchnummeriert von 0 bis 3 und jedes eckige Klammerpaar zeige ein Quadrat an:

Von:

[0][1]
[2][3]

ausgehend kommen die folgenden Zustände in Frage:

[2][0]
[3][1]

[][0]
[3][1,2]

[2][0,3]
[][1]

[][0,3]
[][1,2]

[1,2][0]
[3][]

[1][0]
[3][2]

[1,2][0,3]
[][]

[1][0,3]
[][2]

[2][]
[0,3][1]

[][]
[0,3][1,2]

[2][3]
[0][1]

[][3]
[0][1,2]

[1,2][]
[0,3][]

[1][]
[0,3][2]

[1,2][3]
[0][]

[1][3]
[0][2]

Das sind, wie gesagt, 16 mögliche Folgezustände. Über all diese Folgezustände haben wir:

4 Zustände mit 0 freien Feldern 8 Zustände mit 1 freiem Feld und 4 Zustände mit 2 freien Feldern

Das bedeutet, dass der Erwartungswert bei 4/16*0 + 8/16*1 + 4/16*2 = 1 liegt.

Nein, das ist kein praktikabler Weg, die Aufgabe zu lösen.

Weitere Notizen

• Wie ich im Praktikum gesagt habe: Dies ist neben einer Programmieraufgabe auch eine Rechercheaufgabe. Nutzt alle Ressourcen, die euch zur Verfügung stehen, um eventuelle Herausforderungen mit der Wahrscheinlichkeitsrechnung zu meistern. Es ist irrelevant, wie ihr zu der mathematischen Lösung gekommen seid, solange ihr sie danach erklären könnt und ggf. Quellenangaben in eurer Dokumentation liefert.

Hinweise zur Wahrscheinlichkeitsrechnung

• Jeder Ball ist ein unabhängiges Ergeignis. Sie zwischendurch zu verrechnen ist ein Fehler.
• Betrachten Sie für jedes Feld die Wahrscheinlichkeit, ob sich der Ball (Nr. 1 bis 50) dort befindet.

Wir wiederholen das Beispiel mit 4 Feldern und 4 Bällen. Ich notiere in Klammern, wie hoch die Wahrscheinlichkeit für Ball 1,2,3,4 es ist, an dieer Position zu sein:

(1,0,0,0)	(0,1,0,0)
(0,0,1,0)	(0,0,0,1)

im nächsten Schritt sieht das dann so aus:

(0,1/2,1/2,0)	(1/2,0,0,1/2)
(1/2,0,0,1/2)	(0,1/2,1/2,0)

Die Wahrscheinlichkeit, dass ein Feld leer ist, ermittelt sich aus den Wahrscheinlichkeiten, dass

• Ball 1 nicht da ist
• Ball 2 nicht da ist
• Ball 3 nicht da ist
• Ball 4 nicht da ist

Das ist jeweils das Gegenereignis zu dem, was bislang für jedes Feld berechnet wurde. Die Gegenwahrscheinlichkeit von p ist immer 1-p

Die Bälle werden unabhängig voneinander bewegt und sind damit unanhängige Ereginisse. Die Wahrscheinlichkeit, dass 4 unabhängige Ereignisse gleichzeitig zutreffen errechnet sich aus:

p(Ball 1 nicht da) * p(Ball 2 nicht da) * p(Ball 3 nicht da) * p(Ball 4 nicht da)

So ergibt sich für das Beispiel für jedes Feld die Wahrscheinlichkeit, dass es leer ist:

(1*1/2*1/2*1)	(1/2*1*1*1/2)
(1/2*1*1*1/2)	(1*1/2*1/2*1)

ausgerechnet:

1/4	1/4
1/4	1/4

Der Erwartungswert ist nun die Summe aus den Wahrscheinlichkeiten jedes einzelnen Feldes, dass es leer ist.

1

Bewertungsgrundlage

Diese Aufgabe stellt andere Anforderungen als die Vorangegangenen. Hier geht es darum, ein geeignetes mathematisches Modell zu finden und möglichst passende Werkzeuge der Informatik anzuwenden.

Die Bewertung der Abgabe besteht aus den unten folgenden Punkten, die ihr Lösungsprojekt enthalten muss. Nehmen Sie als Vorlage die Musterlösung zu Aufgabe 0 zur Hand.

• Eine schriftliche Ausarbeitung als PDF-Dokument in Ihrem GitLab-Projekt:
  • Analyse des Problems.
  • Beschreiben Sie mit den Mitteln der Stochastik ihren Lösungsansatz
• Lösung der Problems in einem Projektordner in Ihrem GitLab-Projekt
  • Das ausschließlich von Ihnen allein geschriebene Programm soll die gestellte Aufgabe auf einem gewöhnlichen Laborrechner der Hochschule in unter einer Minute Laufzeit lösen.
  • Das Lösungsprojekt darf nur als Quellcode abgegeben werden.
  • Eine ausführliche Bau- und Ausführanleitung ist zwingender Bestandteil der Abgabe. Legen Sie gegebenenfalls Makefiles oder andere Bauskripte bei. Das Bauen und Ausführen des Lösungsprojekts muss in wenigen Schritten möglich sein und auf einem Laborrechner der Hochschule vorgeführt werden können.
  • Ihr Programm muss die Puzzleeingabe von der Standardeingabe einlesen.
  • Ihr Programm darf nur Ihre Lösung auf der Standardausgabe ausgeben. Die Lösung muss in der Form den mitgelieferten Beispielen entsprechen. Zusätzliche Ausgabe zu Debuggingzwecken sind aus der Abgabe vorher zu entfernen. Falls Ihr Programm hilfreiche Detailinformationen zur Lösungsfindung ausgeben kann, dokumentieren Sie, wie sie gesondert aktiviert werden kann.

Seien Sie außerdem darauf vorbereitet, Ihr Projekt während des Praktikumstermins vorzustellen und dazu Fragen zu beantworten.

Abgabemodalitäten

Zur Abnahme ist die persönliche Anwesenheit erforderlich. Ihr Lösungsprojekt muss zum Abgabetermin im vorher von Ihnen eingerichtetem persönlichen, privaten GitLab-Projekt abrufbar sein.