Anki Deck Changes

Wahr oder falsch?

Es existiert ein Graph mit 51 Knoten, in dem jeder Knoten Grad 17 hat.

An einem inneren Knoten gibt es vier lokale Veränderungen des Flusses, die die Flusserhaltung erhalten. Zu beachten sind dabei:

• bei \(\mathbf{+\delta}\): die Kapazität der Kante
• bei \(\mathbf{-\delta}\): der aktuelle Fluss auf der Kante

Der Wert eines Flusses \(f\) ist definiert als der Nettoabfluss der Quelle:\[\operatorname{val}(f) := {{c1::\operatorname{netoutflow}(s) := \sum_{u \in V : (s,u) \in A} f(s, u) \;-\; \sum_{u \in V : (u,s) \in A} f(u, s). }}\]

MaxFlow-Problem
Gegeben ein Netzwerk \(N = (V, A, c, s, t)\), finde einen Fluss \(f\) grössten Werts (einen maximalen Fluss).

Da es nur endlich viele s-t-Schnitte gibt, folgt:

• s-t-MinCut ist ein endliches algorithmisches Problem,
• ein minimaler Schnitt existiert immer.

Zufallsfärbungen
Sei \(G\) ein Graph mit einem Pfad \(P\) der Länge \(k-1\).

1. Eine zufällige Färbung mit \(k\) Farben erzeugt einen bunten Pfad der Länge \(k-1\) mit Wahrscheinlichkeit \(p \geq {{c1::e^{-k} }}\).
2. Bei wiederholten Färbungen mit \(k\) Farben ist der Erwartungswert der Anzahl der Versuche, bis man einen bunten Pfad der Länge \(k-1\) erhält, \(\tfrac{1}{p} \leq {{c2::e^{k} }}\).

Für jeden Fluss \(f\) gilt: der Nettozufluss der Senke gleicht dem Wert des Flusses:\[\operatorname{netinflow}(t) := \sum_{u \in V : (u,t) \in A} f(u, t) \;-\; \sum_{u \in V : (t,u) \in A} f(t, u) \;=\; {{c1::\operatorname{val}(f)}}.\]

Für eine Kante \(e = (u, v)\) sei \(e^{\mathrm{opp}} := (v, u)\).

Im Spielraum einer Kante mit Kapazität \(c\) und Fluss \(f\) haben wir vorwärts die Restkapazität \(c - f\) und rückwärts die Restkapazität \(f\).

Sei \(N = (V, A, c, s, t)\) ein Netzwerk. Ein Fluss in \(N\) ist eine Funktion \(f : A \to \mathbb{R}\) mit:

1. {{c1::Zulässigkeit: \[0 \leq f(e) \leq c(e) \quad \text{für alle } e \in A\]}}
2. {{c2::Flusserhaltung: für alle \(v \in V \setminus \{s, t\}\) gilt \[\sum_{u \in V : (u,v) \in A} f(u, v) \;=\; \sum_{u \in V : (v,u) \in A} f(v, u)\]}}

Wahr oder falsch?

Ist \(G\) ein Graph mit maximalem Grad \(\Delta(G)\), so findet der Greedy-Algorithmus (mit beliebiger Knotenreihenfolge) stets eine zulässige Färbung mit höchstens \(\Delta(G) + 1\) Farben.

Schwache Dualität
Ist \(f\) ein Fluss und \((S, T)\) ein s-t-Schnitt in einem Netzwerk, so gilt\[{{c1::\operatorname{val}(f) \;\leq\; \operatorname{cap}(S, T)}}.\]

Wahr oder falsch?

Für einen vollständigen Graphen \(G\) mit gerader Anzahl von Knoten und positiven Gewichten \(\ell(x,y)\), der die Dreiecksungleichung erfüllt, sei \(M\) ein perfektes Matching mit minimalen Kosten und \(C\) die minimale Kosten-Reise des Handlungsreisenden (TSP-Tour).

