Für Zufallsvariablen \(X, Y\) und \(a, b \in \mathbb{R}\) gilt:
\[{{c1::\mathbb{E}[aX + bY] = a\,\mathbb{E}[X] + b\,\mathbb{E}[Y]}}.\]
\[{{c1::\mathbb{E}[aX + bY] = a\,\mathbb{E}[X] + b\,\mathbb{E}[Y]}}.\]
Note 1: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
!B0d*2$IxZ
Previous
Note did not exist
New Note
Front
Back
Für Zufallsvariablen \(X, Y\) und \(a, b \in \mathbb{R}\) gilt:
\[{{c1::\mathbb{E}[aX + bY] = a\,\mathbb{E}[X] + b\,\mathbb{E}[Y]}}.\]
\[{{c1::\mathbb{E}[aX + bY] = a\,\mathbb{E}[X] + b\,\mathbb{E}[Y]}}.\]
Wichtig: Gilt unabhängig davon, ob \(X\) und \(Y\) stochastisch unabhängig sind!
Insbesondere: \(\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]\).
Insbesondere: \(\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Für Zufallsvariablen \(X, Y\) und \(a, b \in \mathbb{R}\) gilt:<br>\[{{c1::\mathbb{E}[aX + bY] = a\,\mathbb{E}[X] + b\,\mathbb{E}[Y]}}.\] | |
| Extra | <strong>Wichtig:</strong> Gilt unabhängig davon, ob \(X\) und \(Y\) stochastisch unabhängig sind!<br>Insbesondere: \(\mathbb{E}[X + Y] = \mathbb{E}[X] + \mathbb{E}[Y]\). |
Note 2: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
#a1quntnA7
Previous
Note did not exist
New Note
Front
Für einen zusammenhängenden planaren Graphen \(G\) mit \(n\) Knoten,
\(m\) Kanten und \(f\) Flächen gilt:
\[n - m + f = 2.\]
(Euler-Formel)
Daraus folgt für \(n \geq 3\): \(m \leq 3n - 6\).
\(m\) Kanten und \(f\) Flächen gilt:
\[n - m + f = 2.\]
(Euler-Formel)
Daraus folgt für \(n \geq 3\): \(m \leq 3n - 6\).
Back
Für einen zusammenhängenden planaren Graphen \(G\) mit \(n\) Knoten,
\(m\) Kanten und \(f\) Flächen gilt:
\[n - m + f = 2.\]
(Euler-Formel)
Daraus folgt für \(n \geq 3\): \(m \leq 3n - 6\).
\(m\) Kanten und \(f\) Flächen gilt:
\[n - m + f = 2.\]
(Euler-Formel)
Daraus folgt für \(n \geq 3\): \(m \leq 3n - 6\).
Beweis der Ungleichung: Jede Fläche wird von mind. 3 Kanten begrenzt; jede Kante grenzt an max. 2 Flächen.
Also \(3f \leq 2m\), einsetzen in Euler-Formel gibt \(m \leq 3n - 6\).
Korollar: In jedem planaren Graphen gibt es einen Knoten mit Grad \(\leq 5\).
Also \(3f \leq 2m\), einsetzen in Euler-Formel gibt \(m \leq 3n - 6\).
Korollar: In jedem planaren Graphen gibt es einen Knoten mit Grad \(\leq 5\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Für einen zusammenhängenden planaren Graphen \(G\) mit \(n\) Knoten,<br>\(m\) Kanten und \(f\) Flächen gilt:<br>\[{{c1::n - m + f = 2}}.\]<br>(Euler-Formel)<br><br>Daraus folgt für \(n \geq 3\): \(m \leq {{c2::3n - 6}}\). | |
| Extra | Beweis der Ungleichung: Jede Fläche wird von mind. 3 Kanten begrenzt; jede Kante grenzt an max. 2 Flächen.<br>Also \(3f \leq 2m\), einsetzen in Euler-Formel gibt \(m \leq 3n - 6\).<br>Korollar: In jedem planaren Graphen gibt es einen Knoten mit Grad \(\leq 5\). |
Note 3: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
%g)7+q%i*d
Previous
Note did not exist
New Note
Front
Für endliche Mengen \(A_1, \ldots, A_n\) gilt:
\[\left|\bigcup_{i=1}^n A_i\right| = {{c1::\sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{iFür \(n = 2\): \(|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|\).
\[\left|\bigcup_{i=1}^n A_i\right| = {{c1::\sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i
Back
Für endliche Mengen \(A_1, \ldots, A_n\) gilt:
\[\left|\bigcup_{i=1}^n A_i\right| = {{c1::\sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{iFür \(n = 2\): \(|A_1 \cup A_2| = |A_1| + |A_2| - |A_1 \cap A_2|\).
\[\left|\bigcup_{i=1}^n A_i\right| = {{c1::\sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i
Die Wahrscheinlichkeitsversion ersetzt \(|\cdot|\) durch \(\Pr[\cdot]\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Für endliche Mengen \(A_1, \ldots, A_n\) gilt:<br>\[\left|\bigcup_{i=1}^n A_i\right| = {{c1::\sum_{i} |A_i| - \sum_{i < j} |A_i \cap A_j| + \sum_{i<j<k} |A_i \cap A_j \cap A_k| - \cdots}}\]<br>Für \(n = 2\): \(|A_1 \cup A_2| = {{c2::|A_1| + |A_2| - |A_1 \cap A_2|}}\). | |
| Extra | Die Wahrscheinlichkeitsversion ersetzt \(|\cdot|\) durch \(\Pr[\cdot]\). |
Note 4: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
%vNl0WhR5#
Previous
Note did not exist
New Note
Front
Für Ereignisse \(A_1, \ldots, A_n\) gilt:
\[\Pr[A_1 \cap \cdots \cap A_n] = {{c1::\Pr[A_1] \cdot \Pr[A_2 \mid A_1] \cdot \Pr[A_3 \mid A_1 \cap A_2] \cdots \Pr[A_n \mid A_1 \cap \cdots \cap A_{n-1}]}}.\]
\[\Pr[A_1 \cap \cdots \cap A_n] = {{c1::\Pr[A_1] \cdot \Pr[A_2 \mid A_1] \cdot \Pr[A_3 \mid A_1 \cap A_2] \cdots \Pr[A_n \mid A_1 \cap \cdots \cap A_{n-1}]}}.\]
Back
Für Ereignisse \(A_1, \ldots, A_n\) gilt:
\[\Pr[A_1 \cap \cdots \cap A_n] = {{c1::\Pr[A_1] \cdot \Pr[A_2 \mid A_1] \cdot \Pr[A_3 \mid A_1 \cap A_2] \cdots \Pr[A_n \mid A_1 \cap \cdots \cap A_{n-1}]}}.\]
\[\Pr[A_1 \cap \cdots \cap A_n] = {{c1::\Pr[A_1] \cdot \Pr[A_2 \mid A_1] \cdot \Pr[A_3 \mid A_1 \cap A_2] \cdots \Pr[A_n \mid A_1 \cap \cdots \cap A_{n-1}]}}.\]
Erweiterung der Multiplikationsregel auf \(n\) Ereignisse.
Anwendung: Wahrscheinlichkeit, \(k\) spezifische Karten nacheinander zu ziehen.
Anwendung: Wahrscheinlichkeit, \(k\) spezifische Karten nacheinander zu ziehen.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Für Ereignisse \(A_1, \ldots, A_n\) gilt:<br>\[\Pr[A_1 \cap \cdots \cap A_n] = {{c1::\Pr[A_1] \cdot \Pr[A_2 \mid A_1] \cdot \Pr[A_3 \mid A_1 \cap A_2] \cdots \Pr[A_n \mid A_1 \cap \cdots \cap A_{n-1}]}}.\] | |
| Extra | Erweiterung der Multiplikationsregel auf \(n\) Ereignisse.<br>Anwendung: Wahrscheinlichkeit, \(k\) spezifische Karten nacheinander zu ziehen. |
Note 5: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
*4D!n}uy#2
Previous
Note did not exist
New Note
Front
Für alle \(v \in V\) gilt stets \({{c1::\text{low}[v] \leq \text{dfs}[v]}}\),
da wir auch den leeren Pfad betrachten können.
da wir auch den leeren Pfad betrachten können.
Back
Für alle \(v \in V\) gilt stets \({{c1::\text{low}[v] \leq \text{dfs}[v]}}\),
da wir auch den leeren Pfad betrachten können.
da wir auch den leeren Pfad betrachten können.
D.h. man kann immer mindestens sich selbst erreichen (leerer Pfad = 0 Schritte).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Für alle \(v \in V\) gilt stets \({{c1::\text{low}[v] \leq \text{dfs}[v]}}\),<br>da wir auch den leeren Pfad betrachten können. | |
| Extra | D.h. man kann immer mindestens sich selbst erreichen (leerer Pfad = 0 Schritte). |
Note 6: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
1V$+8N)nVy
Previous
Note did not exist
New Note
Front
Die Indikator-Zufallsvariable (Bernoulli-Variable) für Ereignis \(A\) ist:
\[X_A(\omega) := \begin{cases} 1 & \omega \in A \\ 0 & \omega \notin A \end{cases}.\]
Es gilt: \(\mathbb{E}[X_A] = \Pr[A]\).
\[X_A(\omega) := \begin{cases} 1 & \omega \in A \\ 0 & \omega \notin A \end{cases}.\]
Es gilt: \(\mathbb{E}[X_A] = \Pr[A]\).
Back
Die Indikator-Zufallsvariable (Bernoulli-Variable) für Ereignis \(A\) ist:
\[X_A(\omega) := \begin{cases} 1 & \omega \in A \\ 0 & \omega \notin A \end{cases}.\]
Es gilt: \(\mathbb{E}[X_A] = \Pr[A]\).
\[X_A(\omega) := \begin{cases} 1 & \omega \in A \\ 0 & \omega \notin A \end{cases}.\]
Es gilt: \(\mathbb{E}[X_A] = \Pr[A]\).
Beweis: \(\mathbb{E}[X_A] = 1 \cdot \Pr[A] + 0 \cdot \Pr[A^c] = \Pr[A]\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Die {{c1::Indikator-Zufallsvariable}} (Bernoulli-Variable) für Ereignis \(A\) ist:<br>\[X_A(\omega) := \begin{cases} {{c2::1}} & \omega \in A \\ {{c2::0}} & \omega \notin A \end{cases}.\]<br>Es gilt: \(\mathbb{E}[X_A] = {{c3::\Pr[A]}}\). | |
| Extra | Beweis: \(\mathbb{E}[X_A] = 1 \cdot \Pr[A] + 0 \cdot \Pr[A^c] = \Pr[A]\). |
Note 7: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
5UuotfGX{n
Previous
Note did not exist
New Note
Front
Besteht eine Auswahl aus \(k\) unabhängigen Schritten mit je \(n_1, \ldots, n_k\)
Möglichkeiten, so gibt es insgesamt:
\[n_1 \cdot n_2 \cdot \cdots \cdot n_k\]
Möglichkeiten.
Möglichkeiten, so gibt es insgesamt:
\[n_1 \cdot n_2 \cdot \cdots \cdot n_k\]
Möglichkeiten.
Back
Besteht eine Auswahl aus \(k\) unabhängigen Schritten mit je \(n_1, \ldots, n_k\)
Möglichkeiten, so gibt es insgesamt:
\[n_1 \cdot n_2 \cdot \cdots \cdot n_k\]
Möglichkeiten.
Möglichkeiten, so gibt es insgesamt:
\[n_1 \cdot n_2 \cdot \cdots \cdot n_k\]
Möglichkeiten.
Grundlage aller Zählformeln.
Beispiel: Wie viele Paare (Hemd, Hose) aus 4 Hemden und 3 Hosen? \(4 \cdot 3 = 12\).
Kartesisches Produkt: \(|A \times B| = |A| \cdot |B|\).
Beispiel: Wie viele Paare (Hemd, Hose) aus 4 Hemden und 3 Hosen? \(4 \cdot 3 = 12\).
Kartesisches Produkt: \(|A \times B| = |A| \cdot |B|\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Besteht eine Auswahl aus \(k\) unabhängigen Schritten mit je \(n_1, \ldots, n_k\)<br>Möglichkeiten, so gibt es insgesamt:<br>\[{{c1::n_1 \cdot n_2 \cdot \cdots \cdot n_k}}\]<br>Möglichkeiten. | |
| Extra | Grundlage aller Zählformeln.<br>Beispiel: Wie viele Paare (Hemd, Hose) aus 4 Hemden und 3 Hosen? \(4 \cdot 3 = 12\).<br>Kartesisches Produkt: \(|A \times B| = |A| \cdot |B|\). |
Note 8: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID:
added
Note Type: Horvath Classic
GUID:
8iupsDjsP)
Previous
Note did not exist
New Note
Front
Ein Test für eine seltene Krankheit (Prävalenz 0,1%) ist 99% sensitiv und 99% spezifisch.
Wie groß ist \(\Pr[\text{krank} \mid \text{positiv}]\)?
Wie groß ist \(\Pr[\text{krank} \mid \text{positiv}]\)?
Back
Ein Test für eine seltene Krankheit (Prävalenz 0,1%) ist 99% sensitiv und 99% spezifisch.
Wie groß ist \(\Pr[\text{krank} \mid \text{positiv}]\)?
Wie groß ist \(\Pr[\text{krank} \mid \text{positiv}]\)?
Sei \(K\) = krank, \(T^+\) = positiv.
\(\Pr[K] = 0{,}001\), \(\Pr[T^+ \mid K] = 0{,}99\), \(\Pr[T^+ \mid \neg K] = 0{,}01\).
\(\Pr[T^+] = 0{,}99 \cdot 0{,}001 + 0{,}01 \cdot 0{,}999 \approx 0{,}01098\).
\(\Pr[K \mid T^+] = \dfrac{0{,}99 \cdot 0{,}001}{0{,}01098} \approx \mathbf{9\%}\).
Obwohl der Test 99% genau ist, ist ein positiver Befund meist ein Fehlalarm —
weil die Krankheit so selten ist. Der Prior (Basisrate) bestimmt das Ergebnis.
\(\Pr[K] = 0{,}001\), \(\Pr[T^+ \mid K] = 0{,}99\), \(\Pr[T^+ \mid \neg K] = 0{,}01\).
\(\Pr[T^+] = 0{,}99 \cdot 0{,}001 + 0{,}01 \cdot 0{,}999 \approx 0{,}01098\).
\(\Pr[K \mid T^+] = \dfrac{0{,}99 \cdot 0{,}001}{0{,}01098} \approx \mathbf{9\%}\).
Obwohl der Test 99% genau ist, ist ein positiver Befund meist ein Fehlalarm —
weil die Krankheit so selten ist. Der Prior (Basisrate) bestimmt das Ergebnis.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | Ein Test für eine seltene Krankheit (Prävalenz 0,1%) ist 99% sensitiv und 99% spezifisch.<br>Wie groß ist \(\Pr[\text{krank} \mid \text{positiv}]\)? | |
| Back | Sei \(K\) = krank, \(T^+\) = positiv.<br>\(\Pr[K] = 0{,}001\), \(\Pr[T^+ \mid K] = 0{,}99\), \(\Pr[T^+ \mid \neg K] = 0{,}01\).<br>\(\Pr[T^+] = 0{,}99 \cdot 0{,}001 + 0{,}01 \cdot 0{,}999 \approx 0{,}01098\).<br>\(\Pr[K \mid T^+] = \dfrac{0{,}99 \cdot 0{,}001}{0{,}01098} \approx \mathbf{9\%}\).<br><br>Obwohl der Test 99% genau ist, ist ein positiver Befund meist ein Fehlalarm —<br>weil die Krankheit so selten ist. <strong>Der Prior (Basisrate) bestimmt das Ergebnis.</strong> |
Note 9: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
B1cEOSgE
Previous
Note did not exist
New Note
Front
BFS für augmentierende Pfade in bipartiten Graphen \(G = (A \uplus B, E)\):
- \(L_0 := \)unüberdeckte Knoten aus \(A\)
- Für ungerades \(i\): \(L_i := \){{c2::unbesuchte Nachbarn von \(L_{i-1}\) via Kanten in \(E \setminus M\)}}
- Für gerades \(i\): \(L_i := \){{c3::unbesuchte Nachbarn von \(L_{i-1}\) via Kanten in \(M\)}}
- Terminierung: sobald \(L_i\) einen unüberdeckten Knoten enthält → Pfad per Backtracking.
Back
BFS für augmentierende Pfade in bipartiten Graphen \(G = (A \uplus B, E)\):
- \(L_0 := \)unüberdeckte Knoten aus \(A\)
- Für ungerades \(i\): \(L_i := \){{c2::unbesuchte Nachbarn von \(L_{i-1}\) via Kanten in \(E \setminus M\)}}
- Für gerades \(i\): \(L_i := \){{c3::unbesuchte Nachbarn von \(L_{i-1}\) via Kanten in \(M\)}}
- Terminierung: sobald \(L_i\) einen unüberdeckten Knoten enthält → Pfad per Backtracking.
Laufzeit: \(O(|V| + |E|)\) für einen augmentierenden Pfad.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | BFS für augmentierende Pfade in bipartiten Graphen \(G = (A \uplus B, E)\):<br><ol><li>\(L_0 := \){{c1::unüberdeckte Knoten aus \(A\)}}</li><li>Für ungerades \(i\): \(L_i := \){{c2::unbesuchte Nachbarn von \(L_{i-1}\) via Kanten in \(E \setminus M\)}}</li><li>Für gerades \(i\): \(L_i := \){{c3::unbesuchte Nachbarn von \(L_{i-1}\) via Kanten in \(M\)}}</li><li>Terminierung: {{c4::sobald \(L_i\) einen unüberdeckten Knoten enthält}} → Pfad per Backtracking.</li></ol> | |
| Extra | Laufzeit: \(O(|V| + |E|)\) für einen augmentierenden Pfad. |
Note 10: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
Cok[j3$Aa[
Previous
Note did not exist
New Note
Front
Für \(x, y \in \mathbb{R}\) und \(n \in \mathbb{N}_0\) gilt:
\[(x + y)^n = {{c1::\sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}}}.\]
\[(x + y)^n = {{c1::\sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}}}.\]
Back
Für \(x, y \in \mathbb{R}\) und \(n \in \mathbb{N}_0\) gilt:
\[(x + y)^n = {{c1::\sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}}}.\]
\[(x + y)^n = {{c1::\sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}}}.\]
Speziell:
\((1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k\)
\((1-1)^n = 0 = \sum_{k=0}^n (-1)^k \binom{n}{k}\) (genutzt im Siebformel-Beweis!)
\((1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k\)
\((1-1)^n = 0 = \sum_{k=0}^n (-1)^k \binom{n}{k}\) (genutzt im Siebformel-Beweis!)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Für \(x, y \in \mathbb{R}\) und \(n \in \mathbb{N}_0\) gilt:<br>\[(x + y)^n = {{c1::\sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}}}.\] | |
| Extra | Speziell:<br>\((1+x)^n = \sum_{k=0}^n \binom{n}{k} x^k\)<br>\((1-1)^n = 0 = \sum_{k=0}^n (-1)^k \binom{n}{k}\) (genutzt im Siebformel-Beweis!) |
Note 11: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
F-BHv{onMh
Previous
Note did not exist
New Note
Front
Die Anzahl der Anordnungen von \(n\) Objekten, von denen
\(n_1\) vom Typ 1, …, \(n_r\) vom Typ \(r\) sind (\(n_1 + \cdots + n_r = n\)), ist:
\[{{c1::\frac{n!}{n_1!\, n_2!\, \cdots\, n_r!}}} = \binom{n}{n_1, n_2, \ldots, n_r}.\]
(Multinomialkoeffizient)
\(n_1\) vom Typ 1, …, \(n_r\) vom Typ \(r\) sind (\(n_1 + \cdots + n_r = n\)), ist:
\[{{c1::\frac{n!}{n_1!\, n_2!\, \cdots\, n_r!}}} = \binom{n}{n_1, n_2, \ldots, n_r}.\]
(Multinomialkoeffizient)
Back
Die Anzahl der Anordnungen von \(n\) Objekten, von denen
\(n_1\) vom Typ 1, …, \(n_r\) vom Typ \(r\) sind (\(n_1 + \cdots + n_r = n\)), ist:
\[{{c1::\frac{n!}{n_1!\, n_2!\, \cdots\, n_r!}}} = \binom{n}{n_1, n_2, \ldots, n_r}.\]
(Multinomialkoeffizient)
\(n_1\) vom Typ 1, …, \(n_r\) vom Typ \(r\) sind (\(n_1 + \cdots + n_r = n\)), ist:
\[{{c1::\frac{n!}{n_1!\, n_2!\, \cdots\, n_r!}}} = \binom{n}{n_1, n_2, \ldots, n_r}.\]
(Multinomialkoeffizient)
Speziell für \(r=2\): \(\frac{n!}{k!\,(n-k)!} = \binom{n}{k}\).
Beispiel: Anordnungen von „MISSISSIPPI“: \(\frac{11!}{1!\cdot 4!\cdot 4!\cdot 2!} = 34{,}650\).
Beispiel: Anordnungen von „MISSISSIPPI“: \(\frac{11!}{1!\cdot 4!\cdot 4!\cdot 2!} = 34{,}650\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Die Anzahl der Anordnungen von \(n\) Objekten, von denen<br>\(n_1\) vom Typ 1, …, \(n_r\) vom Typ \(r\) sind (\(n_1 + \cdots + n_r = n\)), ist:<br>\[{{c1::\frac{n!}{n_1!\, n_2!\, \cdots\, n_r!}}} = \binom{n}{n_1, n_2, \ldots, n_r}.\]<br>(Multinomialkoeffizient) | |
| Extra | Speziell für \(r=2\): \(\frac{n!}{k!\,(n-k)!} = \binom{n}{k}\).<br>Beispiel: Anordnungen von „MISSISSIPPI“: \(\frac{11!}{1!\cdot 4!\cdot 4!\cdot 2!} = 34{,}650\). |
Note 12: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID:
added
Note Type: Horvath Classic
GUID:
FY+KJ_cd2]
Previous
Note did not exist
New Note
Front
Was besagt der Vierfarbensatz?
Back
Was besagt der Vierfarbensatz?
Jeder planare Graph (jede Landkarte) lässt sich mit \(\leq 4\) Farben färben.
Formal: Für jeden planaren Graphen \(G\) gilt \(\chi(G) \leq 4\).
(Appel & Haken, 1976 — erster computergestützter Beweis)
Formal: Für jeden planaren Graphen \(G\) gilt \(\chi(G) \leq 4\).
(Appel & Haken, 1976 — erster computergestützter Beweis)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | Was besagt der Vierfarbensatz? | |
| Back | Jeder planare Graph (jede Landkarte) lässt sich mit \(\leq 4\) Farben färben.<br>Formal: Für jeden planaren Graphen \(G\) gilt \(\chi(G) \leq 4\).<br>(Appel & Haken, 1976 — erster computergestützter Beweis) |
Note 13: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
GTMcPtrK9g
Previous
Note did not exist
New Note
Front
Die Anzahl der geordneten Auswahlen von \(k\) aus \(n\) Objekten
mit Zurüclegen (Reihenfolge wichtig) ist:
\[n^k.\]
mit Zurüclegen (Reihenfolge wichtig) ist:
\[n^k.\]
Back
Die Anzahl der geordneten Auswahlen von \(k\) aus \(n\) Objekten
mit Zurüclegen (Reihenfolge wichtig) ist:
\[n^k.\]
mit Zurüclegen (Reihenfolge wichtig) ist:
\[n^k.\]
Jede der \(k\) Positionen hat \(n\) Möglichkeiten.
Beispiel: Wie viele 4-stellige PINs aus 0–9 (mit Wiederholung)? \(10^4 = 10{,}000\).
Beispiel: Wie viele 4-stellige PINs aus 0–9 (mit Wiederholung)? \(10^4 = 10{,}000\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Die Anzahl der geordneten Auswahlen von \(k\) aus \(n\) Objekten<br><strong>mit Zurüclegen</strong> (Reihenfolge wichtig) ist:<br>\[{{c1::n^k}}.\] | |
| Extra | Jede der \(k\) Positionen hat \(n\) Möglichkeiten.<br>Beispiel: Wie viele 4-stellige PINs aus 0–9 (mit Wiederholung)? \(10^4 = 10{,}000\). |
Note 14: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
H#LoquJg]}
Previous
Note did not exist
New Note
Front
Für den Binomialkoeffizienten gelten:
Symmetrie: \(\binom{n}{k} = {{c1::\binom{n}{n-k}}}\)
Randfälle: \(\binom{n}{0} = 1\), \(\binom{n}{n} = 1\), \(\binom{n}{1} = n\)
Rekursion (Pascalsches Dreieck): \(\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k}}}\)
Symmetrie: \(\binom{n}{k} = {{c1::\binom{n}{n-k}}}\)
Randfälle: \(\binom{n}{0} = 1\), \(\binom{n}{n} = 1\), \(\binom{n}{1} = n\)
Rekursion (Pascalsches Dreieck): \(\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k}}}\)
Back
Für den Binomialkoeffizienten gelten:
Symmetrie: \(\binom{n}{k} = {{c1::\binom{n}{n-k}}}\)
Randfälle: \(\binom{n}{0} = 1\), \(\binom{n}{n} = 1\), \(\binom{n}{1} = n\)
Rekursion (Pascalsches Dreieck): \(\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k}}}\)
Symmetrie: \(\binom{n}{k} = {{c1::\binom{n}{n-k}}}\)
Randfälle: \(\binom{n}{0} = 1\), \(\binom{n}{n} = 1\), \(\binom{n}{1} = n\)
Rekursion (Pascalsches Dreieck): \(\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k}}}\)
Rekursion: Entweder das \(n\)-te Element ist in der Auswahl (dann \(\binom{n-1}{k-1}\)) oder nicht (dann \(\binom{n-1}{k}\)).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Für den Binomialkoeffizienten gelten:<br>Symmetrie: \(\binom{n}{k} = {{c1::\binom{n}{n-k}}}\)<br>Randfälle: \(\binom{n}{0} = {{c2::1}}\), \(\binom{n}{n} = {{c2::1}}\), \(\binom{n}{1} = {{c2::n}}\)<br>Rekursion (Pascalsches Dreieck): \(\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k}}}\) | |
| Extra | Rekursion: Entweder das \(n\)-te Element ist in der Auswahl (dann \(\binom{n-1}{k-1}\)) oder nicht (dann \(\binom{n-1}{k}\)). |
Note 15: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
JF0l2bCbMG
Previous
Note did not exist
New Note
Front
Die Anzahl der Möglichkeiten, \(k\) Objekte aus \(n\) Sorten
mit Zurüclegen zu wählen (Reihenfolge egal) (Multiset) ist:
\[\binom{n + k - 1}{k} = {{c1::\frac{(n+k-1)!}{k!\,(n-1)!}}}.\]
mit Zurüclegen zu wählen (Reihenfolge egal) (Multiset) ist:
\[\binom{n + k - 1}{k} = {{c1::\frac{(n+k-1)!}{k!\,(n-1)!}}}.\]
Back
Die Anzahl der Möglichkeiten, \(k\) Objekte aus \(n\) Sorten
mit Zurüclegen zu wählen (Reihenfolge egal) (Multiset) ist:
\[\binom{n + k - 1}{k} = {{c1::\frac{(n+k-1)!}{k!\,(n-1)!}}}.\]
mit Zurüclegen zu wählen (Reihenfolge egal) (Multiset) ist:
\[\binom{n + k - 1}{k} = {{c1::\frac{(n+k-1)!}{k!\,(n-1)!}}}.\]
Auch bekannt als „Sterne und Striche“ (Stars and Bars).
Beispiel: Wie viele Möglichkeiten, 3 Kugeln aus {rot, blau, grün} mit Zurüclegen zu ziehen?
\(\binom{3+3-1}{3} = \binom{5}{3} = 10\).
Beispiel: Wie viele Möglichkeiten, 3 Kugeln aus {rot, blau, grün} mit Zurüclegen zu ziehen?
\(\binom{3+3-1}{3} = \binom{5}{3} = 10\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Die Anzahl der Möglichkeiten, \(k\) Objekte aus \(n\) Sorten<br><strong>mit Zurüclegen</strong> zu wählen (Reihenfolge egal) (Multiset) ist:<br>\[\binom{n + k - 1}{k} = {{c1::\frac{(n+k-1)!}{k!\,(n-1)!}}}.\] | |
| Extra | Auch bekannt als „Sterne und Striche“ (Stars and Bars).<br>Beispiel: Wie viele Möglichkeiten, 3 Kugeln aus {rot, blau, grün} mit Zurüclegen zu ziehen?<br>\(\binom{3+3-1}{3} = \binom{5}{3} = 10\). |
Note 16: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
MrF3sR7oMk
Previous
Note did not exist
New Note
Front
Wie viele Möglichkeiten gibt es, \(k\) Objekte aus \(n\) zu wählen?
| Reihenfolge wichtig | Reihenfolge egal | |
|---|---|---|
| Ohne Zurüclegen | {{c1::\(\dfrac{n!}{(n-k)!}\)}} | {{c2::\(\dbinom{n}{k}\)}} |
| Mit Zurüclegen | \(n^k\) | {{c4::\(\dbinom{n+k-1}{k}\)}} |
Back
Wie viele Möglichkeiten gibt es, \(k\) Objekte aus \(n\) zu wählen?
| Reihenfolge wichtig | Reihenfolge egal | |
|---|---|---|
| Ohne Zurüclegen | {{c1::\(\dfrac{n!}{(n-k)!}\)}} | {{c2::\(\dbinom{n}{k}\)}} |
| Mit Zurüclegen | \(n^k\) | {{c4::\(\dbinom{n+k-1}{k}\)}} |
Eselsbrücke: geordnet ohne = Permutation, ungeordnet ohne = Kombination,
geordnet mit = Wort über Alphabet, ungeordnet mit = Multiset (Sterne & Striche).
geordnet mit = Wort über Alphabet, ungeordnet mit = Multiset (Sterne & Striche).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Wie viele Möglichkeiten gibt es, \(k\) Objekte aus \(n\) zu wählen?<br><br><table><tr><th></th><th>Reihenfolge wichtig</th><th>Reihenfolge egal</th></tr><tr><th>Ohne Zurüclegen</th><td>{{c1::\(\dfrac{n!}{(n-k)!}\)}}</td><td>{{c2::\(\dbinom{n}{k}\)}}</td></tr><tr><th>Mit Zurüclegen</th><td>{{c3::\(n^k\)}}</td><td>{{c4::\(\dbinom{n+k-1}{k}\)}}</td></tr></table> | |
| Extra | Eselsbrücke: geordnet ohne = Permutation, ungeordnet ohne = Kombination,<br>geordnet mit = Wort über Alphabet, ungeordnet mit = Multiset (Sterne & Striche). |
Note 17: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
R[%A*qUOry
Previous
Note did not exist
New Note
Front
Um \(\mathbb{E}[X]\) zu berechnen, schreibe \(X\) als Summe von Indikatoren:
\[X = {{c1::X_{A_1} + X_{A_2} + \cdots + X_{A_n}}},\]
dann gilt per Linearität:
\[\mathbb{E}[X] = \Pr[A_1] + \Pr[A_2] + \cdots + \Pr[A_n].\]
\[X = {{c1::X_{A_1} + X_{A_2} + \cdots + X_{A_n}}},\]
dann gilt per Linearität:
\[\mathbb{E}[X] = \Pr[A_1] + \Pr[A_2] + \cdots + \Pr[A_n].\]
Back
Um \(\mathbb{E}[X]\) zu berechnen, schreibe \(X\) als Summe von Indikatoren:
\[X = {{c1::X_{A_1} + X_{A_2} + \cdots + X_{A_n}}},\]
dann gilt per Linearität:
\[\mathbb{E}[X] = \Pr[A_1] + \Pr[A_2] + \cdots + \Pr[A_n].\]
\[X = {{c1::X_{A_1} + X_{A_2} + \cdots + X_{A_n}}},\]
dann gilt per Linearität:
\[\mathbb{E}[X] = \Pr[A_1] + \Pr[A_2] + \cdots + \Pr[A_n].\]
Unabhängigkeit nicht nötig!
Beispiel: Erwartete Anzahl Fixpunkte einer zufälligen Permutation von \([n]\)?
\(X_i = [i \text{ ist Fixpunkt}]\), \(\Pr[X_i = 1] = \frac{1}{n}\), also \(\mathbb{E}[X] = n \cdot \frac{1}{n} = 1\).
Beispiel: Erwartete Anzahl Fixpunkte einer zufälligen Permutation von \([n]\)?
\(X_i = [i \text{ ist Fixpunkt}]\), \(\Pr[X_i = 1] = \frac{1}{n}\), also \(\mathbb{E}[X] = n \cdot \frac{1}{n} = 1\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Um \(\mathbb{E}[X]\) zu berechnen, schreibe \(X\) als Summe von Indikatoren:<br>\[X = {{c1::X_{A_1} + X_{A_2} + \cdots + X_{A_n}}},\]<br>dann gilt per Linearität:<br>\[\mathbb{E}[X] = {{c2::\Pr[A_1] + \Pr[A_2] + \cdots + \Pr[A_n]}}.\] | |
| Extra | <strong>Unabhängigkeit nicht nötig!</strong><br>Beispiel: Erwartete Anzahl Fixpunkte einer zufälligen Permutation von \([n]\)?<br>\(X_i = [i \text{ ist Fixpunkt}]\), \(\Pr[X_i = 1] = \frac{1}{n}\), also \(\mathbb{E}[X] = n \cdot \frac{1}{n} = 1\). |
Note 18: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
RxK1aiA$%s
Previous
Note did not exist
New Note
Front
Die Anzahl der geordneten Auswahlen von \(k\) aus \(n\) Objekten
ohne Zurüclegen (Reihenfolge wichtig) ist:
\[P(n, k) = {{c1::\frac{n!}{(n-k)!}}} = n \cdot (n-1) \cdots (n-k+1).\]
Speziell: Alle \(n\) Objekte anordnen: \(n!\) Möglichkeiten.
ohne Zurüclegen (Reihenfolge wichtig) ist:
\[P(n, k) = {{c1::\frac{n!}{(n-k)!}}} = n \cdot (n-1) \cdots (n-k+1).\]
Speziell: Alle \(n\) Objekte anordnen: \(n!\) Möglichkeiten.
Back
Die Anzahl der geordneten Auswahlen von \(k\) aus \(n\) Objekten
ohne Zurüclegen (Reihenfolge wichtig) ist:
\[P(n, k) = {{c1::\frac{n!}{(n-k)!}}} = n \cdot (n-1) \cdots (n-k+1).\]
Speziell: Alle \(n\) Objekte anordnen: \(n!\) Möglichkeiten.
ohne Zurüclegen (Reihenfolge wichtig) ist:
\[P(n, k) = {{c1::\frac{n!}{(n-k)!}}} = n \cdot (n-1) \cdots (n-k+1).\]
Speziell: Alle \(n\) Objekte anordnen: \(n!\) Möglichkeiten.
Beispiel: Wie viele 3-stellige PINs aus den Ziffern 0–9 ohne Wiederholung?
\(P(10,3) = 10 \cdot 9 \cdot 8 = 720\).
\(P(10,3) = 10 \cdot 9 \cdot 8 = 720\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Die Anzahl der geordneten Auswahlen von \(k\) aus \(n\) Objekten<br><strong>ohne Zurüclegen</strong> (Reihenfolge wichtig) ist:<br>\[P(n, k) = {{c1::\frac{n!}{(n-k)!}}} = {{c2::n \cdot (n-1) \cdots (n-k+1)}}.\]<br>Speziell: Alle \(n\) Objekte anordnen: \({{c3::n!}}\) Möglichkeiten. | |
| Extra | Beispiel: Wie viele 3-stellige PINs aus den Ziffern 0–9 ohne Wiederholung?<br>\(P(10,3) = 10 \cdot 9 \cdot 8 = 720\). |
Note 19: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
S1a)g3U}sr
Previous
Note did not exist
New Note
Front
Gilt für \(G = (V, E)\): Jeder induzierte Subgraph von \(G\) enthält einen Knoten mit Grad \(\leq k\),
so gilt \[\chi(G) \leq k + 1\]
und eine solche Färbung ist in \(O(|E|)\) findbar.
so gilt \[\chi(G) \leq k + 1\]
und eine solche Färbung ist in \(O(|E|)\) findbar.
Back
Gilt für \(G = (V, E)\): Jeder induzierte Subgraph von \(G\) enthält einen Knoten mit Grad \(\leq k\),
so gilt \[\chi(G) \leq k + 1\]
und eine solche Färbung ist in \(O(|E|)\) findbar.
so gilt \[\chi(G) \leq k + 1\]
und eine solche Färbung ist in \(O(|E|)\) findbar.
Algorithmus: Knoten mit Grad \(\leq k\) wiederholt entfernen (Reihenfolge speichern).
In umgekehrter Reihenfolge einfärben — jeder Knoten hat dann \(\leq k\) bereits gefärbte Nachbarn.
Anwendung: Planare Graphen erfüllen dies mit \(k = 5\), also \(\chi \leq 6\).
In umgekehrter Reihenfolge einfärben — jeder Knoten hat dann \(\leq k\) bereits gefärbte Nachbarn.
Anwendung: Planare Graphen erfüllen dies mit \(k = 5\), also \(\chi \leq 6\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Gilt für \(G = (V, E)\): {{c1::Jeder induzierte Subgraph von \(G\) enthält einen Knoten mit Grad \(\leq k\)}},<br>so gilt \[\chi(G) \leq {{c2::k + 1}}\]<br>und eine solche Färbung ist in \(O(|E|)\) findbar. | |
| Extra | Algorithmus: Knoten mit Grad \(\leq k\) wiederholt entfernen (Reihenfolge speichern).<br>In umgekehrter Reihenfolge einfärben — jeder Knoten hat dann \(\leq k\) bereits gefärbte Nachbarn.<br>Anwendung: Planare Graphen erfüllen dies mit \(k = 5\), also \(\chi \leq 6\). |
Note 20: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
X%!FejeNGl
Previous
Note did not exist
New Note
Front
Der Satz von Bayes lässt sich als Update-Regel schreiben:
\[\text{Posterior} \propto {{c2::\text{Likelihood} \times \text{Prior}}}.\]
D.h.: \(\Pr[H \mid E] \propto \Pr[E \mid H] \cdot \Pr[H]\).
\[\text{Posterior} \propto {{c2::\text{Likelihood} \times \text{Prior}}}.\]
D.h.: \(\Pr[H \mid E] \propto \Pr[E \mid H] \cdot \Pr[H]\).
Back
Der Satz von Bayes lässt sich als Update-Regel schreiben:
\[\text{Posterior} \propto {{c2::\text{Likelihood} \times \text{Prior}}}.\]
D.h.: \(\Pr[H \mid E] \propto \Pr[E \mid H] \cdot \Pr[H]\).
\[\text{Posterior} \propto {{c2::\text{Likelihood} \times \text{Prior}}}.\]
D.h.: \(\Pr[H \mid E] \propto \Pr[E \mid H] \cdot \Pr[H]\).
Das \(\propto\) (proportional zu) bedeutet: durch \(\Pr[E]\) normieren.
Intuition: Der Prior ist die Ausgangsmeinung; die Likelihood gewichtet, wie stark die
Evidenz diese Meinung in Richtung \(H\) verschiebt.
Intuition: Der Prior ist die Ausgangsmeinung; die Likelihood gewichtet, wie stark die
Evidenz diese Meinung in Richtung \(H\) verschiebt.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Der Satz von Bayes lässt sich als Update-Regel schreiben:<br>\[{{c1::\text{Posterior}}} \propto {{c2::\text{Likelihood} \times \text{Prior}}}.\]<br>D.h.: \(\Pr[H \mid E] \propto \Pr[E \mid H] \cdot \Pr[H]\). | |
| Extra | Das \(\propto\) (proportional zu) bedeutet: durch \(\Pr[E]\) normieren.<br>Intuition: Der Prior ist die Ausgangsmeinung; die Likelihood gewichtet, wie stark die<br>Evidenz diese Meinung in Richtung \(H\) verschiebt. |
Note 21: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
XQ3mqcUc7W
Previous
Note did not exist
New Note
Front
Eine Zufallsvariable auf \(\Omega\) ist eine Funktion \(X\colon \Omega \to \mathbb{R}\).
\(\Pr[X = x] := {{c2::\Pr[\{\omega \in \Omega : X(\omega) = x\}]}}.\)
\(\Pr[X = x] := {{c2::\Pr[\{\omega \in \Omega : X(\omega) = x\}]}}.\)
Back
Eine Zufallsvariable auf \(\Omega\) ist eine Funktion \(X\colon \Omega \to \mathbb{R}\).
\(\Pr[X = x] := {{c2::\Pr[\{\omega \in \Omega : X(\omega) = x\}]}}.\)
\(\Pr[X = x] := {{c2::\Pr[\{\omega \in \Omega : X(\omega) = x\}]}}.\)
Zufallsvariablen abstrahieren Ergebnisse zu numerischen Werten.
Beispiel: Bei 2 Würfelwürfen ist \(X =\) "Summe der Augenzahlen" eine Zufallsvariable.
Beispiel: Bei 2 Würfelwürfen ist \(X =\) "Summe der Augenzahlen" eine Zufallsvariable.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Eine {{c1::Zufallsvariable}} auf \(\Omega\) ist eine Funktion \(X\colon \Omega \to \mathbb{R}\).<br><br>\(\Pr[X = x] := {{c2::\Pr[\{\omega \in \Omega : X(\omega) = x\}]}}.\) | |
| Extra | Zufallsvariablen abstrahieren Ergebnisse zu numerischen Werten.<br>Beispiel: Bei 2 Würfelwürfen ist \(X =\) "Summe der Augenzahlen" eine Zufallsvariable. |
Note 22: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID:
added
Note Type: Horvath Classic
GUID:
[baaJj9miG
Previous
Note did not exist
New Note
Front
Was ist der Unterschied zwischen paarweiser und stochastischer (gegenseitiger) Unabhängigkeit von \(n\) Ereignissen?
Back
Was ist der Unterschied zwischen paarweiser und stochastischer (gegenseitiger) Unabhängigkeit von \(n\) Ereignissen?
Paarweise: \(\Pr[A_i \cap A_j] = \Pr[A_i]\Pr[A_j]\) für alle \(i \neq j\).
Stochastisch (mutual): Bedingung gilt für ALLE nichtleeren Teilmengen \(I \subseteq [n]\).
Paarweise Unabhängigkeit \(\not\Rightarrow\) stochastische Unabhängigkeit!
Stochastisch (mutual): Bedingung gilt für ALLE nichtleeren Teilmengen \(I \subseteq [n]\).
Paarweise Unabhängigkeit \(\not\Rightarrow\) stochastische Unabhängigkeit!
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | Was ist der Unterschied zwischen paarweiser und stochastischer (gegenseitiger) Unabhängigkeit von \(n\) Ereignissen? | |
| Back | Paarweise: \(\Pr[A_i \cap A_j] = \Pr[A_i]\Pr[A_j]\) für alle \(i \neq j\).<br>Stochastisch (mutual): Bedingung gilt für ALLE nichtleeren Teilmengen \(I \subseteq [n]\).<br><br>Paarweise Unabhängigkeit \(\not\Rightarrow\) stochastische Unabhängigkeit! |
Note 23: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
_0Pe(qekc5
Previous
Note did not exist
New Note
Front
Es gilt:
\[\sum_{k=0}^{n} \binom{n}{k} = 2^n.\]
\[\sum_{k=0}^{n} \binom{n}{k} = 2^n.\]
Back
Es gilt:
\[\sum_{k=0}^{n} \binom{n}{k} = 2^n.\]
\[\sum_{k=0}^{n} \binom{n}{k} = 2^n.\]
Beweis: Setze \(x = y = 1\) im Binomialsatz: \((1+1)^n = \sum_{k=0}^n \binom{n}{k}\).
Interpretation: Anzahl aller Teilmengen einer \(n\)-elementigen Menge ist \(2^n\).
Interpretation: Anzahl aller Teilmengen einer \(n\)-elementigen Menge ist \(2^n\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Es gilt:<br>\[\sum_{k=0}^{n} \binom{n}{k} = {{c1::2^n}}.\] | |
| Extra | Beweis: Setze \(x = y = 1\) im Binomialsatz: \((1+1)^n = \sum_{k=0}^n \binom{n}{k}\).<br>Interpretation: Anzahl aller Teilmengen einer \(n\)-elementigen Menge ist \(2^n\). |
Note 24: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
a1rkJfjyfd
Previous
Note did not exist
New Note
Front
Eine Zufallsvariable \(X \sim \text{Bernoulli}(p)\) nimmt Werte an:
\[\Pr[X = 1] = p, \qquad \Pr[X = 0] = 1-p.\]
Erwartungswert: \(\mathbb{E}[X] = p\).
\[\Pr[X = 1] = p, \qquad \Pr[X = 0] = 1-p.\]
Erwartungswert: \(\mathbb{E}[X] = p\).
Back
Eine Zufallsvariable \(X \sim \text{Bernoulli}(p)\) nimmt Werte an:
\[\Pr[X = 1] = p, \qquad \Pr[X = 0] = 1-p.\]
Erwartungswert: \(\mathbb{E}[X] = p\).
\[\Pr[X = 1] = p, \qquad \Pr[X = 0] = 1-p.\]
Erwartungswert: \(\mathbb{E}[X] = p\).
Modelliert einen einzelnen Münzwurf (mit verzerrter Münze).
Indikator-ZV \(X_A\) ist genau \(\text{Bernoulli}(\Pr[A])\).
Indikator-ZV \(X_A\) ist genau \(\text{Bernoulli}(\Pr[A])\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Eine Zufallsvariable \(X \sim \text{Bernoulli}(p)\) nimmt Werte an:<br>\[\Pr[X = 1] = {{c1::p}}, \qquad \Pr[X = 0] = {{c1::1-p}}.\]<br>Erwartungswert: \(\mathbb{E}[X] = {{c2::p}}\). | |
| Extra | Modelliert einen einzelnen Münzwurf (mit verzerrter Münze).<br>Indikator-ZV \(X_A\) ist genau \(\text{Bernoulli}(\Pr[A])\). |
Note 25: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
hFx`}69EnK
Previous
Note did not exist
New Note
Front
Der Algorithmus von Hopcroft-Karp verbessert den augmentierenden-Pfad-Algorithmus,
indem er pro Iteration nicht nur einen, sondern eine
inklusionsmaximale Menge paarweise disjunkter kürzester augmentierender Pfade
findet und simultan augmentiert.
Die while-Schleife wird nur \(O(\sqrt{|V|})\) mal durchlaufen.
Proof Sketch Included
indem er pro Iteration nicht nur einen, sondern eine
inklusionsmaximale Menge paarweise disjunkter kürzester augmentierender Pfade
findet und simultan augmentiert.
Die while-Schleife wird nur \(O(\sqrt{|V|})\) mal durchlaufen.
Proof Sketch Included
Back
Der Algorithmus von Hopcroft-Karp verbessert den augmentierenden-Pfad-Algorithmus,
indem er pro Iteration nicht nur einen, sondern eine
inklusionsmaximale Menge paarweise disjunkter kürzester augmentierender Pfade
findet und simultan augmentiert.
Die while-Schleife wird nur \(O(\sqrt{|V|})\) mal durchlaufen.
Proof Sketch Included
indem er pro Iteration nicht nur einen, sondern eine
inklusionsmaximale Menge paarweise disjunkter kürzester augmentierender Pfade
findet und simultan augmentiert.
Die while-Schleife wird nur \(O(\sqrt{|V|})\) mal durchlaufen.
Proof Sketch Included
Gesamtlaufzeit: \(O(\sqrt{|V|} \cdot (|V| + |E|))\).
Proof Sketch
Augmentieren mit kürzestem Pfad \(P\) erhöht die Länge des nächsten kürzesten Pfades um mindestens 2.
Proof Sketch
Augmentieren mit kürzestem Pfad \(P\) erhöht die Länge des nächsten kürzesten Pfades um mindestens 2.
- Sei M ein Matching, für das der kürzeste augmentierende Pfad Länge k hat und M' ein anderes beliebiges Matching. Dann gilt \(|M'| \le |M| + \frac{|V|}{k + 1}\)
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Der Algorithmus von Hopcroft-Karp verbessert den augmentierenden-Pfad-Algorithmus,<br>indem er pro Iteration nicht nur einen, sondern eine<br>{{c1::inklusionsmaximale Menge paarweise disjunkter kürzester augmentierender Pfade}}<br>findet und simultan augmentiert.<br><br>Die while-Schleife wird nur \(O({{c2::\sqrt{|V|}}})\) mal durchlaufen.<br><i>Proof Sketch Included</i> | |
| Extra | Gesamtlaufzeit: \(O(\sqrt{|V|} \cdot (|V| + |E|))\).<br><br><b>Proof Sketch<br></b>Augmentieren mit kürzestem Pfad \(P\) erhöht die Länge des nächsten kürzesten Pfades um mindestens 2.<ul><li>Sei M ein Matching, für das der kürzeste augmentierende Pfad Länge k hat und M' ein anderes beliebiges Matching. Dann gilt \(|M'| \le |M| + \frac{|V|}{k + 1}\)</li></ul> |
Note 26: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
hk@olmS7-#
Previous
Note did not exist
New Note
Front
Für Ereignisse \(A, B\) mit \(\Pr[A], \Pr[B] > 0\) gilt:
\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B \mid A] = \Pr[B] \cdot \Pr[A \mid B].\]
Umgestellt ergibt sich direkt der Satz von Bayes.
\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B \mid A] = \Pr[B] \cdot \Pr[A \mid B].\]
Umgestellt ergibt sich direkt der Satz von Bayes.
Back
Für Ereignisse \(A, B\) mit \(\Pr[A], \Pr[B] > 0\) gilt:
\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B \mid A] = \Pr[B] \cdot \Pr[A \mid B].\]
Umgestellt ergibt sich direkt der Satz von Bayes.
\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B \mid A] = \Pr[B] \cdot \Pr[A \mid B].\]
Umgestellt ergibt sich direkt der Satz von Bayes.
Beide Seiten sind gleich, weil \(\Pr[A \cap B]\) symmetrisch in \(A\) und \(B\) ist.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Für Ereignisse \(A, B\) mit \(\Pr[A], \Pr[B] > 0\) gilt:<br>\[\Pr[A \cap B] = {{c1::\Pr[A] \cdot \Pr[B \mid A]}} = {{c1::\Pr[B] \cdot \Pr[A \mid B]}}.\]<br>Umgestellt ergibt sich direkt der Satz von Bayes. | |
| Extra | Beide Seiten sind gleich, weil \(\Pr[A \cap B]\) symmetrisch in \(A\) und \(B\) ist. |
Note 27: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
jc@5=H8@[9
Previous
Note did not exist
New Note
Front
Satz von Bayes: Seien \(A, B\) Ereignisse mit \(\Pr[B] > 0\). Dann gilt:
\[\Pr[A|B] = {{c1::\frac{\Pr[B|A] \cdot \Pr[A]}{\Pr[B]}}}.\]
\[\Pr[A|B] = {{c1::\frac{\Pr[B|A] \cdot \Pr[A]}{\Pr[B]}}}.\]
Back
Satz von Bayes: Seien \(A, B\) Ereignisse mit \(\Pr[B] > 0\). Dann gilt:
\[\Pr[A|B] = {{c1::\frac{\Pr[B|A] \cdot \Pr[A]}{\Pr[B]}}}.\]
\[\Pr[A|B] = {{c1::\frac{\Pr[B|A] \cdot \Pr[A]}{\Pr[B]}}}.\]
Folgt direkt: \(\Pr[A|B] = \frac{\Pr[A \cap B]}{\Pr[B]} = \frac{\Pr[B|A]\cdot\Pr[A]}{\Pr[B]}\).
Verallgemeinerung (Partition \(A_1,\ldots,A_n\)):
\(\Pr[A_i|B] = \frac{\Pr[B|A_i]\Pr[A_i]}{\sum_j \Pr[B|A_j]\Pr[A_j]}\).
Verallgemeinerung (Partition \(A_1,\ldots,A_n\)):
\(\Pr[A_i|B] = \frac{\Pr[B|A_i]\Pr[A_i]}{\sum_j \Pr[B|A_j]\Pr[A_j]}\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Satz von Bayes: Seien \(A, B\) Ereignisse mit \(\Pr[B] > 0\). Dann gilt:<br>\[\Pr[A|B] = {{c1::\frac{\Pr[B|A] \cdot \Pr[A]}{\Pr[B]}}}.\] | |
| Extra | Folgt direkt: \(\Pr[A|B] = \frac{\Pr[A \cap B]}{\Pr[B]} = \frac{\Pr[B|A]\cdot\Pr[A]}{\Pr[B]}\).<br>Verallgemeinerung (Partition \(A_1,\ldots,A_n\)):<br>\(\Pr[A_i|B] = \frac{\Pr[B|A_i]\Pr[A_i]}{\sum_j \Pr[B|A_j]\Pr[A_j]}\). |
Note 28: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Classic
GUID:
added
Note Type: Horvath Classic
GUID:
ms@ofzVlpa
Previous
Note did not exist
New Note
Front
Wie heißen die vier Terme im Satz von Bayes
\(\Pr[H \mid E] = \dfrac{\Pr[E \mid H] \cdot \Pr[H]}{\Pr[E]}\)?
\(\Pr[H \mid E] = \dfrac{\Pr[E \mid H] \cdot \Pr[H]}{\Pr[E]}\)?
Back
Wie heißen die vier Terme im Satz von Bayes
\(\Pr[H \mid E] = \dfrac{\Pr[E \mid H] \cdot \Pr[H]}{\Pr[E]}\)?
\(\Pr[H \mid E] = \dfrac{\Pr[E \mid H] \cdot \Pr[H]}{\Pr[E]}\)?
\(\Pr[H]\) — Prior (Vorab-Wahrscheinlichkeit): Glaube an \(H\) vor Beobachtung von \(E\).
\(\Pr[E \mid H]\) — Likelihood: Wie wahrscheinlich ist die Evidenz \(E\), wenn \(H\) gilt?
\(\Pr[H \mid E]\) — Posterior: Aktualisierter Glaube an \(H\) nach Beobachtung von \(E\).
\(\Pr[E]\) — Evidenz (Normierungskonstante): Gesamtwahrscheinlichkeit der Beobachtung.
\(\Pr[E \mid H]\) — Likelihood: Wie wahrscheinlich ist die Evidenz \(E\), wenn \(H\) gilt?
\(\Pr[H \mid E]\) — Posterior: Aktualisierter Glaube an \(H\) nach Beobachtung von \(E\).
\(\Pr[E]\) — Evidenz (Normierungskonstante): Gesamtwahrscheinlichkeit der Beobachtung.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Front | Wie heißen die vier Terme im Satz von Bayes<br>\(\Pr[H \mid E] = \dfrac{\Pr[E \mid H] \cdot \Pr[H]}{\Pr[E]}\)? | |
| Back | \(\Pr[H]\) — <strong>Prior</strong> (Vorab-Wahrscheinlichkeit): Glaube an \(H\) vor Beobachtung von \(E\).<br>\(\Pr[E \mid H]\) — <strong>Likelihood</strong>: Wie wahrscheinlich ist die Evidenz \(E\), wenn \(H\) gilt?<br>\(\Pr[H \mid E]\) — <strong>Posterior</strong>: Aktualisierter Glaube an \(H\) nach Beobachtung von \(E\).<br>\(\Pr[E]\) — <strong>Evidenz</strong> (Normierungskonstante): Gesamtwahrscheinlichkeit der Beobachtung. |
Note 29: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
o78LP-Mw-W
Previous
Note did not exist
New Note
Front
Für alle \(k \geq 2\) gibt es einen dreiecksfreien Graphen \(G_k\) mit
\(\chi(G_k) \geq k\).
(Mycielski-Konstruktion)
\(\chi(G_k) \geq k\).
(Mycielski-Konstruktion)
Back
Für alle \(k \geq 2\) gibt es einen dreiecksfreien Graphen \(G_k\) mit
\(\chi(G_k) \geq k\).
(Mycielski-Konstruktion)
\(\chi(G_k) \geq k\).
(Mycielski-Konstruktion)
Konstruktion: Aus \(G_k = (V_k, E_k)\) mit \(V_k = \{v_1,\ldots,v_n\}\) bilde \(G_{k+1}\):
Füge Knoten \(w_1,\ldots,w_n, z\) hinzu. \(w_i\) ist mit allen Nachbarn von \(v_i\) verbunden (aber nicht mit \(v_i\) selbst). \(z\) ist mit allen \(w_i\) verbunden.
Der neue Graph ist dreiecksfrei und braucht eine Farbe mehr als \(G_k\).
Füge Knoten \(w_1,\ldots,w_n, z\) hinzu. \(w_i\) ist mit allen Nachbarn von \(v_i\) verbunden (aber nicht mit \(v_i\) selbst). \(z\) ist mit allen \(w_i\) verbunden.
Der neue Graph ist dreiecksfrei und braucht eine Farbe mehr als \(G_k\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Für alle \(k \geq 2\) gibt es einen {{c1::dreiecksfreien}} Graphen \(G_k\) mit<br>\(\chi(G_k) \geq {{c2::k}}\).<br><br>({{c3::Mycielski-Konstruktion}}) | |
| Extra | Konstruktion: Aus \(G_k = (V_k, E_k)\) mit \(V_k = \{v_1,\ldots,v_n\}\) bilde \(G_{k+1}\):<br>Füge Knoten \(w_1,\ldots,w_n, z\) hinzu. \(w_i\) ist mit allen Nachbarn von \(v_i\) verbunden (aber nicht mit \(v_i\) selbst). \(z\) ist mit allen \(w_i\) verbunden.<br>Der neue Graph ist dreiecksfrei und braucht eine Farbe mehr als \(G_k\). |
Note 30: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
qsXztu}x3_
Previous
Note did not exist
New Note
Front
Ereignisse \(A_1, \ldots, A_n\) heißen stochastisch unabhängig,
falls für alle nichtleeren \(I \subseteq \{1,\ldots,n\}\) gilt:
\[{{c2::\Pr\!\left[\bigcap_{i \in I} A_i\right] = \prod_{i \in I} \Pr[A_i]}}.\]
falls für alle nichtleeren \(I \subseteq \{1,\ldots,n\}\) gilt:
\[{{c2::\Pr\!\left[\bigcap_{i \in I} A_i\right] = \prod_{i \in I} \Pr[A_i]}}.\]
Back
Ereignisse \(A_1, \ldots, A_n\) heißen stochastisch unabhängig,
falls für alle nichtleeren \(I \subseteq \{1,\ldots,n\}\) gilt:
\[{{c2::\Pr\!\left[\bigcap_{i \in I} A_i\right] = \prod_{i \in I} \Pr[A_i]}}.\]
falls für alle nichtleeren \(I \subseteq \{1,\ldots,n\}\) gilt:
\[{{c2::\Pr\!\left[\bigcap_{i \in I} A_i\right] = \prod_{i \in I} \Pr[A_i]}}.\]
Achtung: Paarweise Unabhängigkeit (\(\Pr[A_i \cap A_j] = \Pr[A_i]\Pr[A_j]\) für alle \(i \neq j\)) impliziert NICHT stochastische Unabhängigkeit!
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Ereignisse \(A_1, \ldots, A_n\) heißen {{c1::stochastisch unabhängig}},<br>falls für alle nichtleeren \(I \subseteq \{1,\ldots,n\}\) gilt:<br>\[{{c2::\Pr\!\left[\bigcap_{i \in I} A_i\right] = \prod_{i \in I} \Pr[A_i]}}.\] | |
| Extra | Achtung: Paarweise Unabhängigkeit (\(\Pr[A_i \cap A_j] = \Pr[A_i]\Pr[A_j]\) für alle \(i \neq j\)) impliziert NICHT stochastische Unabhängigkeit! |
Note 31: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
tHY-Qji=0u
Previous
Note did not exist
New Note
Front
Zwei Ereignisse \(A\) und \(B\) heißen stochastisch unabhängig, falls
\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B].\]
Falls \(\Pr[B] > 0\): äquivalent zu \(\Pr[A|B] = \Pr[A]\).
\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B].\]
Falls \(\Pr[B] > 0\): äquivalent zu \(\Pr[A|B] = \Pr[A]\).
Back
Zwei Ereignisse \(A\) und \(B\) heißen stochastisch unabhängig, falls
\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B].\]
Falls \(\Pr[B] > 0\): äquivalent zu \(\Pr[A|B] = \Pr[A]\).
\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B].\]
Falls \(\Pr[B] > 0\): äquivalent zu \(\Pr[A|B] = \Pr[A]\).
Intuition: Das Eintreten von \(B\) gibt keine Information über \(A\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Zwei Ereignisse \(A\) und \(B\) heißen {{c1::stochastisch unabhängig}}, falls<br>\[{{c2::\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]}}.\]<br>Falls \(\Pr[B] > 0\): äquivalent zu {{c3::\(\Pr[A|B] = \Pr[A]\)}}. | |
| Extra | Intuition: Das Eintreten von \(B\) gibt keine Information über \(A\). |
Note 32: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
vcLegjCIrE
Previous
Note did not exist
New Note
Front
Jede Menge \(A\) lässt sich bezüglich eines Ereignisses \(B\) aufteilen:
\[A = (A \cap B) \cup (A \cap B^c),\]
wobei die zwei Teile disjunkt sind. Daher:
\[|A| = |A \cap B| + |A \cap B^c|.\]
\[A = (A \cap B) \cup (A \cap B^c),\]
wobei die zwei Teile disjunkt sind. Daher:
\[|A| = |A \cap B| + |A \cap B^c|.\]
Back
Jede Menge \(A\) lässt sich bezüglich eines Ereignisses \(B\) aufteilen:
\[A = (A \cap B) \cup (A \cap B^c),\]
wobei die zwei Teile disjunkt sind. Daher:
\[|A| = |A \cap B| + |A \cap B^c|.\]
\[A = (A \cap B) \cup (A \cap B^c),\]
wobei die zwei Teile disjunkt sind. Daher:
\[|A| = |A \cap B| + |A \cap B^c|.\]
Anwendung: Um \(|A|\) zu zählen, zähle separat „\(A\) und \(B\) tritt ein“ und
„\(A\) und \(B\) tritt nicht ein“.
Analogon: Satz der totalen Wahrscheinlichkeit \(\Pr[A] = \Pr[A|B]\Pr[B] + \Pr[A|B^c]\Pr[B^c]\).
„\(A\) und \(B\) tritt nicht ein“.
Analogon: Satz der totalen Wahrscheinlichkeit \(\Pr[A] = \Pr[A|B]\Pr[B] + \Pr[A|B^c]\Pr[B^c]\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Jede Menge \(A\) lässt sich bezüglich eines Ereignisses \(B\) aufteilen:<br>\[A = {{c1::(A \cap B) \cup (A \cap B^c)}},\]<br>wobei die zwei Teile disjunkt sind. Daher:<br>\[|A| = {{c2::|A \cap B| + |A \cap B^c|}}.\] | |
| Extra | Anwendung: Um \(|A|\) zu zählen, zähle separat „\(A\) und \(B\) tritt ein“ und<br>„\(A\) und \(B\) tritt nicht ein“.<br>Analogon: Satz der totalen Wahrscheinlichkeit \(\Pr[A] = \Pr[A|B]\Pr[B] + \Pr[A|B^c]\Pr[B^c]\). |
Note 33: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
x+3$}d{d2G
Previous
Note did not exist
New Note
Front
Statt \(|A|\) direkt zu zählen, kann man das Komplement zählen:
\[|A| = |\Omega| - |A^c|.\]
\[|A| = |\Omega| - |A^c|.\]
Back
Statt \(|A|\) direkt zu zählen, kann man das Komplement zählen:
\[|A| = |\Omega| - |A^c|.\]
\[|A| = |\Omega| - |A^c|.\]
Nützlich wenn „\(A\) tritt nicht ein“ einfacher zu zählen ist.
Beispiel: Wie viele Hände (5 aus 52) enthalten mindestens ein Ass?
Komplement: keine Asse = \(\binom{48}{5}\). Antwort: \(\binom{52}{5} - \binom{48}{5}\).
Beispiel: Wie viele Hände (5 aus 52) enthalten mindestens ein Ass?
Komplement: keine Asse = \(\binom{48}{5}\). Antwort: \(\binom{52}{5} - \binom{48}{5}\).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Statt \(|A|\) direkt zu zählen, kann man das Komplement zählen:<br>\[|A| = {{c1::|\Omega| - |A^c|}}.\] | |
| Extra | Nützlich wenn „\(A\) tritt nicht ein“ einfacher zu zählen ist.<br>Beispiel: Wie viele Hände (5 aus 52) enthalten mindestens ein Ass?<br>Komplement: keine Asse = \(\binom{48}{5}\). Antwort: \(\binom{52}{5} - \binom{48}{5}\). |
Note 34: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
xx#lC]f(3E
Previous
Note did not exist
New Note
Front
Der Erwartungswert einer Zufallsvariable \(X\) ist:
\[{{c2::\mathbb{E}[X] := \sum_{x} x \cdot \Pr[X = x]}},\]
wobei die Summe über alle Werte \(x\) läuft, die \(X\) annehmen kann.
\[{{c2::\mathbb{E}[X] := \sum_{x} x \cdot \Pr[X = x]}},\]
wobei die Summe über alle Werte \(x\) läuft, die \(X\) annehmen kann.
Back
Der Erwartungswert einer Zufallsvariable \(X\) ist:
\[{{c2::\mathbb{E}[X] := \sum_{x} x \cdot \Pr[X = x]}},\]
wobei die Summe über alle Werte \(x\) läuft, die \(X\) annehmen kann.
\[{{c2::\mathbb{E}[X] := \sum_{x} x \cdot \Pr[X = x]}},\]
wobei die Summe über alle Werte \(x\) läuft, die \(X\) annehmen kann.
Intuition: Gewichteter Durchschnitt aller möglichen Werte.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Der {{c1::Erwartungswert}} einer Zufallsvariable \(X\) ist:<br>\[{{c2::\mathbb{E}[X] := \sum_{x} x \cdot \Pr[X = x]}},\]<br>wobei die Summe über alle Werte \(x\) läuft, die \(X\) annehmen kann. | |
| Extra | Intuition: Gewichteter Durchschnitt aller möglichen Werte. |
Note 35: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
y9hMubH@3j
Previous
Note did not exist
New Note
Front
Der Binomialkoeffizient \(\binom{n}{k}\) zählt die Anzahl der
\(k\)-elementigen Teilmengen einer \(n\)-elementigen Menge:
\[\binom{n}{k} = {{c2::\frac{n!}{k!\,(n-k)!}}}.\]
Ausgesprochen: „\(n\) über \(k\)“. Definiert für \(0 \leq k \leq n\), sonst \(0\).
\(k\)-elementigen Teilmengen einer \(n\)-elementigen Menge:
\[\binom{n}{k} = {{c2::\frac{n!}{k!\,(n-k)!}}}.\]
Ausgesprochen: „\(n\) über \(k\)“. Definiert für \(0 \leq k \leq n\), sonst \(0\).
Back
Der Binomialkoeffizient \(\binom{n}{k}\) zählt die Anzahl der
\(k\)-elementigen Teilmengen einer \(n\)-elementigen Menge:
\[\binom{n}{k} = {{c2::\frac{n!}{k!\,(n-k)!}}}.\]
Ausgesprochen: „\(n\) über \(k\)“. Definiert für \(0 \leq k \leq n\), sonst \(0\).
\(k\)-elementigen Teilmengen einer \(n\)-elementigen Menge:
\[\binom{n}{k} = {{c2::\frac{n!}{k!\,(n-k)!}}}.\]
Ausgesprochen: „\(n\) über \(k\)“. Definiert für \(0 \leq k \leq n\), sonst \(0\).
Beziehung zu geordneter Auswahl: \(\binom{n}{k} = \frac{P(n,k)}{k!}\)
(durch \(k!\) teilen, weil Reihenfolge egal).
(durch \(k!\) teilen, weil Reihenfolge egal).
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Der {{c1::Binomialkoeffizient}} \(\binom{n}{k}\) zählt die Anzahl der<br>\(k\)-elementigen Teilmengen einer \(n\)-elementigen Menge:<br>\[\binom{n}{k} = {{c2::\frac{n!}{k!\,(n-k)!}}}.\]<br>Ausgesprochen: „\(n\) {{c3::über}} \(k\)“. Definiert für \(0 \leq k \leq n\), sonst \(0\). | |
| Extra | Beziehung zu geordneter Auswahl: \(\binom{n}{k} = \frac{P(n,k)}{k!}\)<br>(durch \(k!\) teilen, weil Reihenfolge egal). |
Note 36: ETH::2. Semester::A&W
Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID:
added
Note Type: Horvath Cloze
GUID:
yQa5-0YeQw
Previous
Note did not exist
New Note
Front
Für \(n\) gerade und \(\ell : \binom{[n]}{2} \to \mathbb{N}_0\) kann man in Zeit
\(O(n^3)\) ein minimales (gewichtsminimales) perfektes Matching in \(K_n\) finden.
\(O(n^3)\) ein minimales (gewichtsminimales) perfektes Matching in \(K_n\) finden.
Back
Für \(n\) gerade und \(\ell : \binom{[n]}{2} \to \mathbb{N}_0\) kann man in Zeit
\(O(n^3)\) ein minimales (gewichtsminimales) perfektes Matching in \(K_n\) finden.
\(O(n^3)\) ein minimales (gewichtsminimales) perfektes Matching in \(K_n\) finden.
Dies wird im Christofides-Algorithmus für das metrische TSP benötigt.
Field-by-field Comparison
| Field | Before | After |
|---|---|---|
| Text | Für \(n\) gerade und \(\ell : \binom{[n]}{2} \to \mathbb{N}_0\) kann man in Zeit<br>\(O({{c1::n^3}})\) ein {{c2::minimales (gewichtsminimales) perfektes Matching}} in \(K_n\) finden. | |
| Extra | Dies wird im Christofides-Algorithmus für das metrische TSP benötigt. |