Anki Deck Changes

Note 1: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: LE!#OdHaHH

modified

Before

Front

Die Linearität der Erwartung hält wenn $X_1,\ldots,X_n$ nicht unabhängig, du dummbatzi sind?

Back

Die Linearität der Erwartung hält wenn $X_1,\ldots,X_n$ nicht unabhängig, du dummbatzi sind?

After

Front

Die Linearität der Erwartung hält, wenn $X_1,\ldots,X_n$ vollkommen wurscht ob unabhängig, du dummbatzi sind?

Back

Die Linearität der Erwartung hält, wenn $X_1,\ldots,X_n$ vollkommen wurscht ob unabhängig, du dummbatzi sind?

Field-by-field Comparison

Field	Before	After
Text	Die Linearität der Erwartung hält wenn $X_1,\ldots,X_n$  {{c1::~~nicht~~ unabhängig, du dummbatzi}} sind?	Die Linearität der Erwartung hält, wenn $X_1,\ldots,X_n$ {{c1::vollkommen wurscht ob unabhängig, du dummbatzi}} sind?

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::4._Zufallsvariablen::2._Erwartungswert

Note 2: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: P#e48Dok$?

modified

Before

Front

Paarweise Unabhängigkeit $\not\Rightarrow$ aber $\Leftarrow$ stochastische Unabhängigkeit!

Back

Paarweise Unabhängigkeit $\not\Rightarrow$ aber $\Leftarrow$ stochastische Unabhängigkeit!

After

Front

Paarweise Unabhängigkeit $\Leftarrow$ Stochastische Unabhängigkeit

Back

Paarweise Unabhängigkeit $\Leftarrow$ Stochastische Unabhängigkeit

Field-by-field Comparison

Field	Before	After
Text	Paarweise Unabhängigkeit {{c1::$\~~not\Rightarrow$ aber $\Leftarrow$~~}} stochastische Unabhängigkeit!	Paarweise Unabhängigkeit {{c1::$\Leftarrow$::Implikationen in welche Richtungen?}} Stochastische Unabhängigkeit

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::3._Unabhängigkeit

Note 3: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: PV7-/GzLwe

modified

Before

Front

Rekursion (Pascalsches Dreieck): $\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k} }}$

Back

Rekursion (Pascalsches Dreieck): $\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k} }}$

After

Front

Die Rekursionsformel des Pascalschen Dreiecks lautet: \[\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k} }}\]

Back

Die Rekursionsformel des Pascalschen Dreiecks lautet: \[\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k} }}\]

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

Field-by-field Comparison

Field	Before	After
Text	Rekursion (Pascalsches Dreieck~~): $~~\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k} }}$	Die Rekursionsformel des Pascalschen Dreiecks lautet: \[\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k} }}\]
Extra		<b>Intuition:</b> <br>Fixiere Element $x$.<br><ul><li>$x$ dabei → noch $k-1$ aus $n-1$ wählen</li><li>$x$ nicht dabei → alle $k$ aus $n-1$ wählen</li></ul><b>Pascalsches Dreieck (Eintrag in Zeile </b>$n$<b>, Position </b>$k$<b> ist </b>$\binom{n}{k}$<b>):</b><br>\[\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.<br>Z.B.: $\binom{4}{2} = 6 = \underbrace{\binom{3}{1}}_{3} + \underbrace{\binom{3}{2}}_{3}$

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::0._Kombinatorik

Note 4: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: Pp@EGP+L[^

modified

Before

Front

Hopcroft-Karp findet in einem bipartiten Graphen in {{c1::$O(\sqrt{|V|} \cdot |E|)$}} ein maximales Matching.

Back

Hopcroft-Karp findet in einem bipartiten Graphen in {{c1::$O(\sqrt{|V|} \cdot |E|)$}} ein maximales Matching.

After

Front

Hopcroft-Karp findet in einem bipartiten Graphen in $O({{c2::\sqrt{|V|} \cdot |E|}})$ ein maximales Matching.

Back

Hopcroft-Karp findet in einem bipartiten Graphen in $O({{c2::\sqrt{|V|} \cdot |E|}})$ ein maximales Matching.

Field-by-field Comparison

Field	Before	After
Text	Hopcroft-Karp findet in einem {{c1::<b>bipartiten ~~Graphen</b>}} in~~ {{c1::\~~(O(\~~sqrt{\|V\|} \cdot \|E\|)\)}} ein {{c1::maximales Matching}}.	Hopcroft-Karp findet in einem {{c1::<b>bipartiten</b>}}<b> Graphen</b> in $O({{c2::\sqrt{\|V\|} \cdot \|E\|}})$ ein {{c3::maximales Matching}}.

Tags: ETH::2._Semester::A&W::1._Graphentheorie::6._Matchings::1._Algorithmen

Note 5: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: jc@5=H8@[9

modified

Before

Front

Seien $A, B$ Ereignisse mit $\Pr[B] > 0$.
Dann gilt:
\[\Pr[A\mid B] = {{c1::\frac{\Pr[B\mid A] \cdot \Pr[A]}{\Pr[B]} }}.\]

Back

Seien $A, B$ Ereignisse mit $\Pr[B] > 0$.
Dann gilt:
\[\Pr[A\mid B] = {{c1::\frac{\Pr[B\mid A] \cdot \Pr[A]}{\Pr[B]} }}.\]

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

After

Front

Seien $A, B$ Ereignisse mit $\Pr[B] > 0$.
Dann gilt:
\[\Pr[A\mid B] = {{c1::\frac{\Pr[B\mid A] \cdot \Pr[A]}{\Pr[B]}::\text{Bayes} }}.\]

Back

Seien $A, B$ Ereignisse mit $\Pr[B] > 0$.
Dann gilt:
\[\Pr[A\mid B] = {{c1::\frac{\Pr[B\mid A] \cdot \Pr[A]}{\Pr[B]}::\text{Bayes} }}.\]

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

Field-by-field Comparison

Field	Before	After
Text	Seien $A, B$ Ereignisse mit $\Pr[B] > 0$. <br>Dann gilt:<br>\[\Pr[A\mid B] = {{c1::\frac{\Pr[B\mid A] \cdot \Pr[A]}{\Pr[B]} }}.\]	Seien $A, B$ Ereignisse mit $\Pr[B] > 0$. <br>Dann gilt:<br>\[\Pr[A\mid B] = {{c1::\frac{\Pr[B\mid A] \cdot \Pr[A]}{\Pr[B]}::\text{Bayes} }}.\]

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::2._Bedingte_Wahrscheinlichkeiten

Note 6: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: n.e@Tr+tLx

modified

Before

Front

Falls $\Pr[B] > 0$ ist stochastische Unabhängigkeit $\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]$ ident mit $\Pr[A|B] = \Pr[A]$ (Bayes).

Back

Falls $\Pr[B] > 0$ ist stochastische Unabhängigkeit $\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]$ ident mit $\Pr[A|B] = \Pr[A]$ (Bayes).

After

Front

Stochastische Unabhängigkeit hat zwei äquivalente Formulierungen (falls $\Pr[B] > 0$):

$\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]$
$\Pr[A\mid B] = \Pr[A]$

