Chomksy, Schema F

2 files changed, 196 insertions, 372 deletions

diff --git a/Makefile b/Makefile
index 34d3efe..9066144 100644
--- a/Makefile
+++ b/Makefile
@@ -1,10 +1,10 @@
 MAIN = sheet
-FLAGS = -pdf
+FLAGS = -pdf -lualatex
 
-dev:
-	latexmk $(FLAGS) -pvc $(MAIN)
 all: 
 	latexmk $(FLAGS) $(MAIN)
+dev:
+	latexmk $(FLAGS) -pvc $(MAIN)
 clean: 
 	latexmk -C
 
diff --git a/sheet.tex b/sheet.tex
index e611508..2521c6e 100644
--- a/sheet.tex
+++ b/sheet.tex
@@ -10,10 +10,14 @@
 ]{geometry}
 \usepackage{amsmath}
 \usepackage{amsfonts}
+\usepackage{makecell}
 \usepackage{multicol}
 \usepackage[noend]{algorithm2e}
 \usepackage[utf8]{inputenc}
 \usepackage{fancyhdr}
+\usepackage{tikz}
+\usetikzlibrary{arrows,automata,positioning, graphs, graphdrawing}
+\usegdlibrary {trees} 
 \usepackage{hyperref}
 \hypersetup{
     colorlinks=true,
@@ -33,397 +37,217 @@
 \fancyhead[R]{Gero Beckmann - \url{https://github.com/Geronymos/}}
 \fancyfoot{}
 \fancyfoot[R]{\thepage}
-\section{Laufzeit}
+\newenvironment{definition}[1]{\noindent\textbf{#1:}}{}
+\section{Chomsky-Hierarchie}
 \hspace*{-.5cm}
-\begin{tabular}{ l l l l }
-    Notations & Asymptotischer Vergleich & Formale Definition & Grenzen \\
-    $f(n) \in \omega(g(n))$& 
-    $f(n)$ wächst schneller als $g(n)$ & 
-    $\forall c \exists n_0 \forall n > n_0 f(n) > c \cdot g(n)$ &
-    $$$\lim\sup\limits_{n \rightarrow \infty}\frac{f}{g} = \infty$$$ \\
-
-    $f(n) \in \Omega(g(n))$ &
-    $f(n)$ wächst min. so schnell wie $g(n)$ & 
-    $\exists c \exists n_0 \forall n > n_0 c \cdot f(n) \leq g(n)$ &
-    $$$0 < \liminf\limits_{n \rightarrow \infty}\frac{f}{g} \leq \infty$$$ \\
-
-    \( f(n) \in \Theta(g(n)) \) &
-    $f(n)$ und $g(n)$ wachsen gleich schnell & 
-    $f(n) \in \mathcal{O}(g(n)) \wedge f(n) \in \Omega(g(n))$ &
-    $$$0 < \lim\limits_{n \rightarrow \infty}\frac{f}{g} < \infty$$$ \\
-
-    \( f(n) \in \mathcal{O}(g(n)) \) &
-    $f(n)$ wächst max. so schnell wie $g(n)$ & 
-    $\exists c \exists n_0 \forall n > n_0 f(n) \leq c \cdot g(n)$ &
-    $$$0 \leq \limsup\limits_{n \rightarrow \infty}\frac{f}{g} < \infty$$$ \\
-
-    \( f(n) \in o(g(n)) \) &
-    $f(n)$ wächst langsamer als $g(n)$ & 
-    $\forall c \exists n_0 \forall n > n_0 c \cdot f(n) < g(n)$ &
-    $$$\lim\limits_{n \rightarrow \infty} \frac{f}{g} = \infty$$$ \\
-
-\end{tabular}
-
-\subsection{Vergleich}
-\begin{tabular}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
-    $1$ & $\log^*n$ & $\log n$ & $\log^2n$ & $\sqrt[3]{n}$ & 
-    $\sqrt{n}$ & $n$ & $n^2$ & $n^3$ & $n^{\log n}$ & 
-    $2^{\sqrt{n}}$ & $2^n$ & $3^n$ & $4^n$ & $n!$ & $2^{n^2}$
+\begin{tabular}{ l l l l l }
+  Chomsky-Typ & Wortproblem & Definition & Bsp & Maschinenmodell \\
+
+  Typ 0 & 
+  semi-entscheidbar &
+  \makecell{$G = (\Sigma, V, S, R)$ \\ $R beliebig$ }&
+  universelle Sprache &
+  NTM/DTM akzeptiert L \\
+
+  Typ 1 & 
+  NP-Schwer &
+  \makecell{$u \rightarrow v, |u| \leq |v|$ \\ $u \in V^+, S \notin V$ \\ $S \rightarrow \epsilon$ } &
+  $L = \{ a^ib^ic^i | i \leq 1 \}$ &
+  \makecell{NTM mit Platzbedarf n \\ erkennt Wörter der Länge n in L \\ $\Rightarrow NTAPE(n)$ } \\
+
+  Typ 2 & 
+  polynomiell & 
+  \makecell{$A \rightarrow v, A \in V$ \\ $v beliebig$} &
+  $L = \{ a^ib^i | i \leq 1\}$ &
+  CYK-Alg. erkennt L in polynom. Zeit, Chomsky-NF, NPDA \\
+
+  Typ 3 &
+  linear &
+  \makecell{$A \rightarrow v, A \in V$ \\ $V \in \epsilon \cup \Sigma \cdot V$} &
+  $L = \{ a^i | i \leq 1 \}$ &
+  NEA/DEA erkennt L \\
 \end{tabular}
 
-\begin{multicols}{3}
-
-    \subsubsection*{Transitivität}
-
-    $f_1(n) \in \mathcal{O}(f_2(n)) \wedge f_2(n) \in\mathcal{O}(f_3(n))$ \\
-    $\Rightarrow f_1(n) \in \mathcal{O}(f_3(n))$
-
-    \subsubsection*{Summen}
-
-    $f_1(n) \in \mathcal{O}f_3(n)) \wedge f_2(n) \in \mathcal{O}(f_3(n))$ \\
-    $\Rightarrow f_1(n) + f_2(n) \in \mathcal{O}(f_3(n))$
-
-    \subsubsection*{Produkte}
-
-    $f_1(n) \in \mathcal{O}(g_1(n)) \wedge f_2(n) \in \mathcal{O}(g_2(n))$ \\
-    $\Rightarrow f_1(n) \cdot f_2(n) \in \mathcal{O}(g_1(n) \cdot g_2(n))$
-
-
-    \columnbreak
-
-    \subsection{Master-Theorem}
-
-    Sei $T(n) = a \cdot T(\frac{n}{b}) + f(n)$ mit $f(n) \in \Theta(n^c)$ und i
-    $T(1) \in \Theta(1)$. Dann gilt
-    $
-    T(n) \in \begin{cases}
-        \Theta(n^c) &\text{wenn } a < b^c, \\
-        \Theta(n^c \log n) &\text{wenn } a = b^c, \\
-        \Theta(n^{\log_b(a)}) &\text{wenn } a > b^c.
-    \end{cases}
-    $ 
-
-    \subsubsection{Monome}
-
-    \begin{itemize}
-        \item $a \leq b \Rightarrow n^a \in \mathcal{O}(n^b)$
-        \item $n^a \in \Theta(n^b) \Leftrightarrow a = b$
-        \item $\sum_{v \in V}deg(v) = \Theta(m)$
-        \item $\forall n \in \mathbb{N}: \sum^n_{k=0}k = \frac{n(n+1)}{2}$
-        \item $
-            \sum^b_{i=a}c^i \in \begin{cases}
-                \Theta(c^a) &\text{wenn } c < 1, \\
-                \Theta(c^b) &\text{wenn } c > 1, \\
-                \Theta(b-a) &\text{wenn } c = 1.
-            \end{cases}
-            $
-        \item $\log(ab) = \log(a) + \log(b)$
-        \item $\log(\frac{a}{b}) = \log(a) - \log(b)$
-        \item $a^{\log_a(b)} = b$
-        \item $a^x = e^{ln(a) \cdot x}$
-        \item $\log(a^b) = b \cdot \log(a)$
-        \item $\log_b(n) = \frac{\log_a(n)}{\log_a(b)}$
-    \end{itemize}
-
-    %\subsubsection{Konstante Faktoren}
-    %
-    %$a \cdot f(n) \in \Theta(f(n))$
+\subsection{Automaten}
+DEA $A = (Q, \Sigma, \delta: Q \times \Sigma \rightarrow Q, s \in Q, F \subseteq Q)$ \\
+NEA $A = (Q, \Sigma, \delta: Q \times (\Sigma \cup \{ \epsilon \} \rightarrow 2^Q, s \in Q, F \subseteq Q)$
+NPDA \\
+DPDA \\
+DTM \\
+NTM \\
 
+\subsection{Pumping-Lemma}
 
+\begin{multicols}{2}
+Erfüllt: 
+\begin{itemize}
+  \item["$\exists$"] Wähle $n = 2$
+  \item["$\forall$"] Betrachte beliebiges $w \in L$ mit $|w| > 2$ 
+  \item["$\exists$"] Wähle zerlegung $w = uvx$ mit $u = \epsilon, v = aa, x=a^{2(j-1)}$
+  \item["$\forall$"] Für alle $i \in \mathbb{N}_0: uv^ix = a^{2i}a^2(j-1) = a^{2(i+j-1)} \in L$ 
+\end{itemize}
+Widerlegen: 
+\begin{itemize}
+  \item["$\exists$"] Wähle $n = 2$
+  \item["$\forall$"] Betrachte beliebiges $w \in L$ mit $|w| > 2$ 
+  \item["$\exists$"] Wähle zerlegung $w = uvx$ mit $u = \epsilon, v = aa, x=a^{2(j-1)}$
+  \item["$\forall$"] Für alle $i \in \mathbb{N}_0: uv^ix = a^{2i}a^2(j-1) = a^{2(i+j-1)} \in L$ 
+\end{itemize}
 \end{multicols}
 
-\begin{minipage}{0.7\textwidth} 
-
-    \section{Sortieren}
-
-    \begin{tabular}[t]{c || c | c | c | c}
-        Algorithmus & best case & average & worst & Stabilität \\
-        \hline
-        Insertion-Sort & 
-        $\mathcal{O}(n)$ & $\mathcal{O}(n^2)$ & $\mathcal{O}(n^2)$ & stabil\\
-        Bubble-Sort & 
-        $\mathcal{O}(n)$ & $\mathcal{O}(n^2)$ & $\mathcal{O}(n^2)$ & stabil\\
-        Merge-Sort & 
-        $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & stabil\\
-        Quick-Sort & 
-        $\mathcal{O}(n \log n)$ & $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & i.A.  nicht stabil\\
-        Heap-Sort & 
-        $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & $\mathcal{O}(n\log n)$ & nicht stabil\\
-        \hline
-        Bucket-Sort & 
-        $\Theta(n+m)$ & $\Theta(n+m)$ & $\Theta(n+m)$ & 
-        stabil $e \in [0, m)$\\
-        Radix-Sort & 
-        $\Theta(c \cdot n)$ & $\Theta(c\cdot n)$ & $\Theta(c\cdot n)$ & 
-        stabil $e \in [0, n^c)$\\
-    \end{tabular}
-\end{minipage}
-\hfill
-\begin{minipage}{0.3\textwidth} 
-    \subsection{Heaps}
-
-    \begin{tabular}[t]{c || c}
-        Bin.-Heap & Laufzeit \\
-        \hline
-        push(x) & $\mathcal{O}(\log n)$ \\
-        popMin() & $\mathcal{O}(\log n)$ \\
-        decPrio(x, x') & $\mathcal{O}(\log n)$ \\
-        build([$\mathbb{N}$; n]) & $\mathcal{O}(n)$
-    \end{tabular}
-
-    \begin{itemize}
-        \item linkes Kind: $2v + 1$
-        \item rechts Kind: $2v + 2$
-        \item Elternknoten: $ \lfloor \frac{v - 1}{2} \rfloor $
-    \end{itemize}
-
-\end{minipage}
-
-
 \begin{multicols}{2}
+Potenzmengenkonstuktion NEA $\rightarrow$ DEA
+
+\begin{tabular}{c | c | c}
+  Zustand & a & b \\
+  \hline
+  $\{\underline{s}\}$ & $\{s, q_1\}$ & $\{f\}$ \\
+  $\{\underline{s}, q_1\}$ & $\{s, q_1\}$ & $\{f, q_2\}$ \\
+  $\{f\}$ & $\{f\}$ & $\{f\}$ \\
+  $\{f, q_2\}$ & $\{f\}$ & $\{f, q_1, q_2\}$ \\
+  $\{f, \underline{s}\}$ & $\{f, s, q_1\}$ & $\{f\}$ \\
+  $\{f, \underline{s}, q_1\}$ & $\{f, s, q_1\}$ & $\{f, q_2\}$ \\
+\end{tabular}
 
-    \section{Datenstrukturen}
-
-    \subsection{Listen}
-
-    \begin{tabular}{c || c | c | c || c}
-        Operation & DLL & SLL & Array & Erklärung(*) \\
-        \hline
-        first & 1 & 1 & 1 & \\
-        last & 1 & 1 & 1 & \\ 
-        insert & 1 & 1* & n & nur insertAfter \\
-        remove & 1 & 1* & n & nur removeAfter \\
-        pushBack & 1 & 1 & 1* & amortisiert \\
-        pushFront & 1 & 1 & n & \\
-        popBack & 1 & n & 1* & amortisiert \\
-        popFront & 1 & 1 & n & \\
-        concat & 1 & 1 & n & \\
-        splice & 1 & 1 & n \\
-        findNext & n & n & n 
-
-    \end{tabular}
-
-    \subsection{Hash-Tabelle}
-    $\mathcal{H}$ heißt \textbf{universell}, wenn für ein zufälliges gewähltes
-    $h \in \mathcal{H}$ gilt: $U \rightarrow \{0, ..., m-1\}$ \\
-    $\forall k, l \in U, k \neq l: Pr[h(k) = h(l)] = \frac{1}{m}$ \\
-    $h_{a,b}(k) = ((a\cdot k + b) \mod p) \mod m$
-
-    \subsection{Graphen}
-
-    \begin{tabular}{c || c}
-        Algorithmus & Laufzeit \\
-        \hline
-        BFS/DFS & $\Theta(n+m)$\\
-        topoSort & $\Theta(n)$\\
-        Kruskal & $\Theta(m \log n)$\\
-        Prim & $\Theta((n+m)\log n)$ \\
-        Dijksta & $\Theta((n + m) \log n)$\\
-        Bellmann-Ford & $\Theta(nm)$\\
-        Floyd-Warshall & $\Theta(n^3)$ \\
-    \end{tabular}
-
+\begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto]
+
+  \node[state,initial,accepting]  (S)                   {$S$};
+  \node[state]                    (q_1) [right of=S]    {$q_1$};
+  \node[state]                    (q_2) [right of=q_1]  {$q_2$};
+  \node[state]                    (f)   [below of=q_1] {$f$};
+
+  \path[->] 
+    (S) edge [loop above] node {a} ()
+    (S) edge   node [below] {a} (q_1)
+    (S) edge              node [left] {b} (f)
+    (q_1) edge [bend right] node [above] {a} (S)
+    (q_1) edge              node [below] {b} (q_2)
+    (q_2) edge [bend right] node [above] {b} (q_1)
+    (q_2) edge [loop right] node {b} ()
+    (q_2) edge              node {a} (f)
+    (f) edge [loop left] node {a,b} ()
+  ;
+
+\end{tikzpicture}
 \end{multicols}
 
-\newpage
-
 \begin{multicols}{2}
+Entfernen von $\epsilon$-Übergängen
+
+\begin{tabular}{c | c | c}
+  Zustand & a & b \\
+  \hline
+  $S$ & $q_1$ & $S, q_1, q_2, q_3$ \\
+  $q_1$ & $q_2, q_3$ & $q_3$ \\
+  $q_2$ & $q_1$ & $S, q_2, q_3$ \\
+  $q_3$ & $q_1$ & $S, q_2, q_3$ \\
+\end{tabular}
 
-    \subsubsection{DFS}
-
-    \begin{tabular}{c || c | c}
-        Kante & DFS & FIN \\
-        \hline
-        Vorkante & klein $\rightarrow$ groß & groß $\rightarrow$ klein \\
-        Rückkante & groß $\rightarrow$ klein & klein $\rightarrow$ groß \\
-        Querkante & groß $\rightarrow$ klein & groß $\rightarrow$ klein \\
-        Baumkante & klein $\rightarrow$ groß & groß $\rightarrow$ klein \\
-    \end{tabular}
-    \subsection{Bäume}
-    \subsubsection{Heap}
-    Priorität eines Knotens $\geq (\leq)$ Priorität der Kinder.
-    \textbf{BubbleUp}, \textbf{SinkDown}. \textbf{Build} mit \textbf{sinkDown} 
-    beginnend mit letztem Knoten der vorletzten Ebene weiter nach oben.
-    \textbf{decPrio} entweder updaten, Eigenschaft wiederherstellen; löschen,
-    mit neuer Prio einfügen oder Lazy Evaluation.
-
-    \subsubsection{(ab)-Baum}
-    Balanciert. \textbf{find}, \textbf{insert}, \textbf{remove} in 
-    $\Theta(log n)$. Zu wenig Kinder: \textbf{rebalance} / \textbf{fuse}. 
-    Zu viele Kinder: \textbf{split}. 
-
-    Linker Teilbaum $\leq$ Schlüssel k $<$ rechter Teilbaum
+\begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto]
+
+  \node[state,initial]   (S)                   {$S$};
+  \node[state,accepting] (q_1) [right of=S]    {$q_1$};
+  \node[state,accepting] (q_2) [below of=q_1]  {$q_2$};
+  \node[state]           (q_3) [below of=S]    {$q_3$};
+
+  \path[->] 
+    (S) edge node {b} (q_1)
+    (S) edge node [above left] {$\epsilon$} (q_2)
+    (q_1) edge node {a} (q_2)
+    (q_1) edge [bend left] node [above right] {b} (q_3)
+    (q_2) edge node {\epsilon} (q_3)
+    (q_3) edge node [below left] {a} (q_1)
+    (q_3) edge node {b} (S)
+    (q_3) edge [loop left] node {b} ()
+  ;
+
+\end{tikzpicture}
+\end{multicols}
 
-    Unendlich-Trick, für Invarianten.  
+Minimierung von Automaten
+\begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto]
+
+  \node[state,initial]  (S)                   {$S$};
+  \node[state]          (p) [right of=S]    {$p$};
+  \node[state]          (q) [right of=p]    {$q$};
+  \node[state]          (t) [below of=p]    {$t$};
+  \node[state,accepting]          (r) [below of=q]    {$r$};
+  \node[state]          (v) [below of=t]    {$v$};
+  \node[state]          (u) [below of=r]    {$u$};
+
+  \path[->] 
+    (S) edge [loop above] node {0} ()
+    (S) edge  node {1} (p)
+    (p) edge [loop above] node {1} ()
+    (p) edge  node {0} (q)
+    (q) edge [bend left] node {0} (S)
+    (q) edge  node {1} (r)
+    (t) edge  node [right] {0} (S)
+    (t) edge [bend right] node {1} (r)
+    (r) edge [bend right] node [above] {0} (t)
+    (r) edge  node {1} (u)
+    (v) edge  node {0} (S)
+    (v) edge  node[left] {1} (r)
+    (u) edge  node {0} (v)
+    (u) edge [loop right] node {1} ()
+  ;
+
+\end{tikzpicture}
+
+\begin{tikzpicture}[initial text=,shorten >=1pt,node distance=2cm,on grid,auto]
+
+  \node[state,initial]  (S)  {$[S]$};
+  \node[state]          (p) [right of=S] {$[p]$};
+  \node[state]          (q) [right of=p] {$[q]$};
+  \node[state,accepting] (r) [right of=q] {$[r]$};
+
+  \path[->] 
+    (S) edge [loop above] node {0} ()
+    (S) edge  node {1} (p)
+    (p) edge [loop above] node {1} (p)
+    (p) edge  node {0} (q)
+    (q) edge[bend left] node {0} (S)
+    (q) edge node {1} (r)
+    (r) edge[bend right] node [above] {1} (p)
+  ;
+
+\end{tikzpicture}
+
+
+
+\begin{tikzpicture} [binary tree layout]
+  \node[align=center] (1) {s,p,q,r,t,a,v \\ $\epsilon$ trennt}
+  child { 
+    node {r}
+  }
+  child { node[align=center] {s,p,q,t,u,v \\ 1 trennt}
+    child { node[align=center] {s,p,u \\ 0 trennt}
+      child { node {s} }
+      child { node {p,u} }
+    }
+    child{
+      node {q,t,v}
+    }
+  };
+\end{tikzpicture}
 
-    \subsection{Union-Find}
-    Rang: höhe des Baums, damit ist die Höhe h mind. $2^h$ Knoten, h $\in
-    \mathcal{O}(\log n)$. 
-    Union hängt niedrigen Baum an höherrängigen Baum. Pfadkompression hängt alle
-    Knoten bei einem \textbf{find} an die Wurzel. 
+\subsection{Nerode-Relation}
 
+\subsection{Chomsky-NF}
 
-    \columnbreak
-    \section{Amortisierte Analyse}
+\section{NP-Vollständigkeit}
 
-    \subsection{Aggregation}
-    Summiere die Kosten für alle Operationen. Teile Gesamtkkosten durch Anzahl
-    Operationen. 
+\section{Kellerautomaten}
 
-    \subsection{Charging}
-    Verteile Kosten-Tokens von teuren zu günstigen Operationen (Charging). Zeige:
-    jede Operation hat am Ende nur wenige Tokens. 
+\subsection{$4COLOR \in NP$}
 
-    \subsection{Konto}
-    Günstige Operationen bezahlen mehr als sie tatsächlich kosten (ins Konto
-    einzahlen). Teure Operationen bezahlen tatsächliche Kosten zum Teil mit
-    Guthaben aus dem Konto. \textbf{Beachte: Konto darf nie negativ sein!}
+\subsection{$3COLOR \propto 4COLOR$}
 
-    \subsection{Potential (Umgekehrte Kontomethode)}
-    Definiere Kontostand abhängig vom Zustand der Datenstruktur
-    (Potentialfunktion)
+\subsubsection{Transformation}
+\subsubsection{Äquivalenz/Korrektheit}
 
-    amortisierten Kosten = tatsächliche Kosten 
-    $+ \Phi(S_\text{nach}) -\Phi(S_\text{vor})$
+\section{Approximationsalgorithmen}
 
-\end{multicols}
+\section{Huffman-Kodierung}
 
-\section{Pseudocode}
-\scriptsize
-\begin{minipage}{.25\linewidth}
-    \begin{algorithm}[H]
-        DFS(Graph G, Node v) \\
-        mark v \\
-        dfs[v] := dfsCounter++ \\
-        low[v] := dfs[v] \\
-        \For{u $\in$ N(v)}{
-            \eIf{not marked u}{
-                dist[u] := dist[v] + 1 \\
-                par[u] := v \\
-                DFS(G, u) \\
-                low[v] := min(low[v], low[u]) \\
-            }{low[v] := min(low[v], dfs[u])}
-        }
-        fin[v] := fin++ \\
-    \end{algorithm}
-\end{minipage}
-\begin{minipage}{.25\linewidth}
-    \begin{algorithm}[H]
-        topoSort(Graph G) \\
-        fin := [$\infty$; n] \\
-        curr := 0 \\
-        \For{Node v in V}{
-            \If{v is colored}{DFS(G,v)}
-        }
-        return V sorted by decreasing fin \\
-    \end{algorithm}
-\end{minipage}
-\begin{minipage}{.25\linewidth}
-    \begin{algorithm}[H]
-        Kruskal(Graph G) \\
-        U := Union-Find(G.v) \\
-        PriorityQueue Q := empty \\
-        \For{Edge e in E}{Q.push(e, len(e))}
-        \While{Q $\neq \emptyset$}{
-            e := Q.popMin() \\
-            \If{U.find(v) $\neq$ U.find(u)}{
-                L.add(e) \\
-                U.union(v, u) \\
-            }
-        }
-    \end{algorithm}
-\end{minipage}
-\begin{minipage}{.25\linewidth}
-    \begin{algorithm}[H]
-        Prim(Graph G) \\
-        Priority Queue Q := empty \\
-        p := [0; n] \\
-        \For{Node v in V}{
-            Q.push(v, $\infty$) \\
-        }
-        \While{Q $\neq \emptyset$}{
-            u := Q.popMin() \\
-            \For{Node v in N(u)}{
-                \If{v $\in$ Q $\wedge$ (len(u, v) $<$ Q.prio(v))}{
-                    p[v] = u \\
-                    Q.decPrio(v, len(u, v) \\
-                }
-            }
-        }
-    \end{algorithm}
-\end{minipage}
-\begin{minipage}{.25\linewidth}
-    \begin{algorithm}[H]
-        BFS(Graph G, Start s, Goal z) \\
-        Queue Q := empty queue \\
-        Q.push(s) \\
-        s.layer = 0 \\
-        \While{Q $\neq \emptyset$}{
-            u := Q.pop() \\
-            \For{Node v in N(u)}{
-                \If{v.layer = $-\infty$}{
-                    Q.push(v) \\
-                    v.layer = u.layer + 1
-                }
-                \If{v = z}{
-                    return z.layer
-                }
-            }
-        }
-    \end{algorithm}
-\end{minipage}
-\begin{minipage}{.25\linewidth}
-    \begin{algorithm}[H]
-        Dijkstra(Graph G, Node s) \\
-        d := [$\infty$; n] \\
-        d[s] := 0 \\
-        PriorityQueue Q := empty priority queue \\
-        \For{Node v in V}{
-            Q.push(v, d[v])
-        }
-        \While{Q $\neq \emptyset$}{
-            u := Q.popMin() \\
-            \For{Node v in N(u)}{
-                \If{d[v] $>$ d[u] + len(u, v)}{
-                    d[v] := d[u] + len(u, v) \\
-                    Q.decPrio(v, d[v]) \\
-                }
-            }
-        }
-    \end{algorithm} 
-\end{minipage}
-\begin{minipage}{.25\linewidth}
-    \begin{algorithm}[H]
-        BellManFord(Graph G, Node s) \\
-        d := [$\infty$, n] \\
-        d[s] := 0 \\
-        \For{n-1 iterations}{
-            \For{(u, v) $\in$ E}{
-                \If{d[v] $>$ d[u] + len(u, v)}{
-                    d[v] := d[u] + len(u, v)
-                }
-            }
-        }
-        \For{(u, v) $\in$ E}{
-            \If{d[v] $>$ d[u] + len(u, v)}{
-                return negative cycle
-            }
-        }
-        return d
-    \end{algorithm}
-\end{minipage}
-\begin{minipage}{.25\linewidth}
-    \begin{algorithm}[H]
-        FloydWarshall(Graph G) \\
-        D := [$\infty$, n $\times$ n] \\
-        \For{(u, v) $\in$ E}{D[u][v] := len(u, v)}
-        \For{v $\in$ V}{D[v][v] := 0}
-        \For{i $\in 1,...,n$}{
-            \For{(u,v) $\in V \times V$}{
-                D[u][v] := min(D[u][v], D[u][$v_i$] + D[$v_i$][v]) \\
-            }
-        }
-        return D
-    \end{algorithm}
-\end{minipage}
 \end{document}