Anki Deck Changes

Es gilt: \(\mathbb{E}[X_A] = \Pr[A]\).

Beweis: \(\mathbb{E}[X_A] = 1 \cdot \Pr[A] + 0 \cdot \Pr[A^c] = \Pr[A]\).

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)

Auch bekannt als „Sterne und Striche“ (Stars and Bars).

Beispiel:
Wie viele Möglichkeiten, 3 Kugeln aus {rot, blau, grün} mit Zurücklegen zu ziehen?
\(\binom{3+3-1}{3} = \binom{5}{3} = 10\).

Eselsbrücke:

• Reihenfolge wichtig, ohne Zurücklegen → Permutation
• Reihenfolge egal, ohne Zurücklegen → Kombination
• Reihenfolge wichtig, mit Zurücklegen → Wort über Alphabet
• Reihenfolge egal, mit Zurücklegen → Multiset (Sterne & Striche)

Beispiel:
Wie viele 3-stellige PINs aus den Ziffern 0–9 ohne Wiederholung?
\(P(10,3) = 10 \cdot 9 \cdot 8 = 720\).

\(\Pr[H \mid E] \propto \Pr[E \mid H] \cdot \Pr[H]\).

Das \(\propto\) (proportional zu) bedeutet, dass die Normierungskonstante \(\Pr[E]\) im Nenner fehlt.

Intuition:
Der Prior \(\Pr[H]\) ist unsere Ausgangsmeinung über \(H\). Die Likelihood \(\Pr[E \mid H]\) gewichtet, wie stark die beobachtete Evidenz \(E\) diese Meinung in Richtung \(H\) verschiebt.

Stochastische Unabhängigkeit ist die stärkere Forderung: Paarweise Unabhängigkeit allein reicht dafür nicht aus.

Paarweise Unabhängigkeit:
Für je zwei der \(n\) Ereignisse gilt, dass das eine keinen Einfluss auf die Wahrscheinlichkeit des anderen hat: \[\Pr[A_i \cap A_j] = \Pr[A_i]\,\Pr[A_j] \quad \text{für alle } i \neq j.\]Stochastische (gegenseitige) Unabhängigkeit:
Egal welche Teilmenge der \(n\) Ereignisse man betrachtet – ob Paare, Tripel, oder alle gleichzeitig – die Ereignisse beeinflussen sich gegenseitig nicht. Das heisst, das Wissen über beliebig viele der Ereignisse ändert die Wahrscheinlichkeit der übrigen nicht: \[\Pr\!\Big[\bigcap_{i \in I} A_i\Big] = \prod_{i \in I} \Pr[A_i] \quad \text{für alle } \emptyset \neq I \subseteq [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\).

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.

• 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}\)

Umgestellt ergibt sich direkt der Satz von Bayes.

Beide Seiten sind gleich, weil \(\Pr[A \cap B]\) symmetrisch in \(A\) und \(B\) ist.

(Satz von Bayes)

Es folgt direkt: \(\Pr[A\mid B] = \frac{\Pr[A \cap B]}{\Pr[B]} = \frac{\Pr[B\mid A]\cdot\Pr[A]}{\Pr[B]}\).
Verallgemeinerung (Partition \(A_1,\ldots,A_n\)):

\(\Pr[A_i\mid B] = \frac{\Pr[B\mid A_i]\Pr[A_i]}{\sum_j \Pr[B\mid A_j]\Pr[A_j]}\).

(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\).

Intuition:
Das Eintreten von \(B\) beeinflusst die Wahrscheinlichkeit von \(A\) nicht.

(\(0\) und \(\infty\) sind hier Kurzschreibweisen für das Verhalten im Grenzwert: \(0\) steht für „geht gegen \(0\)" und \(\infty\) für „geht gegen \(\infty\)".)

