Differences

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

--- lehrkraefte:blc:informatik:glf4-23:relative-und-absolute-bezuege [2024/03/23 23:25]
Olaf Schnürer [Berechnung von $p_{m,k}$]
+++ lehrkraefte:blc:informatik:glf4-23:relative-und-absolute-bezuege [2024/04/23 22:00] (current)
Olaf Schnürer [Varianten (Expert)]
@@ Line 1: / Line 1: @@
+~~NOTOC~~
 ====== Absolute und Relative Bezüge ======
 <WRAP info>
@@ Line 9: / Line 11: @@
 <WRAP todo>
-Erstellen Sie folgende Multiplikationstabelle mit halb-absoluten Bezügen:
+Erstellen Sie folgende Multiplikationstabelle mit halb-absoluten Bezügen.
+Die Idee ist, dass Sie **nur eine einzige Formel** im ersten Ergebnisfeld eingegben. Diese kopieren Sie dann auf die ganze Zeile.
+Danach kopieren Sie die ganze Zeile nach unten, um die Tabelle zu vervollständigen.
 {{:lehrkraefte:blc:informatik:glf4-20:simulation:pasted:20210502-165542.png}}
@@ Line 19: / Line 24: @@
 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.
+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.
+Zusammenfassung der Notationen:
+| $n$ | Anzahl Plätze im Sammelalbum (bzw. Anzahl verschiedener Klebebilder insgesamt). |
+| $m$ | Anzahl gekaufter Bilder, kann doppelte enthalten. |
+| $k$ | Anzahl unterschiedlicher Bilder, die man erwischt hat. Dabei gilt immer $k \leq m$ und $k \leq n$. |
+| $p_{m,k}$ | Wahrscheinlichkeit, nach dem Kauf von $m$ Bildern genau $k$ unterschiedliche Bilder zu besitzen. |
 ==== Berechnung von $p_{m,k}$ ====
@@ Line 28: / Line 39: @@
 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
+p_{1,1}=1 \text{ und } p_{1,k}=0  \text{ wenn }k > 1
 $$
@@ Line 40: / Line 51: @@
 Damit können wir den Baum zeilenweise berechnen, bzw. die Wahrscheinlichkeiten für $m$ aus den Wahrscheinlichkeiten für $m-1$.
+$$
+p_{m,k} = p_{m-1,k}\cdot \frac{k}{n} + p_{m-1,k-1}\cdot \frac{n-(k-1)}{n}
+\qquad \text{ mit } p_{m,0}=0 \text{ wenn } m\geq 1
+$$
 ==== Empfohlenes Tabellen-Layout ====
@@ Line 50: / Line 66: @@
   * 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$.
+Beantworten Sie folgende Fragen, einmal für $n=20$, einmal für $n=200$ (oder $n=707$ die Anzahl Bilder im aktuellen Fussball-Album).
   * Wie viele Bilder muss man kaufen, damit die Wahrscheinlichkeit eines vollen Albums
@@ Line 61: / Line 77: @@
 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.
+Für die exakte Lösung ist folgender Ansatz ein gangbarer Weg: Sei $p_{m,k,l}$ die Wahrscheinlichkeit, dass man nach dem Kauf von $m$ Bildern $k$ Bilder mindestens zweimal und $l$ Bilder genau einmal hat.
 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.
+Achtung: Der Code ist nicht sehr effizient, 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).
@@ Line 117: / Line 133: @@
 {{lehrkraefte:blc:informatik:glf4-20:simulation:2alben-200.svg}}
+</hidden>
+<hidden Python-Programm, per Simulation, variable Anzahl Alben>
+<code python sammelalben-simulation.py>
+import random
+import matplotlib.pyplot as plt
+n = 200
+anzahl_alben = 3
+anzahl_versuche = 10000
+liste_noetiger_kaeufe = []
+for v in range(anzahl_versuche):
+    if v % 1000 == 0:
+        print(f'Versuch {v}')
+    liste_anzahl_bilder = [0 for _ in range(n)]
+    kaeufe = 0
+    while min(liste_anzahl_bilder) < anzahl_alben:
+        kaeufe += 1
+        bild_nummer = random.randrange(n)
+        liste_anzahl_bilder[bild_nummer] += 1
+    while len(liste_noetiger_kaeufe) < kaeufe + 1:
+        liste_noetiger_kaeufe.append(0)
+    liste_noetiger_kaeufe[kaeufe] += 1
+print(liste_noetiger_kaeufe)
+liste_noetiger_kaeufe_summiert = []
+summe = 0
+for i in range(len(liste_noetiger_kaeufe)):
+    summe += liste_noetiger_kaeufe[i]
+    liste_noetiger_kaeufe_summiert.append(summe / anzahl_versuche)
+xwerte = list(range(len(liste_noetiger_kaeufe)))
+plt.bar(xwerte, liste_noetiger_kaeufe)
+plt.xlabel(f"x = Anzahl der Käufe, bis {anzahl_alben} Alben voll")
+plt.ylabel(f"y(x) = Anzahl der Experimente, bei denen x Käufe nötig waren.")
+plt.show()
+p = 0
+while p < 1:
+    i = 0
+    while liste_noetiger_kaeufe_summiert[i] < p:
+        i += 1
+    print(f'Man muss (laut Simulation) {i} Bilder kaufen, um {anzahl_alben} Alben mit Wahrscheinlichkeit {p:.1f} zu füllen.')
+    p += 0.1
+plt.plot(liste_noetiger_kaeufe_summiert)
+plt.xlabel(f"x = Anzahl der Käufe")
+plt.ylabel(f"p(x) = Wahrscheinlichkeit, dass {anzahl_alben} Alben voll.")
+plt.show()
+</code>
 </hidden>