Back

Stochastische Unabhängigkeit hat zwei äquivalente Formulierungen (falls $\Pr[B] > 0$):

$\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]$
$\Pr[A\mid B] = \Pr[A]$

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.

Field-by-field Comparison

Field	Before	After
Text	~~Falls $\Pr[B] > 0$ ist stochastische Unabhängigkeit ~~$\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]$~~ ident mit {{c1:: ~~$\Pr[A\|B] = \Pr[A]$~~ (Bayes)}}.~~	Stochastische Unabhängigkeit hat zwei äquivalente Formulierungen (falls $\Pr[B] > 0$):<br><ol><li>$\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]$</li><li>{{c1::$\Pr[A\mid B] = \Pr[A]$}}</li></ol>
Extra		<b>Beweis:</b> <br>Setze 1. in $\Pr[A\mid B] = \frac{\Pr[A \cap B]}{\Pr[B]}$ ein, dann kürzt sich $\Pr[B]$ weg.<br><br>Intuition: <br>Das Eintreten von $B$ beeinflusst die Wahrscheinlichkeit von $A$ nicht.

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::3._Unabhängigkeit

Note 7: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: o78LP-Mw-W

modified

Before

Front

Für alle $k \geq 2$ gibt es einen dreiecksfreien Graphen $G_k$ mit $\chi(G_k) \geq k$.

Back

Für alle $k \geq 2$ gibt es einen dreiecksfreien Graphen $G_k$ mit $\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$.

After

Front

Für alle $k \geq 2$ gibt es einen dreiecksfreien Graphen $G_k$ mit $\chi(G_k) \geq k$.

Back

Für alle $k \geq 2$ gibt es einen dreiecksfreien Graphen $G_k$ mit $\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$.

Field-by-field Comparison

Field	Before	After
Text	Für alle $k \geq 2$ gibt es einen {{c1::dreiecksfreien}} Graphen $G_k$ mit $\chi(G_k) \geq ~~{{c2::k}}~~$.	Für alle $k \geq 2$ gibt es einen {{c1::dreiecksfreien}} Graphen $G_k$ mit $\chi(G_k) \geq k$.

Tags: ETH::2._Semester::A&W::1._Graphentheorie::7._Färbungen

Note 8: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: qsXztu}x3_

modified

Before

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

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

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!

After

Front

Ereignisse $A_1, \ldots, A_n$ heissen 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]}}.\]

Back

Ereignisse $A_1, \ldots, A_n$ heissen 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]}}.\]

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 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]}}.\]	Ereignisse $A_1, \ldots, A_n$ heissen stochastisch unabhängig, 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]}}.\]

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::3._Unabhängigkeit

Note 9: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: s7OsezhA)h

modified

Before

Front

Für den Binomialkoeffizienten gelten:
Randfälle: $\binom{n}{0} = 1$, $\binom{n}{n} = 1$, $\binom{n}{1} = n$

Back

Für den Binomialkoeffizienten gelten:
Randfälle: $\binom{n}{0} = 1$, $\binom{n}{n} = 1$, $\binom{n}{1} = n$

After

Front

Für den Binomialkoeffizienten gelten:

$\binom{n}{0} = 1$
$\binom{n}{n} = 1$
$\binom{n}{1} = n$

Back

Für den Binomialkoeffizienten gelten:

$\binom{n}{0} = 1$
$\binom{n}{n} = 1$
$\binom{n}{1} = n$

Field-by-field Comparison

Field	Before	After
Text	Für den Binomialkoeffizienten gelten:<br>~~Randfälle:~~ $\binom{n}{0} = {{c2::1}}$, $\binom{n}{n} = {{c2::1}}$, $\binom{n}{1} = {{c2::n}}$	Für den Binomialkoeffizienten gelten:<br><ol><li>$\binom{n}{0} = {{c1::1}}$</li><li>$\binom{n}{n} = {{c2::1}}$</li><li>$\binom{n}{1} = {{c3::n}}$</li></ol>

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::0._Kombinatorik

Note 10: ETH::2. Semester::A&W

Deck: ETH::2. Semester::A&W
Note Type: Horvath Cloze
GUID: tHY-Qji=0u

modified

Before

Front

Zwei Ereignisse $A$ und $B$ heißen stochastisch unabhängig, falls
\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B] \]

Back

Zwei Ereignisse $A$ und $B$ heißen stochastisch unabhängig, falls
\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B] \]

Intuition:
Das Eintreten von $B$ beeinflusst die Wahrscheinlichkeit von $A$ nicht.

