Anki Deck Changes

Hashfunktion (Annahmen)
Falls die Elemente in \(D\) gross sind und Speicherzugriffe sowie Vergleiche teuer sind, verwendet man eine Hashfunktion \(h : U \to [m]\) mit zwei Eigenschaften:

• \(h\) ist effizient berechenbar
• {{c2::\(h\) verhält sich wie eine Zufallsfunktion: \(\forall u \in U\;\forall i \in [m]:\; \Pr[h(u) = i] = \tfrac{1}{m}\), unabhängig für verschiedene \(u\)}}

Floyd's Cycle Finding (Schlüsseleigenschaft)
Definiere die Folge \(x_0 := n,\; x_i := a[x_{i-1}]\) für \(i \geq 1\). Sei der Pfad \(k \geq 1\) Kanten lang und der Kreis \(\ell \geq 3\) Kanten lang.
Wähle \(0 \leq r < \ell\) und \(s \geq 1\) mit \(k + r = s\ell\). Dann gilt:\[x_{k+r} = {{c2::x_{2(k+r)} }}.\]Insbesondere existiert ein {{c3::\(i \leq n\) mit \(x_i = x_{2i}\)}}.

Selektionsproblem: Bestimme in einer Folge \((A[1], \ldots, A[n])\) paarweise verschiedener Zahlen den \(k\)-kleinsten Wert.

Naiver Ansatz: Sortieren + Index, Laufzeit \(O(n \log n)\).

Schneller geht es mit QuickSelect (erwartet \(O(n)\)):

QuickSelect(A, ℓ, r, k):
  p ← Uniform({ℓ, ℓ+1, ..., r})
  t ← Partition(A, ℓ, r, p)
  if t = ℓ + k - 1: return A[t]    # gefunden
  else if t > ℓ + k - 1:
    return QuickSelect(A, ℓ, t-1, k)     # links
  else:
    return QuickSelect(A, t+1, r, k - t) # rechts

Floyd's Cycle Finding (Phase 1)
Wie wird mit nur drei Variablen ein \(i \geq 1\) mit \(x_i = x_{2i}\) berechnet, und welche Bedeutung hat das gefundene \(i\)?

Datensatz und Duplikate
Ein Datensatz \(D = (s_1, s_2, \ldots, s_n)\) ist eine Folge von \(n\) Elementen.
Ein Paar \((i, j)\) mit \(1 \leq i < j \leq n\) heisst Duplikat in \(D\), falls \(s_i = s_j\).

Floyd's Cycle Finding (Phase 2)
Nach Phase 1 ist ein Treffpunkt mit \(i = k + r\) bekannt. Wie bestimmt man daraus die gesuchten Indizes \(i \neq j\) mit \(a[i] = a[j]\)?

Lösung mit Hashmap
Beschreibe den Algorithmus und nenne den entscheidenden Unterschied zur Sortier-Lösung.

Floyd's Cycle Finding (Aufgabenstellung)
Gegeben ein Array \(a[1, \ldots, n]\) mit \(a[i] \in \{1, \ldots, n-1\}\). Finde zwei Indizes \(i \neq j\) mit \(a[i] = a[j]\), unter folgenden Einschränkungen:

• Laufzeit \(O(n)\)
• Das Array \(a\) darf nicht verändert werden (Zugriffe \(a[i]\) sind beliebig oft erlaubt)
• Nur \(O(1)\) zusätzliche Speicherzellen

Kollision
Eine Kollision ist ein Paar \((i, j)\) mit \(1 \leq i < j \leq n\), \(s_i \neq s_j\) und \(h(s_i) = h(s_j)\).
Anschaulich: Kollisionen sind die neuen (unerwünschten) Duplikate in der Hashmap, also Hashmap-Duplikate, die im Original keine sind.