Dann ist \(\ell(M) \leq \ell(C)/2\).

Eine Flussaugmentierung ist eine Folge von lokalen Veränderungen entlang eines s-t-Pfads, bei dem auf jeder Kante entweder \(+\delta\) (in Vorwärtsrichtung) oder \(-\delta\) (in Rückwärtsrichtung) addiert wird.

Da an Quelle und Senke keine Flusserhaltung gefordert ist, erhöht sich \(\operatorname{val}(f)\) genau um \(\delta\).

Bei der bimolekularen Reaktion \(A + B \to C\) ist die DGl \(u'(t) = k(a - u)(b - u)\) und nicht \(u'(t) = k(a + u)(b + u)\), weil?

Fundamentallösungen
Eine lineare, homogene Differentialgleichung der Ordnung \(n\) besitzt \(n\) Lösungen \(y_1(x), \dots, y_n(x)\), sodass die allgemeine Lösung gegeben ist durch
\[ {{c2::y(x) = C_1 y_1(x) + \dots + C_n y_n(x), \quad C_1, \dots, C_n \in \mathbb{R} }} \]Diese Lösungen werden Fundamentallösungen genannt.

Beschränktes (logistisches) Wachstum mit Wachstumskonstante \(k > 0\) und Kapazitätsgrenze \(L > 0\):\[ u'(t) = {{c1::k\,u(t)\left(1 - \dfrac{u(t)}{L}\right)}} \]Charakteristisches Verhalten:

• Für \(u(t) \ll L\): nahezu exponentielles Wachstum \(u' \approx k\,u\)
• Für \(u(t) \to L\): Wachstumsrate \(u' \to 0\), die Grösse stagniert bei der Kapazität \(L\)

Die Taylorreihe (Taylorentwicklung) von \(f\) um den Punkt \(a\) ist die Reihe
\[ {{c1::\sum_{k=0}^{\infty} \frac{f^{(k)}(a)}{k!} (x - a)^k = f(a) + f'(a)(x - a) + \tfrac{1}{2} f''(a)(x - a)^2 + \dots }}\]

Zum Lösen einer linearen, homogenen DGl mit konstanten Koeffizienten
\[ a_n u^{(n)}(x) + a_{n-1} u^{(n-1)}(x) + \dots + a_1 u'(x) + a_0 u(x) = 0 \]verwendet man den Eulerschen Ansatz:
\[ {{c1::u(x) = e^{\lambda x} }} \]Einsetzen liefert die charakteristische Gleichung {{c2::
\[ a_n \lambda^n + a_{n-1} \lambda^{n-1} + \dots + a_1 \lambda + a_0 = 0 \]bzw. das charakteristische Polynom \[p(\lambda) = a_n \lambda^n + a_{n-1} \lambda^{n-1} + \dots + a_1 \lambda + a_0\]}}

Binomialreihe für beliebigen Exponenten \(p \in \mathbb{R}\) (konvergiert für \(-1 < x < 1\)):
\[ (1 + x)^p = {{c1::\sum_{n=0}^{\infty} \binom{p}{n} x^n = 1 + p x + \frac{p(p-1)}{2!} x^2 + \dots }}\]

Geometrische Reihe als Potenzreihendarstellung (konvergiert für \(-1 < x < 1\)):
\[ \frac{1}{1 - x} = {{c1::\sum_{n=0}^{\infty} x^n = 1 + x + x^2 + x^3 + \dots }}\]

Taylorreihe des natürlichen Logarithmus (konvergiert nur für \(-1 < x \leq 1\)):
\[ \ln(1 + x) = {{c1::\sum_{n=1}^{\infty} (-1)^{n-1} \frac{x^n}{n} = x - \tfrac{1}{2} x^2 + \tfrac{1}{3} x^3 - \tfrac{1}{4} x^4 + \dots }}\]

Allgemeine Lösung (nur reelle Nullstellen):
Hat das charakteristische Polynom einer linearen, homogenen DGl mit konstanten Koeffizienten ausschliesslich reelle Nullstellen \(\lambda_i\) mit Multiplizität \(m_i\) (\(i = 1, \dots, r\)), so ist die allgemeine Lösung
\[ {{c1::u(x) = \sum_{i=1}^{r} \left( \sum_{p=0}^{m_i - 1} C_{ip}\, x^p \right) e^{\lambda_i x} }} \]Pro Nullstelle \(\lambda_i\) liefert das also {{c2::\(m_i\) Fundamentallösungen \(e^{\lambda_i x}, x e^{\lambda_i x}, \dots, x^{m_i - 1} e^{\lambda_i x}\)}}.

Jede beschränkte Folge reeller Zahlen hat einen Häufungspunkt und eine konvergente Teilfolge.

Proof Idea Included

Eine lineare Differentialgleichung
\[ a_n(x) y^{(n)}(x) + \dots + a_0(x) y(x) = s(x) \]heisst:

• homogen, falls \(s(x) = 0\)
• inhomogen, falls \(s(x) \neq 0\)

Die allgemeine Lösung einer DGl der Ordnung \(n\) enthält \(n\) freie Konstanten. Um eine konkrete Lösung auszuwählen, muss man also \(n\) Bedingungen vorgeben. Zwei Strategien:

1. Anfangswertproblem (AWP): Alle Bedingungen werden an derselben Stelle \(t_0\) vorgegeben, z.B. für \(n = 2\): \(u(t_0) = u_0,\ u'(t_0) = v_0\).
2. Randwertproblem (RWP): Die Bedingungen werden an verschiedenen Stellen vorgegeben, z.B. für \(n = 2\): \(u(t_0) = u_0,\ u(t_1) = u_1\) mit \(t_0 \neq t_1\).

Welche der folgenden DGl beschreibt beschränktes Wachstum (eine Grösse, die nicht beliebig gross werden kann)?

• \(u' = k\,u \cdot \dfrac{u}{L}\): nicht beschränkt: für \(u \to \infty\) wächst \(u'\) sogar quadratisch
• \(u' = k\,u\,\bigl(1 + \dfrac{u}{L}\bigr)\): nicht beschränkt: \(u'\) wächst mit \(u\) immer schneller
• \(u' = k\,u\,\dfrac{L}{u} = k\,L\): nicht beschränkt: konstantes Wachstum, also lineares unbegrenztes Wachstum
• \(u' = k\,u\,\bigl(1 - \dfrac{u}{L}\bigr)\): beschränkt, da \(u' \to 0\) für \(u \to L\) ✅

Mechanische Probleme:
Bewegung wird über die wirkenden Kräfte modelliert. Nach Newton gilt für jede Kraft \(F\):\[ F = {{c1::m\,\ddot{y} }} = m\,a \]wobei \(y\) die Position des Körpers und \(a = {{c2::\ddot{y} }}\) seine Beschleunigung ist. 

Grundprinzip beim Aufstellen von DGln aus einer Bilanz: Die Änderungsrate einer Grösse \(y(t)\) ist die Differenz aus Zuwachsrate und Abnahmerate:\[y'(t) = {{c1::\text{Zuwachs}(t) - \text{Abnahme}(t)}} \]

Bimolekulare Reaktion \(A + B \to C\) mit endlichen Anfangsmengen \(a, b\) und Reaktionskonstante \(k > 0\).
Sei \(u(t)\) die Menge des Produkts \(C\) zur Zeit \(t\). Dann lautet die DGl:\[ u'(t) = k\,(a - u(t))\,(b - u(t)) \]

Taylorreihe des Sinus (konvergiert für alle \(x \in \mathbb{R}\)):
\[ \sin(x) = {{c1::\sum_{n=0}^{\infty} (-1)^n \frac{x^{2n+1} }{(2n+1)!} = x - \tfrac{1}{3!} x^3 + \tfrac{1}{5!} x^5 - \dots}} \]

Superpositionsprinzip:
Sind \(y_1(x)\) und \(y_2(x)\) Lösungen einer linearen, homogenen Differentialgleichung, so ist auch
\[ y(x) = {{c2::C_1 y_1(x) + C_2 y_2(x), \quad C_1, C_2 \in \mathbb{R} }} \]eine Lösung der gleichen Differentialgleichung.

Taylorreihe des Sinus (konvergiert für alle \(x \in \mathbb{R}\)):
\[ \sin(x) = {{c1::\sum_{n=0}^{\infty} (-1)^n \frac{x^{2n+1} }{(2n+1)!} = x - \tfrac{1}{3!} x^3 + \tfrac{1}{5!} x^5 - \dots}} \]

5-Schritt-Methodik zum Aufstellen einer Differentialgleichung für eine Grösse \(y(t)\):

1. Veränderung in einem kleinen Zeitintervall \(\Delta t\) bilanzieren: {{c1::\(y(t + \Delta t) = y(t) + \text{Zuwachs} - \text{Abnahme}\)}}
2. Differenz bilden: \(\Delta y = y(t + \Delta t) - y(t)\)
3. Proportionale Veränderung (Differenzenquotient): {{c3::\(\dfrac{\Delta y}{\Delta t} = \dfrac{y(t + \Delta t) - y(t)}{\Delta t}\)}}
4. Grenzwert \(\Delta t \to 0\): {{c4::\(\dfrac{dy}{dt} = \lim\limits_{\Delta t \to 0} \dfrac{\Delta y}{\Delta t}\)}}
5. Differentialgleichung \(y'(t) = \dots\) zusammenfassen

Bevölkerungsmodell

Sei \(B(t)\) die Geburtenrate und \(T(t)\) die Sterberate (jeweils pro Zeiteinheit). Dann ist die DGl für die Bevölkerung \(y(t)\):\[ y'(t) = B(t) - T(t) \]

Implementation of a semaphore without spinning (with a blocking queue \(Q_S\)):

The condition test plus queue operation must be atomic (e.g. under an internal lock).
release only increments S if no one is waiting: otherwise it directly unblocks a waiting process without S ever becoming positive.

Mutual exclusion built only from atomic registers (Filter, Bakery, Peterson) is not used in practice for four reasons:

1. Space lower bound is linear in the maximum number of threads.
2. Correctness relies on no memory reordering, which requires expensive memory barriers in real hardware.
3. These algorithms are not wait-free.
4. The "primitive" assumption is unrealistic - hardware provides faster combined RMW instructions instead.

A barrier synchronises a number \(n\) of processes such that no process passes the .

The Filter Lock extends Peterson's lock from 2 to \(n\) processes by introducing \(n-1\) levels:
Each thread climbs from level 1 up to level \(n-1\), and at each level \(\ell\) it sets \(\texttt{level[me]} = \ell\) and \(\texttt{victim}[\ell] = \texttt{me}\), then waits while
\(\exists k \neq \texttt{me}: \texttt{level}[k] \geq \ell \;\land\; \texttt{victim}[\ell] = \texttt{me}\)

When applying resource ordering and the objects do not have a natural total order, generate one:
Each instance is assigned a unique final long index from a class-level AtomicLong counter via counter.incrementAndGet() in the constructor.
Locks are then always acquired in ascending order of index.

Correct (one-shot) barrier with semaphores mutex = 1, barrier = 0 and integer count = 0:

acquire(mutex)
count++
release(mutex)
if (count == n) release(barrier)
acquire(barrier)
release(barrier)

The mutex protects the race on count++.
The trailing acquire(barrier); release(barrier); is called a turnstile and ensures that each thread that gets through immediately admits the next, so all \(n\) threads pass in sequence.

java.util.concurrent.atomic.AtomicBoolean exposes two key RMW operations on top of plain get / set:

1. compareAndSet(expect, update), which atomically writes update iff the current value equals expect and returns true on success.
2. getAndSet(newValue), which atomically writes newValue and returns the previous value.