1. \(\sum a_n \geq 0\), \(\displaystyle L = \lim_{n\to\infty} \left| \frac{a_{n+1}}{a_n} \right|< 1\)
1. Choose \(q\) with \(L < q < 1\). Since \(\left| \frac{a_{n+1}}{a_n} \right| \to L\), there exists \(N\) such that for all \(n \geq N: \left|\frac{a_{n+1}}{a_n} \right| \leq q\) \(\implies\) \(\left|a_{N+k}\right|\leq \left|a_N \right|\cdot q^k\)
2. So \(\sum_{k=0}^{\infty} \left| a_{N+k} \right|\) \(\leq \left| a_N \right| \sum_{k=0}^{\infty} q^k\)\(= \frac{\left| a_N \right|}{1-q}\)\(< \infty\) (geometric series, \(q < 1\) ).
3. Hence \(\sum a_n\) converges.
2. \(\sum a_n \geq 0, \displaystyle L\)   \(= \lim_{n\to\infty} \left| \frac{a_{n+1}}{a_n} \right|\)   \(> 1\).
   1. Choose \(q\) with \(1 < q < L\). There exists \(N\) such that for all \(n \geq N: \left| \frac{a_{n+1}}{a_n} \right|\)   \(\geq q > 1\)    \(\implies \left| a_{N+k} \right|\) \(\geq \left| a_N \right| \cdot q^k \to \infty\)
   2. So \(\left| a_n\right| \not\to 0\), hence \(\sum a_n\) diverges.

Beispiel: 
\(a_n = (-1)^n\) divergiert, aber \(a_{2n} = 1\) und \(a_{2n+1} = -1\) konvergieren.

Umkehrung: 
Eine Folge konvergiert gegen \(L\) genau dann, wenn jede Teilfolge gegen \(L\) konvergiert.

Das Wurzelkriterium ist stärker: Liefert der Quotient ein Ergebnis, so auch die Wurzel - aber nicht umgekehrt.

In der Praxis ist das Quotientenkriterium oft bequemer, besonders bei \(n!\) oder Potenzen.

Beide versagen bei \(\rho = 1\), z.B. bei \(p\)-Reihen.

In diesem Fall: Verdichtungssatz oder Grenzwertkriterium verwenden.

(Riemannscher Umordnungssatz für bedingt konvergente Reihen)

Merke: Bedingt konvergente Reihen können durch Umordnung jeden Grenzwert annehmen!

Ja, dies nennt man bedingte Konvergenz.

Beispiel: \(\sum \frac{(-1)^n}{n}\) konvergiert (Leibniz), aber \(\sum \frac{1}{n}\) divergiert.