After

Front

Zwei Ereignisse $A$ und $B$ heißen stochastisch unabhängig, falls:
\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B] \]

Back

Zwei Ereignisse $A$ und $B$ heißen stochastisch unabhängig, falls:
\[\Pr[A \cap B] = \Pr[A] \cdot \Pr[B] \]

Intuition:
Das Eintreten von $B$ beeinflusst die Wahrscheinlichkeit von $A$ nicht.

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]}} \]	Zwei Ereignisse $A$ und $B$ heißen {{c1::stochastisch unabhängig}}, falls:<br>\[{{c2::\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]}} \]

Tags: ETH::2._Semester::A&W::2._Wahrscheinlichkeitstheorie_und_randomisierte_Algorithmen::3._Unabhängigkeit

Note 11: ETH::2. Semester::Analysis

Deck: ETH::2. Semester::Analysis
Note Type: Horvath Cloze
GUID: =wRp[:z20n

modified

Before

Front

Riemannscher Umordnungssatz (bedingt konvergente Reihen): Sei $\sum a_n$ {{c1::bedingt konvergent und $L \in \mathbb{R} \cup \{+\infty, -\infty\}$}}.

Dann {{c2::gibt es eine Bijektion $\phi$, so dass:
\[\sum_{n=0}^\infty a_{\phi(n)} = L\]}}

Back

Riemannscher Umordnungssatz (bedingt konvergente Reihen): Sei $\sum a_n$ {{c1::bedingt konvergent und $L \in \mathbb{R} \cup \{+\infty, -\infty\}$}}.

Dann {{c2::gibt es eine Bijektion $\phi$, so dass:
\[\sum_{n=0}^\infty a_{\phi(n)} = L\]}}

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

After

Front

Sei $\sum a_n$ {{c1::bedingt konvergent und $L \in \mathbb{R} \cup \{+\infty, -\infty\}$}}.

Dann {{c2::gibt es eine Bijektion $\phi$, so dass:
\[\sum_{n=0}^\infty a_{\phi(n)} = L\]}}

Back

Sei $\sum a_n$ {{c1::bedingt konvergent und $L \in \mathbb{R} \cup \{+\infty, -\infty\}$}}.

Dann {{c2::gibt es eine Bijektion $\phi$, so dass:
\[\sum_{n=0}^\infty a_{\phi(n)} = L\]}}

(Riemannscher Umordnungssatz)

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

Field-by-field Comparison

Field	Before	After
Text	~~<b>Riemannscher</b> Umordnungssatz (bedingt konvergente Reihen):~~ Sei $\sum a_n$ {{c1::<b>bedingt konvergent</b> und $L \in \mathbb{R} \cup \{+\infty, -\infty\}$}}.<br><br>Dann {{c2::gibt es eine Bijektion $\phi$, so dass:<br>\[\sum_{n=0}^\infty a_{\phi(n)} = L\]}}	Sei $\sum a_n$ {{c1::<b>bedingt konvergent</b> und $L \in \mathbb{R} \cup \{+\infty, -\infty\}$}}.<br><br>Dann {{c2::gibt es eine Bijektion $\phi$, so dass:<br>\[\sum_{n=0}^\infty a_{\phi(n)} = L\]}}
Extra	<b>Merke:</b> Bedingt konvergente Reihen können durch Umordnung <i>jeden</i> Grenzwert annehmen!	(Riemannscher Umordnungssatz)<b><br><br>Merke:</b> Bedingt konvergente Reihen können durch Umordnung <i>jeden</i> Grenzwert annehmen!

Tags: ETH::2._Semester::Analysis::3._Reihen::4._Umordnung

Note 12: ETH::2. Semester::Analysis

Deck: ETH::2. Semester::Analysis
Note Type: Horvath Cloze
GUID: @#Owv2&S1x

modified

Before

Front

Beim Leibniz-Kriterium gilt die Fehlerabschätzung:
\[|S - S_n| \leq {{c1::a_{n+1} }}\]
D.h. der Fehler ist höchstens so groß wie der erste weggelassene Term.

Back

Beim Leibniz-Kriterium gilt die Fehlerabschätzung:
\[|S - S_n| \leq {{c1::a_{n+1} }}\]
D.h. der Fehler ist höchstens so groß wie der erste weggelassene Term.

Nützlich zur numerischen Approximation alternierender Reihen.

After

Front

Beim Leibniz-Kriterium gilt die Fehlerabschätzung:
\[|S - S_n| \leq {{c1::a_{n+1} }}\]D.h. der Fehler ist höchstens so gross wie der erste weggelassene Term.

Back

Beim Leibniz-Kriterium gilt die Fehlerabschätzung:
\[|S - S_n| \leq {{c1::a_{n+1} }}\]D.h. der Fehler ist höchstens so gross wie der erste weggelassene Term.

Nützlich zur numerischen Approximation alternierender Reihen.

Field-by-field Comparison

Field	Before	After
Text	Beim Leibniz-Kriterium gilt die Fehlerabschätzung:<br>\[\|S - S_n\| \leq {{c1::a_{n+1} }}\]~~<br>~~D.h. der Fehler ist höchstens so groß wie {{c1::der erste weggelassene Term}}.	Beim Leibniz-Kriterium gilt die Fehlerabschätzung:<br>\[\|S - S_n\| \leq {{c1::a_{n+1} }}\]D.h. der Fehler ist höchstens so gross wie {{c1::der erste weggelassene Term}}.

Tags: ETH::2._Semester::Analysis::3._Reihen::3._Konvergenzkriterien

Note 13: ETH::2. Semester::Analysis

Deck: ETH::2. Semester::Analysis
Note Type: Horvath Classic
GUID: jKp`Sev.N*

modified

Before

Front

Warum gilt Cauchy $\iff$ konvergent in $\mathbb{R}$, aber nicht in $\mathbb{Q}$?

Back

Warum gilt Cauchy $\iff$ konvergent in $\mathbb{R}$, aber nicht in $\mathbb{Q}$?

In $\mathbb{R}$: jede Cauchy-Folge konvergiert in $\mathbb{R}$ (Vollständigkeit).

In $\mathbb{Q}$: Eine Cauchy-Folge in $\mathbb{Q}$ kann gegen $\sqrt{2} \notin \mathbb{Q}$ konvergieren — der Grenzwert liegt außerhalb des Raumes. $\mathbb{Q}$ ist nicht vollständig.

After

Front

Warum ist jede Cauchy-Folge in $\mathbb{R}$ konvergent, aber nicht jede in $\mathbb{Q}$?

Back

Warum ist jede Cauchy-Folge in $\mathbb{R}$ konvergent, aber nicht jede in $\mathbb{Q}$?

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.

Field-by-field Comparison

Field	Before	After
Front	Warum ~~gilt Cauchy $\iff$ konvergent in $\mathbb{R}$, aber nicht in~~ $\mathbb{Q}$?	Warum ist jede Cauchy-Folge in $\mathbb{R}$ konvergent, aber nicht jede in $\mathbb{Q}$?
Back	In $\mathbb{R}$~~: jede Cauchy-Folge konvergiert <b>in</b>~~ $\mathbb{R}$ ~~(Vollständigkeit).<br><br>In $\mathbb{Q}$: Eine Cauchy-Folge in~~ $\mathbb{Q}$ k~~ann gegen~~ $\sqrt{2} \notin \mathbb{Q}$ ~~konvergieren — d~~er Grenzwert liegt ~~außerhalb des Raumes.~~ $\mathbb{Q}$ ~~ist <b>nicht vollständig</b>~~.	Weil $\mathbb{R}$ vollständig ist (keine "Lücken"), während $\mathbb{Q}$ das nicht ist.<br><br><b>Beispiel:</b><br>Die Folge $1,\; 1.4,\; 1.41,\; 1.414,\; \dots$ ist Cauchy in $\mathbb{Q}$, konvergiert aber gegen $\sqrt{2} \notin \mathbb{Q}$.<br>Der Grenzwert existiert in $\mathbb{Q}$ nicht - die "Lücke" fehlt.<br>In $\mathbb{R}$ ist $\sqrt{2}$ vorhanden, also konvergiert die Folge dort.

Tags: ETH::2._Semester::Analysis::2._Folgen::2._Konvergenz::4._Cauchy_Folge

Note 14: ETH::2. Semester::Analysis

Deck: ETH::2. Semester::Analysis
Note Type: Horvath Cloze
GUID: tRig1dAtan06

modified

Before

Front

The range of $\arctan$ is ${{c1::\left(-\frac{\pi}{2},\, \frac{\pi}{2}\right)}}$, and it is a strictly increasing function.

Back

The range of $\arctan$ is ${{c1::\left(-\frac{\pi}{2},\, \frac{\pi}{2}\right)}}$, and it is a strictly increasing function.

After

Front

Der Wertebereich von $\arctan$ ist ${{c1::\left(-\frac{\pi}{2},\, \frac{\pi}{2}\right)}}$, und die Funktion ist streng monoton steigend.

Back

Der Wertebereich von $\arctan$ ist ${{c1::\left(-\frac{\pi}{2},\, \frac{\pi}{2}\right)}}$, und die Funktion ist streng monoton steigend.

Field-by-field Comparison

Field	Before	After
Text	~~The range of $\arctan$ is~~ ${{c1::\left(-\frac{\pi}{2},\, \frac{\pi}{2}\right)}}$, and it is a {{c1::str~~ictly increasing}} function~~.	Der Wertebereich von $\arctan$ ist ${{c1::\left(-\frac{\pi}{2},\, \frac{\pi}{2}\right)}}$, und die Funktion ist {{c1::streng monoton steigend::Wachstumsverhalten}}.

Tags: ETH::2._Semester::Analysis::0._Trigonometrie::2._Identitäten::1._Arcostangens

Note 15: ETH::2. Semester::Analysis

Deck: ETH::2. Semester::Analysis
Note Type: Horvath Cloze
GUID: u$3f,(&]?[

modified

Before

Front

Absolut konvergent $\implies$ konvergent

Back

Absolut konvergent $\implies$ konvergent

nicht andersherum

After

Front

Absolut konvergent $\implies$konvergent

Back

Absolut konvergent $\implies$konvergent

nicht andersherum, na no na ned

Field-by-field Comparison

Field	Before	After
Text	Absolut konvergent  $\implies$~~ ~~{{c2::konvergent}}	Absolut konvergent $\implies${{c1::konvergent}}
Extra	nicht andersherum	nicht andersherum, na no na ned

Tags: ETH::2._Semester::Analysis::3._Reihen::1._Definitionen

Note 16: ETH::2. Semester::Analysis

Deck: ETH::2. Semester::Analysis
Note Type: Horvath Cloze
GUID: w)NK`}V9nz