Erwartete Anzahl Kollisionen
Für eine Hashfunktion \(h : U \to [m]\) mit \(\Pr[h(u) = i] = \tfrac{1}{m}\) gilt:\[\mathbb{E}[\#\text{Kollisionen}] \leq {{c1::\binom{n}{2} \cdot \tfrac{1}{m}}}.\]Insbesondere folgt mit der Wahl \(m = n^2\): \(\mathbb{E}[\#\text{Kollisionen}] < 1\).

Floyd's Cycle Finding (Resultat)
Auf einem Array \(a[1, \ldots, n]\) mit \(a[i] \in \{1, \ldots, n-1\}\) findet der Hase-und-Igel-Algorithmus zwei Indizes \(i \neq j\) mit \(a[i] = a[j]\) in:

• Laufzeit \(O(n)\)
• Zusätzlicher Speicher: nur vier Variablen (igel, hase, i, j)

Das Array \(a\) wird dabei nicht verändert.

Erste Lösung für das Duplikate-finden-Problem
Beschreibe den Algorithmus und gib seine Laufzeit an.

Wichtige Eigenschaften der Hashwerte
Jedes \(h(s_i)\) ist zufällig gleichverteilt in \([m]\), aber es gilt deterministisch \(s_i = s_j \Rightarrow h(s_i) = h(s_j)\).
Wir wählen \(m\) viel kleiner als \(|U|\), also Komprimierung.

Floyd's Cycle Finding (Graph-Reformulierung)
Definiere den gerichteten Graphen \(D = (V, A)\) mit \(V = [n]\) und {{c2::\(A = \{(i, a[i]) \mid 1 \leq i \leq n\}\)}}.
Eigenschaften:

• Jeder Knoten hat genau eine ausgehende Kante
• Knoten \(n\) hat keine eingehende Kante (weil \(a[i] \neq n\) für alle \(i\))
• Der von Knoten \(n\) ausgehende Subgraph (immer der ausgehenden Kante folgen) besteht aus einem Pfad gefolgt von einem Kreis (\(\rho\)-Form)

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:

Die Ausgangsstoffe \(A\) und \(B\) liegen in endlicher Menge vor und werden mit der Reaktion verbraucht. Die verbleibenden Mengen sind \(a - u\) bzw. \(b - u\), nicht \(a + u\) bzw. \(b + u\).

Konsequenz: Die Reaktion stoppt, sobald \(u = \min(a, b)\), weil dann ein Edukt aufgebraucht ist und \(u' = 0\) wird.

Eine lineare Differentialgleichung \(a_n(x) y^{(n)} + \dots + a_0(x) y = s(x)\) heisst DGl mit konstanten Koeffizienten, falls alle Funktionen \(a_i(x)\) konstante Funktionen sind (d.h. \(a_i(x) = a_i \in \mathbb{R}\)).

Satz (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
\[ 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\):

\[ {{c1::u'(t) = 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\)

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:
\[ 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 {{c3::\(p(\lambda) = a_n \lambda^n + a_{n-1} \lambda^{n-1} + \dots + a_1 \lambda + a_0\)}}.

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

Eine Differentialgleichung der Form
\[ a_n(x) y^{(n)}(x) + a_{n-1}(x) y^{(n-1)}(x) + \dots + a_1(x) y'(x) + a_0(x) y(x) = s(x) \]heisst lineare Differentialgleichung mit Koeffizienten \(a_i(x)\).

• Die Ordnung der DGl ist die maximale Ordnung der vorkommenden Ableitungen.
• Die Funktion \(s(x)\) nennt man Störfunktion.

Alle drei Transformationen (Streckung/Verschiebung in x- und y-Richtung) sind darstellbar als zusammengesetzte Funktion: \[ g(x) = s(u(x)) = s \circ u(x) \]Dabei nennt man \(s\) die äussere und \(u\) die innere Funktion.

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

Allgemeine Lösung (mit komplexen Nullstellen): Hat das charakteristische Polynom \(r\) reelle Nullstellen \(\lambda_i\) (Multiplizität \(m_i\)) und \(s\) Paare komplexer Nullstellen \(a_j \pm i b_j\) (Multiplizität \(m_j\)), so ist die allgemeine Lösung
\[ \begin{gathered} u(x) = \sum_{i=1}^{r} \left( \sum_{p=0}^{m_i - 1} C_{ip}\, x^p \right) e^{\lambda_i x} \\ {{c1::+ \sum_{j=1}^{s} \sum_{q=0}^{m_j - 1} \left( A_{jq}\, x^q\, e^{a_j x} \sin(b_j x) + B_{jq}\, x^q\, e^{a_j x} \cos(b_j x) \right)}} \end{gathered} \]
Pro komplexem Paar \(a_j \pm i b_j\) treten also Fundamentallösungen der Form {{c2::\(x^q e^{a_j x} \sin(b_j x)\) und \(x^q e^{a_j x} \cos(b_j x)\) für \(q = 0, \dots, m_j - 1\)}} auf.

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:

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

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\):

\[ {{c1::F = m\,\ddot{y} = m\,a}} \]
wobei \(y\) die Position des Körpers und {{c3::\(a = \ddot{y}\) seine Beschleunigung}} ist. Die DGl entsteht, indem alle Kräfte aufsummiert und gleich \(m\,\ddot{y}\) gesetzt werden.

Grundprinzip beim Aufstellen von DGln aus einer Bilanz: Die Änderungsrate einer Grösse \(y(t)\) ist die Differenz aus Zuwachsrate und Abnahmerate:

\[ {{c2::y'(t) = \text{Zuwachs}(t) - \text{Abnahme}(t)}} \]
Beide Raten sind in Einheiten pro Zeit angegeben und dürfen von \(t\) und/oder von \(y(t)\) selbst abhängen.

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)) \]
Idee: Die Reaktionsrate ist proportional zum Produkt der verbleibenden Mengen \((a - u)\) von \(A\) und \((b - u)\) von \(B\), weil pro entstandenem \(C\) je ein \(A\) und ein \(B\) verbraucht werden.

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

Definition Differentialgleichung: Eine Differentialgleichung ist eine Gleichung, in welcher die gesuchte Funktion sowie deren Ableitungen auftreten.

Bezeichnungen am Beispiel \(u'(t) = r(a - u(t))\):

• \(t\) heisst unabhängige Variable
• \(u\) heisst abhängige Variable (gesuchte Funktion)

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

1. Schritt 1: Veränderung in einem kleinen Zeitintervall \(\Delta t\) bilanzieren: {{c1::\(y(t + \Delta t) = y(t) + \text{Zuwachs} - \text{Abnahme}\)}}
2. Schritt 2: Differenz bilden: \(\Delta y = y(t + \Delta t) - y(t)\)
3. Schritt 3: Proportionale Veränderung (Differenzenquotient): {{c3::\(\dfrac{\Delta y}{\Delta t} = \dfrac{y(t + \Delta t) - y(t)}{\Delta t}\)}}
4. Schritt 4: Grenzwert \(\Delta t \to 0\): {{c4::\(\dfrac{dy}{dt} = \lim\limits_{\Delta t \to 0} \dfrac{\Delta y}{\Delta t}\)}}
5. Schritt 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) \]
Begründung: Im Intervall \(\Delta t\) gilt \(y(t+\Delta t) = y(t) + B(t)\,\Delta t - T(t)\,\Delta t\), und der Grenzwert \(\Delta t \to 0\) liefert die DGl.

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

acquire(S):                 release(S):
  if S > 0: dec(S)            if Q_S == \(\emptyset\): inc(S)
  else: put(Q_S, self);        else: get(Q_S, p);
        block(self)                  unblock(p)

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.

In the 2nd reusable-barrier trial, the release(mutex) is moved to after the release(barrier) on the entry side (and analogously on the exit side). It still fails because a single process can lap the others: while \(n-1\) processes are still in the post-barrier region, one fast process re-enters the entry section, increments count, and could even reach count == n a second time before the others have finished the first round. Violated invariant: "even when a single process has passed the barrier, barrier = 0": the lapping process leaves barrier open behind it.

The three conditions for a correct critical-section solution according to Ben-Ari are:

1. Mutual exclusion (statements from CSes of different processes must not interleave).
2. Freedom from deadlock (if some processes are trying to enter a CS, at least one must eventually succeed).
3. Freedom from starvation (any process trying to enter its CS must eventually succeed).

A barrier synchronises a number \(n\) of processes such that no process passes the barrier until all \(n\) of them have reached it.

When constructing mutex algorithms from atomic registers, three assumptions are made:

1. atomic reads and writes of primitive-type variables
2. no reorderings of read/write sequences (not true in practice; assumed here for simplicity) 
3. threads that enter a critical section eventually leave it.

About progress outside the critical section, no assumption is made.

Two-phase barrier solution: with mutex=1, barrier1=0, barrier2=1, count=0,

acquire(mutex)
count++
if (count==n) { acquire(barrier2); release(barrier1); }
release(mutex)
acquire(barrier1); release(barrier1);   // phase 1
acquire(mutex)
count--
if (count==0) { acquire(barrier1); release(barrier2); }
release(mutex)
acquire(barrier2); release(barrier2);   // phase 2

Idea: two semaphores act as alternating gates: the \(n\)-th arriver flips barrier1 open and barrier2 closed; the last leaver flips them back. Between phases the invariant is barrier1 = 1 and barrier2 = 0 for all processes (and after phase 2: barrier1 = 0, barrier2 = 1).

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.

Starvation denotes the repeated but unsuccessful attempt of a recently unblocked process to continue its execution.