Differences

This shows you the differences between two versions of the page.

--- lehrkraefte:blc:informatik:glf4-20:simulation:tabellenkalkulation-absolute-bezuege [2021/05/02 17:19]
Ivo Blöchliger
+++ lehrkraefte:blc:informatik:glf4-20:simulation:tabellenkalkulation-absolute-bezuege [2021/05/03 12:03] (current)
Ivo Blöchliger [Varianten (Expert)]
@@ Line 5: / Line 5: @@
   * Zellbezüge können aber auch nur auf die Spalte oder Zeile absolut gemacht werden, wie z.B. B\$2. Die Zeile 2 bleibt erhalten, die Spalte B wandert aber beim Kopieren nach links oder rechts entsprechend mit.
 </WRAP>
+===== Multiplikationstabelle =====
 <WRAP todo>
@@ Line 14: / Line 16: @@
 </WRAP>
+===== Sammelalbum füllen =====
+Wir betrachten ein Sammelablbum mit $n$ Plätzen für Klebebilder zum Einkleben. Der Einfachheit halber nehmen wir an, man kauft sich die Sammelbilder einzeln.
+Wir werden berechnen, wie gross die Wahrscheinlichkeit $p_{m,k}$ ist, nach dem Kauf von $m$ Bildern, genau $k$ unterschiedliche Bilder zu haben.
+Besonders interessant ist natürlich die Wahrscheinlichkeit $p_{m,n}$, d.h. die Wahrscheinlichkeit, nach dem Kauf von $m$ Bildern das Album komplett gefüllt zu haben.
+==== Berechnung von $p_{m,k}$ ====
+Man betrachtet einen Wahrscheinlichkeitsbaum mit den Knoten $p_{m,k}$
+Um diese Wahrscheinlichkeiten zu berechnen stellen wir erst mal fest, dass
+$$
+p_{1,1}=1 \text{ und } p_{1,k}=0  \text{ für }k > 1
+$$
+Nehmen wir an, wir hätten bereits $m$ Bilder gekauft und $k$ verschiedene. Man kauft jetzt ein zusätzliches Bild. Es gibt zwei Möglichkeiten:
+  * Wir haben das Bild bereits. Die Wahrscheinlichkeit dafür beträgt $\frac{k}{n}$. Begründen Sie, warum das so ist.
+  * Wir haben das Bild noch nicht. Die Wahrscheinlichkeit dafür beträgt $\frac{n-k}{n}$. Begründen Sie, warum das so ist.
+Umgekehrt gibt es zwei Möglichkeiten auf auf $k$ verschiedene Bilder bei $m$ gekauften zu kommen:
+  * Entweder man hatte vorher schon $k$ verschiedene und kauft erhält eines, das man schon hat. Die Wahrscheinlichkeit dafür beträgt $\frac{k}{n}$.
+  * Oder man hatte vorher $k-1$ verschiedene und erhält eines, das man noch nicht hat. Die Wahrscheinlichkeit dafür beträgt $\frac{n-k+1}{n}$.
+Damit können wir den Baum zeilenweise berechnen, bzw. die Wahrscheinlichkeiten für $m$ aus den Wahrscheinlichkeiten für $m-1$.
+==== Empfohlenes Tabellen-Layout ====
+{{:lehrkraefte:blc:informatik:glf4-20:simulation:pasted:20210502-184403.png}}
+**Tipps und Tricks**:
+  * Bennen Sie die Zelle mit der Anzahl Bilder.
+  * Verwenden Sie auch in den ersten beiden Kolonnen Formeln, um die Werte aus den vorhergehenden Werten zu berechnen. Das hat den Vorteil, dass Sie die gesamte Zeile 5 (für $m=2$) nach unten kopieren können.
+  * Zum Füllen mit Nullen geben Sie in zwei benachbarten Zellen eine Null ein, markieren Sie diese und kopieren Sie dann (wird nur eine Zelle markiert, wird diese beim Kopieren hochgezählt).
+Beantworten Sie folgende Fragen, einmal für $n=20$, einmal für $n=200$.
+  * Wie viele Bilder muss man kaufen, damit die Wahrscheinlichkeit eines vollen Albums
+    * min. 50% beträgt?
+    * min. 90% beträgt?
+    * min. 99% beträgt?
+    * min. 99.9% beträgt?
+===== Varianten (Expert) =====
+Wenn man jetzt zwei Alben hat, die man füllen möchte? Das Problem lässt sich wohl nur mit vielen Kniffs in Excel lösen, da muss wohl ein Python-Programm her (simuliert oder exakt).
+Für die exakte Lösung ist folgender Ansatz ein gangbarer Weg: Man betrachtet die Wahrscheinlichkeiten $p_{m,k,l}$ mit wobei $m$ die Anzahl gekaufter Bilder ist, $k$ die Anzahl Bilder, die zwei oder mehrere Male vorhanden sind, und $l$ die Anzahl Bilder, die genau einmal vorhanden sind.
+Damit lässt sich wieder ein Baum konstruieren, den man zeilenweise berechnen kann.
+<hidden Lösungsvorschlag in Python>
+Achtung: Der Code ist nicht sehr effizient und braucht sehr viel Speicher und ist nicht geeignet für Werte über 100.
+Das Speicherproblem kann relativ einfach gelöst werden, weil nur zwei Zeilen benötigt werden (alle vorhergehenden müssen nicht gespeichert werden).
+<code python sammelalben.py>
+n = 20
+p = [[[1 if k==l and k==0 else 0 for l in range(n+1)] for k in range(n+1)]]
+pfull = [[0,0]]
+csv = "Bilder;P(1 voll);P(2 voll)\n"
+for m in range(1,8*n):
+    # Neue Zeile mit Nullen einfügen
+    p.append([[0 for l in range(n+1)] for k in range(n+1)])  # Leere Zeile
+    pf = [0,0]  # Wahrscheinlichkeiten 1 oder 2 Alben voll zu haben
+    for k in range(n+1):     # Anzahl mehrfach vorhandene Bilder
+        for l in range(n-k+1):   # Anzahl einfach vorhandene Bilder
+            pmehrfach = 0.0
+            peinmal = 0.0
+            pkeinmal = 0.0
+            pmehrfach = p[m-1][k][l] * k/n             # Bild gekauft, das schon mehrfach vorhanden war
+            if (k>0 and l<n):
+                peinmal = p[m-1][k-1][l+1] * (l+1)/n      # Bild gekauft, das genau einmal vorhanden war
+            if (l>0):
+                pkeinmal = p[m-1][k][l-1] * (n-k-(l-1))/n  # Bild gekauft, das noch gar nicht vorhanden war
+            p[m][k][l] = pmehrfach + peinmal + pkeinmal
+            # Wahrscheinlichkeiten, 1 oder 2 Alben voll zu haben:
+            if (k==n):
+                pf[1]+=p[m][k][l]
+            if (l+k>=n):
+                pf[0]+=p[m][k][l]
+    pfull.append(pf)
+    print("Mit %3d von %d Bildern: p(1 volles Album)=%.8f, p(2 volle Alben)=%.8f" % (m, n, pfull[-1][0], pfull[-1][1]))
+    csv += "%d;%f;%f\n" % (m, pfull[-1][0], pfull[-1][1])
+datei = open("2alben.csv", "w")
+datei.write(csv)
+datei.close()
+</code>
+{{lehrkraefte:blc:informatik:glf4-20:simulation:2alben-200.svg}}
+</hidden>