Anki Deck Changes

Intuition:
Fixiere Element \(x\).

• \(x\) dabei → noch \(k-1\) aus \(n-1\) wählen
• \(x\) nicht dabei → alle \(k\) aus \(n-1\) wählen

Pascalsches Dreieck (Eintrag in Zeile \(n\), Position \(k\) ist \(\binom{n}{k}\)):
\[\begin{array}{ccccccccc} & & & & 1 \\ & & & 1 & & 1 \\ & & 1 & & 2 & & 1 \\ & 1 & & 3 & & 3 & & 1 \\ 1 & & 4 & & 6 & & 4 & & 1 \end{array}\]Jeder Eintrag = Summe der zwei Einträge schräg darüber.
Z.B.: \(\binom{4}{2} = 6 = \underbrace{\binom{3}{1}}_{3} + \underbrace{\binom{3}{2}}_{3}\)

Heuristik:
\(v_n\) := Knoten vom kleinsten Grad. Lösche \(v_n\).
\(v_{n-1}\) := Knoten vom kleinsten Grad im Restgraph. Lösche \(v_{n-1}\). Iteriere.

Falls \(G=(V,E)\) erfüllt:
In jedem Subgraphen gibt es einen Knoten mit Grad \(\leq k\)
\(\Rightarrow\) Heuristik liefert Reihenfolge \(v_1,\ldots,v_n\) für die der Greedy-Algorithmus höchstens \(k+1\) Farben benötigt

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

Beweis:
Setze 1. in \(\Pr[A\mid B] = \frac{\Pr[A \cap B]}{\Pr[B]}\) ein, dann kürzt sich \(\Pr[B]\) weg.

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

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

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!

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

(Riemannscher Umordnungssatz)

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

Nützlich zur numerischen Approximation alternierender Reihen.

(D.h. nicht absolut konvergiert..)

Beispiel: 
\(\sum \frac{(-1)^n}{n}\) ist bedingt konvergent.

Weil \(\mathbb{R}\) vollständig ist (keine "Lücken"), während \(\mathbb{Q}\) das nicht ist.

Beispiel:
Die Folge \(1,\; 1.4,\; 1.41,\; 1.414,\; \dots\) ist Cauchy in \(\mathbb{Q}\), konvergiert aber gegen \(\sqrt{2} \notin \mathbb{Q}\).
Der Grenzwert existiert in \(\mathbb{Q}\) nicht - die "Lücke" fehlt.
In \(\mathbb{R}\) ist \(\sqrt{2}\) vorhanden, also konvergiert die Folge dort.

nicht andersherum, na no na ned

Gilt jedoch nicht in die andere Richtung, siehe z.B. die harmonische Reihe \(\sum 1/n\).

Proof:
Da \(\sum_{n=1}^{\infty} b_n\) konvergiert, konvergiert die Folge der Partialsummen. Deswegen ist sie auch beschränkt. Da alle \(a_k \le b_k\), gilt auch \(S_n \le T_n\) (\(S_n\) Partialsummen von \(\sum a_N\), \(T_n\) Partialsummen von \(\sum b_n\)) Dadurch ist auch \(S_n\) beschränkt und da sie monoton steigt (\(a_n \ge 0\)) ist sie auch konvergent. Dadurch ist \(\sum_{n=1}^{\infty} a_n\) konvergent.

(Konvergenzradius \(R = \infty\))

Oft als Referenzreihe im Vergleichssatz nützlich (wenn Wurzel/Quotient versagen).

Faster than synchronized for simple counters.

Implemented via hardware CAS (compare-and-swap).

Part of java.util.concurrent.atomic.

Example:
For a finite run, effective throughput was 0.7 while the infinite-stream bound was 1. As N → ∞, effective throughput approaches 1/max(stage_time).

\(T_1\) is the total work (sum of all node costs in the DAG).
With \(p\) processors, at most \(p\) units of work can be done per time step.
Therefore the minimum time to do \(T_1\) units of work is \(T_1/p\).

This is a counting argument, independent of the scheduler's strategy.

When multiple threads may be waiting and they have different conditions to wait for.

notify() wakes only one (arbitrary) thread - if it wakes a thread whose condition is still false, it goes back to sleep and no progress is made.
notifyAll() wakes all waiters; each re-checks its condition in its while loop.

Cost: more context switches.
Safe default: always use notifyAll() unless you have a single-condition, single-consumer pattern.

The sum of all leaves in its subtree.

Leaves store the original values.
This pass is a parallel tree reduction - done bottom-up with \(O(n)\) work and \(O(\log n)\) span.

Example:
pack([3,1,4,1,5], x > 2) → [3,4,5].
This is the parallel equivalent of a sequential filter loop.