Anki Deck Changes

• \(A := {{c1::\{(x, y), (y, x) \mid \{x, y\} \in E\} }}\) (jede ungerichtete Kante wird zu zwei gerichteten Kanten),
• \(c \equiv 1\),
• Quelle \(u\), Senke \(v\).

1. Beginnend bei \(u\), laufe entlang gerichteter, ungebrauchter Kanten mit Fluss 1 bis man bei \(v\) ankommt; durchlaufene Kanten werden als gebraucht markiert.
2. Wiederhole das Verfahren {{c2::\(\operatorname{val}(f)\) Mal}}.
3. Das liefert \(\operatorname{val}(f)\) kantendisjunkte \(u\)-\(v\)-Pfade (nach Entfernen von Kreisen).

• Flusswerte: {{c1::\(f(e) \in \{0, 1\}\)}} für alle Kanten \(e\).
• Für jeden Knoten \(w \notin \{u, v\}\): {{c2::\(\operatorname{indeg}_f(w) = \operatorname{outdeg}_f(w)\)}} (Flusserhaltung in inneren Knoten).
• \(\operatorname{val}(f) = {{c3::\operatorname{outdeg}_f(u) - \operatorname{indeg}_f(u) = \operatorname{indeg}_f(v) - \operatorname{outdeg}_f(v)}}\).

1. Laufzeit: \(O\!\big(\varepsilon \cdot (2e)^k \cdot k \cdot m\big)\), wobei \(m = |E|\).
2. Antwortet der Algorithmus mit JA, dann hat \(G\) einen Pfad der Länge \(k-1\) (kein false positive: einseitiger Fehler).
3. Hat \(G\) einen Pfad der Länge \(k-1\), dann ist die Wahrscheinlichkeit, dass der Algorithmus mit NEIN antwortet, höchstens {{c3::\(e^{-\varepsilon}\)}}.

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

• \(s \neq t\) sind zwei neue Knoten (Quelle und Senke).
• \(A := {{c2::\{s\} \times U \;\cup\; \{(u, w) \in U \times W : \{u, w\} \in E\} \;\cup\; W \times \{t\} }}\)
• \(c \equiv 1\) (alle Kapazitäten gleich 1).

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

• Jedem Matching \(M\) in \(G\) entspricht ein ganzzahliger Fluss \(f_M\) in \(N_G\) mit {{c1::\(\operatorname{val}(f_M) = |M|\)}}.
• Jedem ganzzahligen Fluss \(f\) in \(N_G\) entspricht ein Matching \(M\) in \(G\) mit {{c1::\(|M| = \operatorname{val}(f)\)}}.

• Greedy funktioniert nicht (liefert nur ein inklusionsmaximales Matching).
• Lösungsansatz: Reduktion auf Maxflow.

• Physikalische Zufallsgeneratoren: Lottozahlen, Geigerzähler, Rauschen, Quantenexperimente.
• Deterministische (Pseudo-)Zufallsgeneratoren: liefern, basierend auf einem Startwert (seed) \(s\), eine Folge \(s \to r_0(s), r_1(s), r_2(s), \ldots\) Das ermöglicht Reproduzierbarkeit, wenn man sich den .

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

• \(\alpha : P \to \mathbb{R}_0^{+}\): \(\alpha_p\) grösser \(\Rightarrow\) Pixel \(p\) eher im Vordergrund.
• \(\beta : P \to \mathbb{R}_0^{+}\): \(\beta_p\) grösser \(\Rightarrow\) Pixel \(p\) eher im Hintergrund.
• \(\gamma : E \to \mathbb{R}_0^{+}\): \(\gamma_e\) grösser \(\Rightarrow\) benachbarte Pixel eher im gleichen Teil.

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

• Neue Knoten \(s\) (Quelle) und \(t\) (Senke).
• Für jedes \(p \in P\): gerichtete Kante \((s, p)\) mit Kapazität \(\alpha_p\).
• Für jedes \(p \in P\): gerichtete Kante \((p, t)\) mit Kapazität \(\beta_p\).
• Für jede Bildkante \(e = \{p, p'\} \in E\): zwei gerichtete Kanten \((p, p')\) und \((p', p)\), je mit Kapazität \(\gamma_e\).

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

while (true) {
  Node first = head.get();
  Node last  = tail.get();
  Node next  = first.next.get();
  if (first == last) {
    if (next == null) return null;          // truly empty
    else tail.compareAndSet(last, next);    // help advance tail
  } else {
    T value = next.item;
    if (head.compareAndSet(first, next))
      return value;
  }
}

while (true) {
  Window w = find(head, key);
  Node pred = w.pred, curr = w.curr;
  if (curr.key != key) return false;
  Node succ = curr.next.getReference();
  snip = curr.next.attemptMark(succ, true);  // step 1
  if (!snip) continue;                       // mark failed, retry
  pred.next.compareAndSet(curr, succ, false, false); // step 2, ignore result
  return true;
}

public Long pop() {
  Node head, next;
  do {
    head = top.get();
    if (head == null) return null;
    next = head.next;
  } while (!top.compareAndSet(head, next));
  return head.item;
}