modified

Before

Front

Falls $\sum a_n$ konvergiert, dann gilt zwingend: $\lim_{n\to\infty} a_n = 0$.

Back

Falls $\sum a_n$ konvergiert, dann gilt zwingend: $\lim_{n\to\infty} a_n = 0$.

Gegenbeispiel: harmonische Reihe $\sum 1/n$

After

Front

Falls $\sum a_n$ konvergiert, dann gilt zwingend, dass $\lim_{n\to\infty} a_n = 0$.

Back

Falls $\sum a_n$ konvergiert, dann gilt zwingend, dass $\lim_{n\to\infty} a_n = 0$.

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

Field-by-field Comparison

Field	Before	After
Text	Falls $\sum a_n$ konvergiert, dann gilt zwingend: $\lim_{n\to\infty} a_n = {{c1::0}}$.	Falls $\sum a_n$ konvergiert, dann gilt zwingend, dass $\lim_{n\to\infty} a_n = {{c1::0}}$.
Extra	G~~egenbeispiel:~~ harmonische Reihe $\sum 1/n$	Gilt jedoch nicht in die andere Richtung, siehe z.B. die harmonische Reihe $\sum 1/n$.

Tags: ETH::2._Semester::Analysis::3._Reihen::3._Konvergenzkriterien

