lehrkraefte:blc:informatik:glf4-23:relative-und-absolute-bezuege [https://fginfo.ksbg.ch Fachgruppe Informatik der KSBG]

This page is read only. You can view the source, but not change it. Ask your administrator if you think this is wrong.
~~NOTOC~~

====== Absolute und Relative Bezüge ======
<WRAP info>
  * Zellbezüge in Excel sind normalerweise **relativ**, d.h. z.B. wenn sich die Zelle C5 auf die Zelle B4 bezieht, heisst das, man bezieht sich auf eine Zelle die sich um eins diagonal links darüber befindet. Kopiert man diese Zelle z.B. in die Zelle F8, bezieht sich die neue Zelle auf die Zelle E7. Kurz: Ein relativer Zellbezug ist wie ein **Vektor**, der beim Verschieben oder Kopieren nicht verändert wird.
  * Zellbezüge können aber auch **absolut** gemacht werden, dies indem man den Bezug mit \$-Zeichen kennzeichnet. Der Zelle \$C\$2 bezieht sich **immmer** auf die Zelle C2, auch wenn die Zelle kopiert oder verschoben wird. Oft lohnt es sich aber in einem solchen Fall die Zelle zu benennen und so als einfach lesbare Variable in Formeln zu verwenden.
  * 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>
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}}

**ADVANCED**: Erstellen Sie eine Multiplikationstabelle mit den (noch zu übersetzenden) Funktionen ''column()'' und ''row()''.
</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.

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}$ ====
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{ wenn }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 $k$ verschiedene Bilder bei $m$ gekauften Bildern 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$.

$$
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
$$

(In manchen Klassen habe ich die Formel mit folgendem ähnlichem Beispiel erklärt: {{ :lehrkraefte:snr:informatik:klasse-4:simulationen:wuerfelbeispiel-aehnlich-wie-sammelalbum.pdf |Würfelbeispiel, ähnlich zu Sammelalbum}})

==== 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$ (oder $n=707$ die Anzahl Bilder im aktuellen Fussball-Album).

  * 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: 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, 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>

<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>