platzeffiziente-algorithmen.tex

\documentclass{cheat-sheet}

\pdfinfo{
  /Title (Zusammenfassung Platzeffiziente Algorithmen)
  /Author (Tim Baumann)
}

\usepackage{algorithmicx}
\usepackage[noend]{algpseudocode}
\usepackage{nicefrac}

% Kleinere Klammern
\delimiterfactor=701

\newcommand{\ceil}[1]{\lceil #1 \rceil} % Aufrunden
\newcommand{\floor}[1]{\lfloor #1 \rfloor} % Abrunden
\renewcommand{\O}{\mathcal{O}} % Landau-O
\newcommand{\Push}{\Leftarrow} % etwas auf den Stack pushen
\newcommand{\Pop}{\Leftarrow} % etwas vom Stack nehmen
\algnewcommand\To{\textbf{to}}
\algnewcommand\Continue{\textbf{continue}}

\begin{document}

\raggedcolumns % stretche Inhalt nicht über die gesamte Spaltenhöhe

\maketitle{Zusammenfassung Platzeffiziente Alg.}

Basierend auf dem Skript zur gleichnamigen Vorlesung von Prof. Dr. Torben Hagerup an der Universität Augsburg im WS15/16.

% Vorlesung vom 14.10.2015

% 1. Introduction

\begin{ziel}
  Algorithmen entwerfen, die wenig Speicherplatz und Speicherzugriffe benötigen, aber trotzdem schnell sind.
\end{ziel}

% 2. Reachability
\section{Erreichbarkeit in Graphen}

\begin{prob}[\emph{Erreichbarkeit}]
  Gegeben sei ein gerichteter oder ungerichteter Graph, ein Startknoten und ein Zielknoten darin. \\
  Frage: Ist der Zielknoten vom Startknoten erreichbar?
\end{prob}

\iffalse
\begin{alg}
  Algorithmen, mit denen man das Erreichbarkeits-Problem lösen kann, sind Breiten- und Tiefensuche.
\end{alg}
\fi

% 2.1. Depth-First-Search and Recursion

\begin{lem}
  Es sei ein Graph mit $n$ Knoten und $m$ Kanten gegeben.
  Tiefensuche benötigt $\Theta(n+m)$ Zeit und $\Theta(n \log n)$ Speicherplatz.
\end{lem}

% 2.2. Savitch's Algorithm

\begin{alg}[\emph{Savitch}]\mbox{}\\[4pt]
%\begin{algorithm}
  %\caption{Savitch's Algorithmus}
  \begin{algorithmic}[1]
    \Function{sReachable}{$u, v, k$}
      \If{$u = v$} \Return true \EndIf
      \If{$k = 0$} \Return false \EndIf
      \If{$(u,v) \in E$} \Return true \EndIf
      \If{$k=1$} \Return false \EndIf
      \For{$x \in V$}
        \If{\Call{sReachable}{$u, x, \floor{\tfrac{k}{2}}$} $\wedge$ \Call{sReachable}{$x, v, \ceil{\tfrac{k}{2}}$}}
          \State \Return true
        \EndIf
      \EndFor
      \State \Return false
    \EndFunction
    \State \Return sReachable(s,t,n-1)
  \end{algorithmic}
%\end{algorithm}
\end{alg}

% Thm 2.1
\begin{lem}
  Savitch's Alg. löst Erreichbarkeit mit $\O((\log n)^2)$ Bits.
\end{lem}

\begin{samepage}

\begin{bem}
  Die Laufzeit von Savitch's Alg. ist allerdings sehr schlecht, im schlechtesten Fall (\zB{} bei einer verketteten Liste) $n^{\Theta(\log n)}$.
\end{bem}

% Vorlesung vom 21.10.2015

% §3. The Representation of Graphs
\section{Die Repräsentation von Graphen}

\end{samepage}

% 3.1. Adjacency Matrices and Adjacency Lists
% und 3.2. Graph Representation with Little Memory

\begin{bem}
  Eine Darstellung eines Graphen als Adjazenzmatrix benötigt $O(n^2)$, eine Darstellung als Adjazenzliste/-array $O(m \cdot \log n)$ Bits.
  Manchmal ist es nützlich, zusätzlich Rückwärtskanten oder Aus- und Ingrad von Knoten zu speichern, um diese Informationen nicht mehrmals berechnen zu müssen. Bei bestimmten Algorithmen werden sie auch als gegeben angenommen.
  % Ausgelassen: 'mates', Multigraphen
\end{bem}

% 3.3 Common Input Requirements

\begin{konv}
  Wir werden folgende Graphfunktionen benutzen:
  
  \begin{tabular}{r l}
    Funktion & Ergebnis \\[3pt] \hline
    $\text{adjfirst} : V \to P$ & ersten Eintrag in der Adjazenzliste \\
    $\text{adjhead} : P \to V$ & Knoten zum Eintrag in der Adjazenzliste \\
    $\text{adjnext} : P \to P$ & nächsten Eintrag in der Adjazenzliste \\
    $\text{deg} : V \to \N$ & Ausgrad eines Knoten \\
    $\text{head} : A \to V$ & den $k$-ten Nachbar eines Knoten \\
    $\text{tail} : B \to V$ & den $k$-ten In-Nachbar eines Knoten \\
    $\text{mate} : A \to A$ & den "`Mate"' einer Kante (bei unger. Graphen)
  \end{tabular}
  \begin{align*}
    \text{wobei} \quad
    A &\coloneqq \Set{(v, k) \in V \times \N}{1 \leq k \leq \text{deg}(v)} \\
    B &\coloneqq \Set{(v, k) \in V \times \N}{1 \leq k \leq \text{indeg}(v)}
  \end{align*}
\end{konv}

% §4. Depth-First search
\section{Tiefensuche}

\begin{alg}
  Bei einer Tiefensuche in einem Graphen wird am meisten Platz für den Laufzeitstack verbraucht. Um diesen Platz zu optimieren, ist es geschickt, zunächst den Algorithmus mit explizitem Keller aufzuschreiben:
  \begin{algorithmic}[1]
    \Function{process}{$u$}
      \State $S \Push (u, \Call{adjfirst}{u})$
      \While{$S \neq \emptyset$}
        \State $(u, p) \Pop S$
        \If{$color[u] = white$}
          \State $color[u] \coloneqq gray$
          \State $\Call{preprocess}{u}$
        \EndIf
        \If{$p \neq null$}
          \State $S \Push (u, \Call{adjnext}{p})$
          \State $v \coloneqq \Call{adjhead}{u, p}$
          \State $\Call{preexplore}{u, v, color[v]}$
          \If{$color[v] = white$}
            \State $S \Push (v, \Call{adjfirst}{v})$
          \Else
            \State $\Call{postexplore}{u, v}$
          \EndIf
        \Else
          \State $\Call{postprocess}{u}$
          \If{$S \neq \emptyset$}
            \State $(w, \blank) \coloneqq \Call{peek}{S}$
            \State $\Call{postexplore}{w, u}$
          \EndIf
          \State $color[u] \coloneqq black$
        \EndIf
      \EndWhile
    \EndFunction
  \end{algorithmic}
\end{alg}

% §4.1 DFS with logarithmic slowdown

% 4.1
\begin{thm}
  Für alle $\epsilon > 0$ gibt es ein $n_0 \in \N$, sodass eine Tiefensuche eines Graphen (repräsentiert mit Adjazenzlisten) mit $n \geq n_0$ Ecken und $m$ Kanten in $\O((n+m) \log n)$ Zeit und $(\log_2 3 + \epsilon) n$ Bits an Arbeitsspeicher durchgeführt werden kann.
\end{thm}

\begin{alg}[\emph{DFS with logarithmic slowdown}] \mbox{}\\
  Teile den Stack in Segmente der Größe $q$ auf, wobei $q = \Theta(\nicefrac{n}{\log n})$.
  Wir behalten immer nur die obersten beiden Segmente des imaginä- ren vollständigen Stacks~$S$ auf dem Stack~$S'$ unseres Algorithmus.
  Falls~$S'$ leerläuft, so müssen wir die obersten Segmente rekonstru- ieren: Dazu färben wir alle grauen Knoten wieder weiß und führen eine erneute Tiefensuche beginnend beim Startknoten aus.
\end{alg}

% §4.2 Space-Efficient DFS in Linear Time

% 4.2
\begin{thm}
  Eine Tiefensuche eines Graphen (repräsentiert mit Adjazenz- \textit{arrays}) mit $n$ Ecken kann in $\O(n+m)$ Zeit und $\O(n \log \log n)$ Bits an Arbeitsspeicher durchgeführt werden.
\end{thm}

\begin{alg}[\emph{$\log n$ shades of gray}] \mbox{}\\
  Wir ändern den vorhergehenden Algorithmus folgendermaßen ab:
  Wir behalten nicht bloß die obersten beiden Segmente von $S$ auf dem Stack $S'$, sondern auch zusätzlich von jedem Segment den obersten Knoten, den \textit{Trailer}.
  Wir starten die Rekonstruktion nicht beim Startknoten, sondern beim Trailer des Segments unter dem Segment, das wir rekonstruieren wollen.
  Vor dem Rekonstruieren löschen wir die Farben nicht, da dies zu viel Laufzeit kosten würde.
\end{alg}

\begin{samepage}

% sollte eigentlich Teil der Algorithmus-Umgebung sein, ich habe aber leider nicht rausfinden können, wie man Spalten-Umbrüche innerhalb einer solchen Umgebung zulässt
Während des Rekonstruierens müssen wir für jeden grauen Knoten wissen, ob er weiter unten im Stack liegt, oder ob wir ihn rekonstruieren müssen.
Dazu verwenden wir $\O(\nicefrac{n}{q}) = \O(\log n)$ Grautöne, einen für jede Segmenttiefe, wobei tiefere Segmente dunklere Grautöne bekommen.
Zum Speichern der Grautöne von allen Knoten benötigen wir $\O(n \log \log n)$ Bits.

Damit wir beim Rekonstruieren die Adjazenzlisten der Knoten nicht wiederholt durchlaufen müssen, speichern wir für jeden Knoten (annähernd), wie weit wir in der Liste schon fortgeschritten sind.
Genauer speichern wir die exakte Position für Knoten mit $\geq \nicefrac{m}{q}$ ausgehenden Kanten.
Falls ein Knoten~$u$ weniger ausgehende Kanten besitzt, so speichern wir nur die $\O(\log \log n)$-Bit-Approximation
\[
  f_u \coloneqq \floor{\tfrac{k-1}{g_u}}, \quad
  \text{mit} \quad
  g_u \coloneqq \ceil{\tfrac{\deg(u)}{\ell}}, \enspace
  \ell \coloneqq \Theta(\log n).
\]

% §5. Applications of DFS
\section{Anwendungen von Tiefensuche}

\end{samepage}

% §5.1 Topological Sorting
\subsection{Topologisches Sortieren}

\begin{alg}[Topologisches Sortieren eines azyklischen Graphen]
  Führe eine Tiefensuche durch.
  Lege in $\Call{postProcess}{u}$ den Knoten $u$ auf einen Stack.
  Gebe nach Abschluss der Tiefensuche alle Knoten auf dem Stack aus, also in umgekehrter Reihenfolge, wie sie auf den Stack gelegt wurden.
\end{alg}

\begin{problem}
  Die Maximalgröße des Stacks beträgt $\O(n \log n)$.
\end{problem}

\begin{lem}
  Wenn eine Folge von $n$ Elementen à $\O(\log n)$ Bits in $t(n)$ Zeit und mit $s(n)$ Bits berechnet werden kann, so kann die umgekehrte Folge in $\O(t(n) \log n)$ Zeit und $\O(s(n) + n)$ Bits berechnet werden.
\end{lem}

\begin{proof}
  Wir berechnen die Folge mehrmals und speichern jeweils ein Segment mit $\O(\nicefrac{n}{\log n})$ Elementen der Ausgabe, angefangen beim letzten, drehen dieses um und geben es aus.
\end{proof}

\begin{kor}
  Die topologische Sortierung eines azyklischen Graphen, der mit Adjazenzarrays repräsentiert wird, kann in $\O((n + m) \log n)$ Zeit und mit $\O(n \log \log n)$ Bits an Speicher berechnet werden.
\end{kor}

\begin{bezeichnung}
  Wir nennen die Aufrufe von $\Call{preProcess}$ und $\Call{postProcess}$ und Aufrufe, denen ein Aufruf einer dieser Prozeduren vorausgeht oder folgt, \textit{Hauptaufrufe}.
\end{bezeichnung}

\begin{bem}
  Während der Tiefensuche eines Graphen mit $n$ Knoten passieren maximal $6 n$ Hauptaufrufe.
\end{bem}

% 5.1
\begin{lem}
  Sei $G$ ein gericht. Graph mit $n$ Knoten und $m$ Kanten. \\
  Ein Stream der Hauptaufrufe bei einer Tiefensuche von~$G$ in umge- kehrter Reihenfolge kann mit $\O(n \log \log n)$ Bits an Speicher und in
  \[
    \begin{cases}
      \O((n+m) \log n) & \text{falls $G$ mit Adjazenzlisten repräsentiert wird,} \\
      \O(n \log \log n) & \text{falls $G$ mit Adjazenzarrays repräsentiert wird}
    \end{cases}
  \]
  Zeit berechnet werden.
\end{lem}

\begin{proof}
  Wir teilen die Ausführung einer Tiefensuche auf $G$ in $\O(\log n)$ \textit{Epochen} auf, in denen jeweils $\O(\nicefrac{n}{\log n})$ Hauptaufrufe stattfinden.
  Wir führen dann jede Epoche, beginnend bei der letzten erneut aus, wobei wir die Hauptaufrufe mitloggen und danach in umgekehrter Reihenfolge ausgeben.
  Es bleibt noch zu klären, wie wir den Zustand des Stacks zu Beginn einer Epoche wiederherstellen können.
  Dazu speichern wir für jede Epoche den obersten Knoten $H$ auf dem Stack sowie den tiefsten Knoten $\hat{H}$, der während der Epoche verändert wird.
  Dann brauchen wir bloß den Teil des Stacks ab $\hat{H}$ bis $H$ rekonstruieren.
  Dazu müssen wir noch wissen, welche Farbe ein jeder Knoten zu Beginn einer jeden Epoche besitzt.
  Dies können wir uns merken, indem wir für jeden Knoten speichern, in welcher Epoche er grau und in welcher er schwarz geworden ist.
\end{proof}

% 5.2
\begin{kor}
  Eine topologische Sortierung eines gerichteten azyklischen Graphen mit $n$ Knoten und $m$ Kanten, der mit Adjazenzarrays repräsentiert wird, kann in $\O(n + m)$ Zeit und $\O(n \log \log n)$ Bits berechnet werden.
\end{kor}

% §5.2 Computing Strongly Connected Components
\subsection{Starke Zusammenhangskomponenten}

% TODO

\begin{alg}[Starke Zshgskomponenten durch TS] \mbox{}\\
  Führe eine Tiefensuche $S$ auf $G$ durch.
  Führe dann eine Tiefensuche $\overleftarrow{S}$ auf dem Graph $\overleftarrow{G}$ durch, wobei man neue Tiefensuchbäume bei dem Knoten beginnt, bei dem $S$ als letztes fertig wurde, und gebe alle Knoten aus.
  Wenn $\overleftarrow{S}$ einen Tiefensuchbaum abschließt, so endet auch eine starke Zshgskomponente.
\end{alg}

% 5.3
\begin{thm}
  Die starken Zusammenhangskomponenten eines gerichteten Graphen mit $n$ Knoten und $m$ Kanten, der mit Aus- und In-Adjazenzarrays repräsentiert wird, kann in $\O(n + m)$ Zeit mit $\O(n \log \log n)$ Bits an Speicher berechnet werden.
\end{thm}

\begin{bem}
  Die Ausgabe ist dabei eine Liste von Knoten, in einer beliebigen Reihenfolge, gruppiert nach starken Zshgskomponenten.
  Es ist kein Algorithmus mit gleichen Platz- und Zeitanforderungen bekannt, der die Knoten sortiert zusammen mit der Nummer der Zshgskomponente ausgibt.
\end{bem}

% §5.3 Streams

\begin{folgerung}
  Im platzbeschränkten Setting ist es wichtig, genau zu spezifizieren, wie die Ausgabe eines Algorithmus auszusehen hat.
  Die Ausgabe ist dabei häufig ein \textit{Stream}, eine Liste, die kontinuierlich produziert wird.
  Sie muss oft direkt weiterverarbeitet werden, weil man nicht den Platz hat, ihn zu speichern.
\end{folgerung}

% §6. Connected Components and BFS
\section{Zshgskomponenten und Breitensuche}

% TODO
\begin{bem}
  Die Zshgskomponenten eines ungerichteten Graphen kann mit Tiefensuche berechnet werden.
  Mit anderen Explorierungs- strategien sind jedoch effizientere Algorithmen möglich.
\end{bem}

\begin{alg}[\emph{Connected Components} mit Lücken] \mbox{}
  \begin{algorithmic}[1]
    \Function{CC}{$G$}
      \State $k \coloneqq 0$
      \For{$u := 1 \ \To\ n$}
        \State $color[u] \coloneqq white$ \EndFor
      \For{$u := 1 \ \To\ n$}
        \If{$color[u] \neq white$}
          \State \Continue
        \EndIf
        \State $k \coloneqq k + 1$
        \While{at least one vertex is gray}
          \State Let $v$ be a gray vertex
          \State $\Call{output}{v, k}$
          \ForAll{neighbors $w$ of $v$}
            \If{$color[w] = white$}
              \State $color[w] \coloneqq gray$
            \EndIf
            \State $color[v] \coloneqq black$
          \EndFor
        \EndWhile
      \EndFor
    \EndFunction
  \end{algorithmic}
\end{alg}

\begin{bem}
  Um diesen Algorithmus zu implementieren, benötigt man eine Datenstruktur, die sich die grauen Knoten merkt:
\end{bem}

% 6.1 Choice dictionaries
\subsection{Choice Dictionaries}

\begin{defn}
  Ein \emph{Choice Dictionary} der Größe $n$ ist eine Datenstruktur, welche eine (initial leere) Teilmenge $I \subset [n] \coloneqq \{ 1, \ldots, n \}$ verwaltet und folgende Operationen unterstützt:
  
  \begin{tabular}{r l}
    Aufruf & Resultat \\[3pt] \hline
    $\Call{insert}{i}$ & Füge $i \in [n]$ zu $I$ hinzu \\
    $\Call{delete}{i}$ & Nehme $i \in I$ aus $I$ heraus \\
    $\Call{isMember}{i}$ & Prüfe, ob $i \in [n]$ in $I$ enthalten ist \\
    $\Call{someId}{\,}$ & Gebe ein beliebiges Element von $I$ zurück \\
    $\Call{allIds}{\,}$ & Gebe alle Elemente von $I$ zurück (als Stream)
  \end{tabular}
\end{defn}

\begin{lem}[CD\textsubscript{1}]
  Man kann ein Choice-Dictionary der Größe $n$, welches die ersten vier Operationen in konstanter Zeit und $\Call{allIds}{}$ in Zeit $\O(\abs{I} + 1)$ unterstützt, mit $n \cdot (1 + 2 \cdot \ceil{\log_2 n})$ Bits realisieren.
\end{lem}

\begin{proof}
  Mit einem $n$-Bit-Array merken wir uns für jede Zahl $i \in [n]$, ob sie in $I$ enthalten ist.
  Wir verwenden außerdem zwei Arrays $A$ und $B$ bestehend aus je $n$ Einträgen à $\ceil{\log_2 n}$ Bits und einen Zähler $k \in \{ 0, \ldots, n \}$, welcher die Größe von~$I$ speichert.
  %Das Array~$A$ verwenden wir als Liste von Elementen aus $I$
  In~$A$ sind die ersten~$k$ Einträge beliebige Elemente aus~$I$.
  Das Array~$B$ wird verwendet, um für jedes $i \in [n]$ zu merken, an welcher Stelle es in~$A$ vorkommt (falls überhaupt $i \in I$ gilt).
  Anders ausgedrückt:
  \[
    \fa{i \in I} A[B[i]] = i, \quad
    \fa{0 \leq j < k = \abs{I}} B[A[j]] = j.
  \]
  Folgende Invariante ermöglicht zu prüfen, ob $i \in I$:
  \[
    \fa{i \in [n]} \quad i \in I \iff 0 \leq B[i] < k \wedge A[B[i]] = i.
    \qedhere
  \]
\end{proof}

\begin{technik}
  Sei $f : A \to B$ eine Funktion, $A$ endlich.
  Wenn $f$ in einem Programm häufig aufgerufen wird, so kann es günstiger sein, die Werte von $f$ im Voraus (beim Kompilieren oder Initialisieren) zu berechnen und im einem Array, der \emph{Lookup-Table}, zu speichern.
  Werte können dann einfach nachgeschlagen werden. \\
  Die Voraussetzung dafür ist, dass $\abs{A}$ relativ klein ist und die Werte von~$f$ wenig Speicher benötigen. \\
  Genauer: Angenommen, für einen Parameter $n \in \N$ gilt, dass
  \begin{itemize}
    \item Elemente von $A$ binär mit $m \leq \nicefrac{1}{2} \log_2 n$ Bits repräsentiert werden können (folglich $\abs{A} \leq 2^{\nicefrac{1}{2} \log_2 n} = \sqrt{n}$),
    \item $f$ in polynomieller Zeit in $m$ auf binär repräsentierten Elementen von $A$ ausgewertet werden kann,
    \item die Werte von $f$ polynomiell in $m$ viel Platz benötigen.
  \end{itemize}
  Dann kann eine Lookup-Table in $\sqrt{n} (\log_2 n)^C$ Zeit berechnet und in $\sqrt{n} (\log_2 n)^D$ Bit gespeichert werden. \\
  Durch Verwendung dieser Technik kann man Funktionen mit kleinen Argumenten als in konstanter Zeit auswertbar betrachten.
\end{technik}

\begin{bspe}
  Lookup-Tables können verwendet werden, um folgende Funktionen zu berechnen:
  \begin{itemize}
    \miniitem{0.3 \linewidth}{Sinus (approx.)}
    \miniitem{0.68 \linewidth}{Anzahl/Position der 1-Bits in einem Byte}
  \end{itemize}
\end{bspe}

% 6.2
\begin{lem}[CD\textsubscript{2}]
  Es gibt ein Choice-Dictionary, welches $\O(n)$ Platz benötigt, die ersten vier Operationen in konstanter Zeit und $\Call{allIds}{}$ in Zeit $\O(\abs{I} + 1)$ unterstützt.
  % Initialisierung in $\O(n)$ Zeit
\end{lem}

\begin{proof}
  Wir merken uns in einem Array~$V$ von~$n$ Bit, welche Elemente in~$I$ enthalten sind.
  Wir teilen die Menge~$[n]$ in $\O(\nicefrac{n}{\log n})$ Gruppen, \dh{} disjunkte zusammenhängende Teilmengen, zu je $\leq \nicefrac{1}{2} \log_2 n$ ganzen Zahlen auf.
  Sei~$I^{*}$ die Menge aller Gruppen, die Elemente aus~$I$ enthalten.
  Da die Zahlen jeder Gruppe nur höchstens zwei Maschinenworte im Bitarray~$V$ umfassen, können wir in kon- stanter Zeit prüfen, ob eine Gruppe Zahlen in~$I$ enthält, also ob die Gruppe in~$I^{*}$ liegt.
  Um schnell Gruppen aus $I^{*}$ zu finden, verwenden wir zwei Arrays~$A$ und~$B$ zu je $\O(\nicefrac{n}{\log n} \cdot \log(\nicefrac{n}{\log n})) = \O(n)$ Bits wie im Beweis von~CD\textsubscript{1}.
  Wir implementieren $\Call{someId}{}$ wie folgt: Zunächst ist $G \coloneqq A[0]$ eine nichtleere Gruppe. Sei $q$ das zugehörige Wort in~$V$. Sei~$f$ eine Funktion, welche für ein Maschinenwort den Index eines 1-Bits im Wort zurückgibt. Dann ist $(\min G) + f(q) \in I$.
  Wir benutzen eine Lookup-Table, um $f$ effizient auszuwerten.
\end{proof}

% 6.3
\begin{thm}[CD\textsubscript{3}]
  Es gibt ein Choice-Dictionary, welches $n + \O(\nicefrac{n}{\log n})$ Bits an Platz benötigt, die ersten vier Operationen in konstanter Zeit und $\Call{allIds}{}$ in Zeit $\O(\abs{I} + 1)$ unterstützt.
\end{thm}

\begin{proof}
  Wir verwenden diesselbe Konstr. wie im Beweis von~CD\textsubscript{2}, speziell das Bitarray $V$ mit $n$ Bits und die Einteilung in Gruppen.
  Um $I^{*} \subseteq [m]$ mit $m = \O(\nicefrac{m}{\log n})$ zu verwalten, gebrauchen wir das Choice-Dictionary von~CD\textsubscript{2}, welches nur~$\O(m)$ Bits benötigt.
\end{proof}

% 6.4
\begin{kor}
  Man kann die Zshgskomponenten eines ungerichteten Graphen in Zeit $\O(n + m)$ mit $2 n + \O(\nicefrac{n}{\log n})$ Bits berechnen.
\end{kor}

\begin{bem}
  Man benötigt sogar nur $c n + \O(1)$ Bits für belieb. $c > \log_2 3$.
\end{bem}

% Vorlesung vom 25.11.2015

% §6.2. A Lower Bound for Choice Dictionaries
\subsection{Eine untere Schranke für Choice Dictionaries}

\begin{defn}
  Ein Choice-Dictionary $D$ heißt \emph{systematisch}, falls es (nach der Initialisierung von $D$) $n$ von $D$ verwaltete Bits $z_1, \ldots, z_n$ gibt, sodass $z_i = 1 \iff i \in I$ für alle $i = 1, \ldots, n$ ab dem ersten Schreiben von $z_i$ durch $D$ gilt.
\end{defn}

\begin{defn}
  \begin{itemize}
    \item Ein \emph{Rot-Blau-Baum} ist ein Binärbaum, dessen inneren Knoten alle entweder rot oder blau gefärbt sind.
    \item Die \emph{blaue Tiefe} eines Blattes ist die Zahl der blauen Vorfahren.
    \item Die \emph{rechts-rote (rr) Tiefe} eines Blattes ist die Anzahl der Vorfahren, die rechtes Kind eines roten Knotens sind.
    \item Ein \emph{$(d, r, s)$-Baum} ist ein Rot-Blau-Baum, in dem jedes Blatt Tiefe $= d$, blaue Tiefe $\leq s$ und rechts-rote Tiefe $\leq r$ besitzt.
  \end{itemize}
\end{defn}

\begin{nota}
  $N(d, r, s) \coloneqq$ max. Anzahl Blätter eines $(d, r, s)$-Baums
\end{nota}

\begin{lem}
  $N(d, r, s) =$
  \[
    \begin{cases}
      0 & \text{wenn $\min \{ d, r, s \} < 0$,} \\
      1 & \text{wenn $d = 0$ und $r, s \geq 0$,} \\
      \max \left\{
        \begin{array}{l}
          2 N(d-1, r, s-1), \\
          N(d{-}1, r, s) + N(d{-}1, r{-}1, s)
        \end{array}
      \right\} & \text{wenn $d > 0$ und $r, s \geq 0$.}
    \end{cases}
  \]
\end{lem}

\begin{lem}
  %Für alle $d, r, s \in \Z$ gilt
  $N(d, r, s) \leq 2^{s'} \binom{d - s' + r}{r}$ \enspace
  wobei $s' \coloneqq \min \{ d, s \}$
\end{lem}

\begin{thm}
  Seien $n, s, t \in \N$.
  Sei $D$ ein systematisches Choice-Dictionary, das nach dem Initialisieren neben $z_1, \ldots, z_n$ weitere~$s$ Bits benutzt.
  Angenommen, für $0 \leq r \leq n$ gibt es eine Berechnung $C_r$, die alle Teilmengen $A \subset I$ mit $\abs{A} = r$ unterscheiden kann und dabei $\leq rt$ Bits der internen Repräsentation von $D$ liest.
  Dann gilt $st \geq \tfrac{n}{2}$.
\end{thm}

\begin{kor}
  Seien $n, s \in \N$ und $D$ ein systematisches Choice-Dictionary, welches nach dem Initialisieren $n + s$ Bits an Speicher belegt. \\
  Seien $t_{\text{choice}}$ und $t_{\text{delete}}$ die maximalen Anzahlen an Bits, die bei einer \textit{choice}- bzw. \textit{delete}-Operation gelesen werden. \\
  Dann gilt $s (t_{\text{choice}} + t_{\text{delete}}) \leq \tfrac{n}{2}$.
\end{kor}

% Vorlesung vom 2.12.2015

% §6.3. Breadth-First-Search
\subsection{Breitensuche}

\begin{defn}
  Sei ein Graph gegeben.
  Eine allgemeine Suche durch den Graphen geht wie folgt:
  Es gibt weiße, graue und schwarze Knoten, explorierte und unexplorierte Kanten.
  Zunächst sind alle Knoten weiß, bis auf einen grauen Startknoten und alle Kanten unexploriert.
  Solange es noch einen grauen Knoten $u$ gibt, wählen wir einen solchen aus.
  Hat $u$ keine unexplorierten Kanten, so färben wir $u$ schwarz.
  Wenn $u$ noch eine unexplorierte Kante $(u, v)$ hat, so \textit{explorieren} wir $(u, v)$, \dh{} falls $v$ weiß ist, so färben wir $v$ grau und rufen eine Benutzerfunktion mit $(u, v)$ auf.
\end{defn}

\begin{bem}
  Verschiedene Suchstrategien unterscheiden sich darin, wie $u$ gewählt wird.
\end{bem}

\begin{defn}[\emph{Breitensuche}]
  Drei Varianten:
  %\setlength{\leftmargin}{20pt}
  \begin{enumerate}[label=\Alph*.,leftmargin=2em]
    \item $u$ ist der älteste graue Knoten
    \item Der graue Knoten $u$ aus der vorherigen Iteration wird weiterverwendet, falls er noch unexplorierte Kanten besitzt.
    Andernfalls ist $u$ wie in C.
    \item $u$ ist ein grauer Knoten mit minimaler Distanz vom Startknoten.
  \end{enumerate}
\end{defn}

% 6.11
\begin{thm}
  Sei ein Graph mit $n$ Knoten und $m$ Kanten gegeben, $r$ ein Startknoten, von dem aus alle anderen Knoten erreichbar sind.
  Die Variante B der Breitensuche kann in $O(n + m)$ Zeit mit $O(n)$ Bits an Speicher durchgeführt werden.
\end{thm}

\begin{idee}
  Verwende zwei Choice-Dictionaries, um graue Knoten zu speichern: Eines für alle Knoten in Entfernung $d$, eines für alle Knoten in Entfernung $d + 1$ vom Startknoten.
\end{idee}

\end{document}