Note 17: ETH::2. Semester::Analysis

Deck: ETH::2. Semester::Analysis
Note Type: Horvath Cloze
GUID: z>(#?Mm:.A

modified

Before

Front

Wenn $\sum^\infty a_n$ konvergent ist gilt:
\[ \sum_{n = 0}^\infty a_n = {{c1::\sum_{n = 0}^{N - 1} + \sum_{n = N}^\infty a_n:: \text{split sum} }}\]

Back

Wenn $\sum^\infty a_n$ konvergent ist gilt:
\[ \sum_{n = 0}^\infty a_n = {{c1::\sum_{n = 0}^{N - 1} + \sum_{n = N}^\infty a_n:: \text{split sum} }}\]

After

Front

Wenn $\sum^\infty a_n$ konvergent ist, gilt:
\[ \sum_{n = 0}^\infty a_n = {{c1::\sum_{n = 0}^{N - 1} a_n + \sum_{n = N}^\infty a_n:: \text{split sum} }}\]

Back

Wenn $\sum^\infty a_n$ konvergent ist, gilt:
\[ \sum_{n = 0}^\infty a_n = {{c1::\sum_{n = 0}^{N - 1} a_n + \sum_{n = N}^\infty a_n:: \text{split sum} }}\]

Field-by-field Comparison

Field	Before	After
Text	Wenn $\sum^\infty a_n$ konvergent ist gilt:<br>\[ \sum_{n = 0}^\infty a_n = {{c1::\sum_{n = 0}^{N - 1} + \sum_{n = N}^\infty a_n:: \text{split sum} }}\]	Wenn $\sum^\infty a_n$ konvergent ist, gilt:<br>\[ \sum_{n = 0}^\infty a_n = {{c1::\sum_{n = 0}^{N - 1} a_n + \sum_{n = N}^\infty a_n:: \text{split sum} }}\]

Tags: ETH::2._Semester::Analysis::3._Reihen::1._Definitionen

Note 18: ETH::2. Semester::Analysis

Deck: ETH::2. Semester::Analysis
Note Type: Horvath Cloze
GUID: {XU$eYR/n`

modified

Before

Front

Sei $0 \leq a_n \leq b_n$ für alle $n \geq N$:

$\sum b_n$ konvergiert $\implies \sum a_n \text{ konvergiert}$ (Majorante)
$\sum a_n$ divergiert $\implies \sum b_n \text{ divergiert}$ (Minorante)

Back

Sei $0 \leq a_n \leq b_n$ für alle $n \geq N$:

$\sum b_n$ konvergiert $\implies \sum a_n \text{ konvergiert}$ (Majorante)
$\sum a_n$ divergiert $\implies \sum b_n \text{ divergiert}$ (Minorante)

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.

After

Front

Sei $0 \leq a_n \leq b_n$ für alle $n \geq N$:

$\sum b_n$ konvergiert $\implies \sum a_n$ konvergiert (Majorante)
$\sum a_n$ divergiert $\implies \sum b_n$ divergiert (Minorante)

Back

Sei $0 \leq a_n \leq b_n$ für alle $n \geq N$:

$\sum b_n$ konvergiert $\implies \sum a_n$ konvergiert (Majorante)
$\sum a_n$ divergiert $\implies \sum b_n$ divergiert (Minorante)

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.

Field-by-field Comparison

Field	Before	After
Text	Sei $0 \leq a_n \leq b_n$ für alle $n \geq N$:<br><br>$\sum b_n$ konvergiert $\implies ~~{{c1::~~\sum a_n ~~\text{ konvergiert}}}$   (<b>~~Majorante~~</b>)~~<br>$\sum a_n$ divergiert $\implies ~~{{c2::~~\sum b_n ~~\text{ divergiert}}}$   (<b>~~Minorante~~</b>)~~	Sei $0 \leq a_n \leq b_n$ für alle $n \geq N$:<br><br>$\sum b_n$ konvergiert $\implies \sum a_n$ {{c1:: konvergiert (Majorante)}}<br>$\sum a_n$ divergiert $\implies \sum b_n$ {{c1::divergiert (Minorante)}}

Tags: ETH::2._Semester::Analysis::3._Reihen::3._Konvergenzkriterien

Note 19: ETH::2. Semester::Analysis

Deck: ETH::2. Semester::Analysis
Note Type: Horvath Cloze
GUID: {].oPsIfG|

modified

Before

Front

Exponentialreihe:\[\exp(z) = {{c1:: \sum_{n=0}^\infty \frac{z^n}{n!} }}\]
Diese Reihe konvergiert {{c1::absolut für alle $z \in \mathbb{C}$}} (Konvergenzradius $R = \infty$).

Back

Exponentialreihe:\[\exp(z) = {{c1:: \sum_{n=0}^\infty \frac{z^n}{n!} }}\]
Diese Reihe konvergiert {{c1::absolut für alle $z \in \mathbb{C}$}} (Konvergenzradius $R = \infty$).

After

Front

Exponentialreihe:\[\exp(z) = {{c1:: \sum_{n=0}^\infty \frac{z^n}{n!} }}\]Diese Reihe konvergiert {{c2::absolut für alle $z \in \mathbb{C}$::Konvergenztyp}}.

Back

Exponentialreihe:\[\exp(z) = {{c1:: \sum_{n=0}^\infty \frac{z^n}{n!} }}\]Diese Reihe konvergiert {{c2::absolut für alle $z \in \mathbb{C}$::Konvergenztyp}}.

(Konvergenzradius $R = \infty$)

Field-by-field Comparison

Field	Before	After
Text	Exponentialreihe:\[\exp(z) = {{c1:: \sum_{n=0}^\infty \frac{z^n}{n!} }}\]~~<br>~~Diese Reihe konvergiert {{c1::absolut für alle $z \in \mathbb{C}$~~}} (~~Konvergenz~~radius $R = \infty$)~~.	Exponentialreihe:\[\exp(z) = {{c1:: \sum_{n=0}^\infty \frac{z^n}{n!} }}\]Diese Reihe konvergiert {{c2::absolut für alle $z \in \mathbb{C}$::Konvergenztyp}}.
Extra		(Konvergenzradius $R = \infty$)

Tags: ETH::2._Semester::Analysis::3._Reihen::2._Standard_Reihen

Note 20: ETH::2. Semester::Analysis

Deck: ETH::2. Semester::Analysis
Note Type: Horvath Cloze
GUID: }3LSktDYts

modified

Before

Front

Die Riemansche-Zeta Funktion Reihe $\displaystyle\zeta(s) = {{c1:: \sum_{n=1}^\infty \frac{1}{n^s} }}$ konvergiert für s > 1 und divergiert für s $\leq 1$.

Back

Die Riemansche-Zeta Funktion Reihe $\displaystyle\zeta(s) = {{c1:: \sum_{n=1}^\infty \frac{1}{n^s} }}$ konvergiert für s > 1 und divergiert für s $\leq 1$.

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

After

Front

Die Riemansche-Zeta Funktion Reihe $\displaystyle\zeta(s) = {{c1:: \sum_{n=1}^\infty \frac{1}{n^s} }}$ konvergiert für s > 1 und divergiert für s $\leq 1$.

Back

Die Riemansche-Zeta Funktion Reihe $\displaystyle\zeta(s) = {{c1:: \sum_{n=1}^\infty \frac{1}{n^s} }}$ konvergiert für s > 1 und divergiert für s $\leq 1$.

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

Field-by-field Comparison

Field	Before	After
Text	Die Riemansche-Zeta Funktion Reihe $\displaystyle\zeta(s) = {{c1:: \sum_{n=1}^\infty \frac{1}{n^s} }}$ konvergiert für {{c1::s > 1}} und divergiert für {{c1::s $\leq 1$}}.	Die Riemansche-Zeta Funktion Reihe $\displaystyle\zeta(s) = {{c1:: \sum_{n=1}^\infty \frac{1}{n^s} }}$ konvergiert für {{c2::s > 1}} und divergiert für {{c2::s $\leq 1$}}.

Tags: ETH::2._Semester::Analysis::3._Reihen::2._Standard_Reihen

Note 21: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: EdVyAbz-qv

modified

Before

Front

AtomicInteger provides atomic compound operations such as getAndIncrement() and compareAndSet(expected, update) without requiring synchronized.

Back

AtomicInteger provides atomic compound operations such as getAndIncrement() and compareAndSet(expected, update) without requiring synchronized.

Implemented via hardware CAS (compare-and-swap). Faster than synchronized for simple counters. Part of java.util.concurrent.atomic.

After

Front

AtomicInteger provides atomic compound operations such as getAndIncrement() and compareAndSet(expected, update) without requiring synchronized.

Back

AtomicInteger provides atomic compound operations such as getAndIncrement() and compareAndSet(expected, update) without requiring synchronized.

Faster than synchronized for simple counters.

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

Part of java.util.concurrent.atomic.

Field-by-field Comparison

Field	Before	After
Text	<code>{{c1::AtomicInteger}}</code> provides {{c2::atomic compound operations}} such as <code>~~{{c2::~~getAndIncrement()}}</code> and <code>~~{{c2::~~compareAndSet(expected, update)}}</code> without requiring <code>synchronized</code>.	<code>{{c1::AtomicInteger}}</code> provides {{c2::atomic compound operations}} such as <code>getAndIncrement()</code> and <code>compareAndSet(expected, update)</code> without requiring <code>synchronized</code>.
Extra	~~Implemented via hardware CAS (compare-and-swap).~~ Faster than <code>synchronized</code> for simple counters. Part of <code>java.util.concurrent.atomic</code>.	Faster than <code>synchronized</code> for simple counters.<br><br>Implemented via hardware CAS (compare-and-swap).<br><br>Part of <code>java.util.concurrent.atomic</code>.

Tags: ETH::2._Semester::PProg::12._Shared_Memory_Concurrency

Note 22: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: GH&YPQRsTh

modified

Before

Front

Lead-in and lead-out reduce effective throughput below the theoretical bound for a finite number of elements N. Their impact is largest when N is small (short pipelines).

Back

Lead-in and lead-out reduce effective throughput below the theoretical bound for a finite number of elements N. Their impact is largest when N is small (short pipelines).

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

After

Front

Lead-in and lead-out reduce effective throughput below the theoretical bound for a finite number of elements N.

Their impact is largest when N is small (short pipelines).

Back

Lead-in and lead-out reduce effective throughput below the theoretical bound for a finite number of elements N.

Their impact is largest when N is small (short pipelines).

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

Field-by-field Comparison

Field	Before	After
Text	Lead-in and lead-out ~~{{c1::~~reduce effective throughput below the theoretical bound}} for {{c2::a finite number of elements N}}. Their impact is largest when {{c3::N is small (short pipelines)}}.	Lead-in and lead-out reduce {{c1::effective throughput below the theoretical bound}} for {{c2::a finite number of elements N}}. <br><br>Their impact is largest when {{c3::N is small (short pipelines)}}.
Extra	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).	<b>Example:</b> <br>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).

Tags: ETH::2._Semester::PProg::06._Parallel_Architecture::3._Pipelining

Note 23: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Classic
GUID: KD1&||&6xW

modified

Before

Front

Why is $T_p \geq T_1/p$ a strict lower bound — why can no scheduler beat it?

Back

Why is $T_p \geq T_1/p$ a strict lower bound — why can no scheduler beat it?

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

After

Front

Why is $T_p \geq T_1/p$ a strict lower bound - why can no scheduler beat it?

Back

Why is $T_p \geq T_1/p$ a strict lower bound - why can no scheduler beat it?

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

Field-by-field Comparison

Field	Before	After
Front	Why is $T_p \geq T_1/p$ a strict lower bound — why can no scheduler beat it?	Why is $T_p \geq T_1/p$ a strict lower bound - why can no scheduler beat it?
Back	$T_1$ is the total work (sum of all node costs in the DAG). <br>With p processors, at most p units of work can be done per time step. <br>herefore the minimum time to do $T_1$ units of work is $T_1/p$.<br><br>This is a counting argument, independent of the scheduler's strategy.	$T_1$ is the total work (sum of all node costs in the DAG). <br>With p processors, at most p units of work can be done per time step. <br>Therefore the minimum time to do $T_1$ units of work is $T_1/p$.<br><br>This is a counting argument, independent of the scheduler's strategy.

Tags: ETH::2._Semester::PProg::10._Parallel_Algorithms::1._Task_graphs_and_performance_measures

Note 24: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Classic
GUID: KqO7gK}Fu/

modified

Before

Front

When should you prefer notifyAll() over notify()?

Back

When should you prefer notifyAll() over notify()?

Prefer notifyAll() 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.

After

Front

When should you prefer notifyAll() over notify()?

Back

When should you prefer notifyAll() over notify()?

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.

Field-by-field Comparison

Field	Before	After
Front	When should you prefer <code>notifyAll()</code> over <code>notify()</code>?	When should you prefer <code>notifyAll()</code> over <code>notify()</code>?
Back	~~Prefer <code>notifyAll()</code> w~~hen <b>multiple threads</b> may be waiting and they have <b>different conditions</b> to wait for. <code>notify()</code> 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. <code>notifyAll()</code> wakes all waiters; each re-checks its condition in its <code>while</code> loop. Cost: more context switches. Safe default: always use <code>notifyAll()</code> unless you have a single-condition, single-consumer pattern.	When <b>multiple threads</b> may be waiting and they have <b>different conditions</b> to wait for. <br><code><br>notify()</code> 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.<code><br>notifyAll()</code> wakes all waiters; each re-checks its condition in its <code>while</code> loop. <br><br>Cost: more context switches. <br>Safe default: always use <code>notifyAll()</code> unless you have a single-condition, single-consumer pattern.

Tags: ETH::2._Semester::PProg::05._Java_Threads::3._Wait,_Notify,_NotifyAll

Note 25: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Classic
GUID: Lj=X5W/02X

modified

Before

Front

What does each node store after the up pass (reduce pass) of the parallel prefix-sum algorithm?

Back

What does each node store after the up pass (reduce pass) of the parallel prefix-sum algorithm?

Each internal node stores 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.

After

Front

What does each node store after the up pass (reduce pass) of the parallel prefix-sum algorithm?

Back

What does each node store after the up pass (reduce pass) of the parallel prefix-sum algorithm?

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.

Field-by-field Comparison

Field	Before	After
Back	~~Each internal node stores the <b>~~sum of all leaves in its subtree~~</b>.~~ Leaves store the original values. This pass is a parallel tree reduction — done bottom-up with ~~O(n) work and~~ O(log n) span.	The sum of all leaves in its subtree. <br><br>Leaves store the original values.<br>This pass is a parallel tree reduction - done bottom-up with $O(n)$ work and $O(\log n)$ span.

Tags: ETH::2._Semester::PProg::10._Parallel_Algorithms::3._Parallel_algorithms

Note 26: ETH::2. Semester::PProg

Deck: ETH::2. Semester::PProg
Note Type: Horvath Cloze
GUID: NLVo5v1@Dy

modified

Before

Front

Pack (also called filter) takes a collection and a predicate and returns a new array containing only the elements satisfying the predicate, preserving their original relative order.

Back

Pack (also called filter) takes a collection and a predicate and returns a new array containing only the elements satisfying the predicate, preserving their original relative order.

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

After

Front

Pack (also called filter) takes a collection and a predicate and returns a new array containing only the elements satisfying the predicate, preserving their original relative order.

Back

Pack (also called filter) takes a collection and a predicate and returns a new array containing only the elements satisfying the predicate, preserving their original relative order.

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

Field-by-field Comparison

Field	Before	After
Text	{{c1::Pack}} (also called filter) takes a collection and a predicate and returns {{c2::a new array containing only the elements satisfying the predicate, preserving their original relative order}}.	{{c1::Pack (also called filter)}} takes a collection and a predicate and returns {{c2::a new array containing only the elements satisfying the predicate, preserving their original relative order}}.
Extra	Example: pack([3,1,4,1,5], x > 2) → [3,4,5]. This is the parallel equivalent of a sequential filter loop.	<b>Example:</b> <br>pack([3,1,4,1,5], x > 2) → [3,4,5]. <br>This is the parallel equivalent of a sequential filter loop.

Tags: ETH::2._Semester::PProg::10._Parallel_Algorithms::3._Parallel_algorithms

Field	Before	After
Text	Rekursion (Pascalsches Dreieck~~): \(~~\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k} }}\)	Die Rekursionsformel des Pascalschen Dreiecks lautet: \[\binom{n}{k} = {{c3::\binom{n-1}{k-1} + \binom{n-1}{k} }}\]
Extra		<b>Intuition:</b> <br>Fixiere Element \(x\).<br><ul><li>\(x\) dabei → noch \(k-1\) aus \(n-1\) wählen</li><li>\(x\) nicht dabei → alle \(k\) aus \(n-1\) wählen</li></ul><b>Pascalsches Dreieck (Eintrag in Zeile </b>\(n\)<b>, Position </b>\(k\)<b> ist </b>\(\binom{n}{k}\)<b>):</b><br>\[\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.<br>Z.B.: \(\binom{4}{2} = 6 = \underbrace{\binom{3}{1}}_{3} + \underbrace{\binom{3}{2}}_{3}\)

Field	Before	After
Text	~~Falls \(\Pr[B] > 0\) ist stochastische Unabhängigkeit ~~\(\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]\)~~ ident mit {{c1:: ~~\(\Pr[A\|B] = \Pr[A]\)~~ (Bayes)}}.~~	Stochastische Unabhängigkeit hat zwei äquivalente Formulierungen (falls \(\Pr[B] > 0\)):<br><ol><li>\(\Pr[A \cap B] = \Pr[A] \cdot \Pr[B]\)</li><li>{{c1::\(\Pr[A\mid B] = \Pr[A]\)}}</li></ol>
Extra		<b>Beweis:</b> <br>Setze 1. in \(\Pr[A\mid B] = \frac{\Pr[A \cap B]}{\Pr[B]}\) ein, dann kürzt sich \(\Pr[B]\) weg.<br><br>Intuition: <br>Das Eintreten von \(B\) beeinflusst die Wahrscheinlichkeit von \(A\) nicht.

Field	Before	After
Text	~~<b>Riemannscher</b> Umordnungssatz (bedingt konvergente Reihen):~~ Sei \(\sum a_n\) {{c1::<b>bedingt konvergent</b> und \(L \in \mathbb{R} \cup \{+\infty, -\infty\}\)}}.<br><br>Dann {{c2::gibt es eine Bijektion \(\phi\), so dass:<br>\[\sum_{n=0}^\infty a_{\phi(n)} = L\]}}	Sei \(\sum a_n\) {{c1::<b>bedingt konvergent</b> und \(L \in \mathbb{R} \cup \{+\infty, -\infty\}\)}}.<br><br>Dann {{c2::gibt es eine Bijektion \(\phi\), so dass:<br>\[\sum_{n=0}^\infty a_{\phi(n)} = L\]}}
Extra	<b>Merke:</b> Bedingt konvergente Reihen können durch Umordnung <i>jeden</i> Grenzwert annehmen!	(Riemannscher Umordnungssatz)<b><br><br>Merke:</b> Bedingt konvergente Reihen können durch Umordnung <i>jeden</i> Grenzwert annehmen!

Field	Before	After
Front	Warum ~~gilt Cauchy \(\iff\) konvergent in \(\mathbb{R}\), aber nicht in~~ \(\mathbb{Q}\)?	Warum ist jede Cauchy-Folge in \(\mathbb{R}\) konvergent, aber nicht jede in \(\mathbb{Q}\)?
Back	In \(\mathbb{R}\)~~: jede Cauchy-Folge konvergiert <b>in</b>~~ \(\mathbb{R}\) ~~(Vollständigkeit).<br><br>In \(\mathbb{Q}\): Eine Cauchy-Folge in~~ \(\mathbb{Q}\) k~~ann gegen~~ \(\sqrt{2} \notin \mathbb{Q}\) ~~konvergieren — d~~er Grenzwert liegt ~~außerhalb des Raumes.~~ \(\mathbb{Q}\) ~~ist <b>nicht vollständig</b>~~.	Weil \(\mathbb{R}\) vollständig ist (keine "Lücken"), während \(\mathbb{Q}\) das nicht ist.<br><br><b>Beispiel:</b><br>Die Folge \(1,\; 1.4,\; 1.41,\; 1.414,\; \dots\) ist Cauchy in \(\mathbb{Q}\), konvergiert aber gegen \(\sqrt{2} \notin \mathbb{Q}\).<br>Der Grenzwert existiert in \(\mathbb{Q}\) nicht - die "Lücke" fehlt.<br>In \(\mathbb{R}\) ist \(\sqrt{2}\) vorhanden, also konvergiert die Folge dort.

Field	Before	After
Text	Absolut konvergent  \(\implies\)~~ ~~{{c2::konvergent}}	Absolut konvergent \(\implies\){{c1::konvergent}}
Extra	nicht andersherum	nicht andersherum, na no na ned

Field	Before	After
Text	Falls \(\sum a_n\) konvergiert, dann gilt zwingend: \(\lim_{n\to\infty} a_n = {{c1::0}}\).	Falls \(\sum a_n\) konvergiert, dann gilt zwingend, dass \(\lim_{n\to\infty} a_n = {{c1::0}}\).
Extra	G~~egenbeispiel:~~ harmonische Reihe \(\sum 1/n\)	Gilt jedoch nicht in die andere Richtung, siehe z.B. die harmonische Reihe \(\sum 1/n\).

Field	Before	After
Front	Why is \(T_p \geq T_1/p\) a strict lower bound — why can no scheduler beat it?	Why is \(T_p \geq T_1/p\) a strict lower bound - why can no scheduler beat it?
Back	\(T_1\) is the total work (sum of all node costs in the DAG). <br>With p processors, at most p units of work can be done per time step. <br>herefore the minimum time to do \(T_1\) units of work is \(T_1/p\).<br><br>This is a counting argument, independent of the scheduler's strategy.	\(T_1\) is the total work (sum of all node costs in the DAG). <br>With p processors, at most p units of work can be done per time step. <br>Therefore the minimum time to do \(T_1\) units of work is \(T_1/p\).<br><br>This is a counting argument, independent of the scheduler's strategy.