Konsequenz: Bei bedingt konvergenten Reihen darf man nicht umordnen (Riemann'scher Umordnungssatz).

Anwendung:
\(\sum 1/n^s\) für \(s > 1\) konvergiert: \(\sum 2^n \cdot 2^{-ns} = \sum 2^{n(1-s)}\) geometrisch mit \(q = 2^{1-s} < 1\).

• Weil \(a_n\) monoton fällt gilt \(2^n a_{2^n} \ge a_{2^k + 1} + a_{2^k + 2} + \dots + a_{2^{k + 1} - 1}\).
• Wir benutzen das Majorantenkriterium mit\[\begin{align} \sum^n_{k = 0} 2^k a_{2^k} &\ge \sum_{k = 0}^n (a_{2^k + 1} + a_{2^k + 2} + \dots + a_{2^{k + 1} - 1}) \\ &= \sum^{2^n + 1}_{j = 1} a_j \\ &\ge \sum_{k = 0}^n 2^k a_{2^{k+1}} = \frac{1}{2} \sum_{k = 1}^{n + 1} 2^k a_{2^k} \end{align}\]
• Konvergiert \(\sum a_n\) konvergiert auch \((s_n)\) die Folge der Partialsummen und damit auch die Folge der Partialsummen \((s_{2^{n + 1} })\). Damit konvergiert auch die Folge der Partialsummen \((S_{n + 1})\), \(S_{n + 1} = \sum_{k = 1}^{n + 1} 2^k a_{2^k}\).
• Und dann konvergiert auch \(\sum^\infty 2^k a_{2^k}\) nach dem Majorantenkriterium.

Achtung: Bei der Umrechnung von Normal- in Polarform ist der Fall \(x=y=0\) ausgeschlossen.

Direktes Cauchy-Kriterium auf die Partialsummenfolge.

Gilt wirklich nur für konvergente Reihen!

 (verallgemeinerte Dreiecksungleichung)

Ohne die Bedingung, dass \(\sum_{i=0}^m \sum_{j=0}^m |a_{ij}| \leq B\) für alle \(m\), kann die Reihenfolge das Ergebnis ändern. Das ist im Wesentlichen die Forderung, dass die Doppelreihe absolut konvergiert.

Gegenbeispiel:
\[a_{ij} = \begin{cases} 1 & j = i \\ -1 & j = i+1 \\ 0 & \text{sonst} \end{cases}\]

• Zeilensummen: jede Zeile \(= 0\) → Gesamt \(= 0\)
• Spaltensummen: erste Spalte \(= 1\), Rest \(= 0\) → Gesamt \(= 1\)

Beachte: Liefert i.A. nur bedingte Konvergenz, nicht absolute.

1. Die Folge der geraden Partialsummen \(S_{2n}\) ist monoton wachsend und beschränkt, konvergiert also gegen \(L_1\)
2. Die Folge der ungeraden Partialsummen \(S_{2n + 1}\) ist monoton fallend und beschränkt, konvergiert also gegen \(L_2\)
3. Da aber gilt \(S_{2n - 1} - S_{2n} = a_{2n} \rightarrow_\infty = 0 \text{gilt} L_1 - L_2 = 0\) und so konvergieren beide gegen den selben Grenzwert.

(Formel von Hadamard)

Proof (Die Hadamard-Formel ist einfach das Wurzelkriterium umgestellt für |z|)

• Potenzreihe \(\sum c_k z^k = \sum a_k\) für \(a_k = c_k z^k\)
• Wurzelkriterium: \(|a_k|^{1/k} = |(c_k)^{1/k}| \ |z|\) - \(\limsup |(c_k)^{1/k}| \ |z| = |z| \limsup |(c_k)^{1/k}| < 1\)
• \(\implies |z| < \frac{1}{\limsup |c_k|^{1/k}}\) Konvergiert also genau wenn \(|z| < \rho\) also innerhalb des Kreises mit Radius \(\rho\).

Beweis: \(\frac{1}{3}+\frac{1}{4} > \frac{1}{2}\), \(\frac{1}{5}+\cdots+\frac{1}{8} > \frac{1}{2}\), usw. Pakete mit \(> 1/2\) bilden, dann mit \(> 1\) etc...

Spezialfall \(a = 0\):
\(\sum c_k x^k\) - Entwicklungspunkt im Ursprung.

Grenzwertkriterium (Limitenvergleich)

Beispiel:\[\sum \frac{1}{n^2+3n}\]Vergleich mit \(1/n^2\), Grenzwert \(= 1\) → konvergiert.

Nein, es fehlt der Faktor \(a_n\) am Anfang!

Perfect efficiency (\(E = 1,\ S_p = p\)) is rarely achievable. Sub-linear speedup is the normal situation; super-linear is exceptional.

This is a global (class-level) lock, shared across all instances.

A non-static synchronized method locks this (the instance). The two locks are independent — a static and a non-static synchronized method on the same class can execute concurrently.

When the parallel part scales perfectly, i.e. there is no synchronization overhead and no load imbalance, so that \(T_p = f \cdot T_1 + \frac{(1-f) \cdot T_1}{p}\) holds exactly.

 In practice this is never reached - Amdahl gives an idealized upper bound, not a prediction.

If notify() is called before any thread has called wait(). The notification simply is discarded.

Any thread that subsequently calls wait() will block indefinitely. Fix: always protect the condition with a flag variable and check it before waiting.

Because of spurious wakeups. 

A thread can wake from wait() without notify() ever being called (allowed by the JVM for performance reasons).

If the condition is checked only once with if, the thread proceeds even when the condition is still false. A while loop re-checks the condition after every wakeup.

Independent nodes in the DAG can but do not have to execute in parallel. This always depends on the scheduler and available threads.

Forking both sides creates two new tasks and leaves the current thread idle waiting for both.

By calling compute() on one side directly, the current thread does useful work instead of idling - halving the number of tasks created and reducing scheduling overhead.

Always join() the forked task after compute() finishes.