\documentclass[a4paper,10pt]{scrartcl}
%\documentclass[a4paper,10pt]{scrreprt}
\setlength{\topmargin}{-2.5cm}
\setlength{\oddsidemargin}{-1.5cm}
\setlength{\evensidemargin}{-1.5cm}
\setlength{\textwidth}{19cm}
\setlength{\textheight}{26.5cm}

\usepackage[active]{srcltx}
\usepackage[german]{babel}
\usepackage[utf8]{inputenc}
\usepackage[pdftex,a4paper,colorlinks=true,linkcolor=black]{hyperref}
\usepackage{enumitem}
\usepackage{amsmath}
\usepackage{bbm}
\usepackage{amssymb}
\usepackage{graphicx}
%\usepackage{trfsigns}
\usepackage[usenames]{color}
\usepackage{listings}

% Shortcuts für Matrizen, '&' und '\\' gelten wie gewohnt
\newcommand{\mtrx}[1]{\begin{matrix}#1\end{matrix}} % ( normal Matrix )
\newcommand{\smtrx}[1]{\begin{smallmatrix}#1\end{smallmatrix}} % ( small Matrix )
\newcommand{\pmtrx}[1]{\begin{pmatrix}#1\end{pmatrix}}	% ( (...) )
\newcommand{\bmtrx}[1]{\begin{bmatrix}#1\end{bmatrix}}	% ( [...] )
\newcommand{\Bmtrx}[1]{\begin{Bmatrix}#1\end{Bmatrix}}	% ( {...} )
\newcommand{\e}{\text{e}}
\newcommand{\im}{\text{i}}

% code box
\setlength{\fboxrule}{1.2pt}
%\definecolor{codeFrame}{rgb}{0.1,0.1,0.1}
\definecolor{codeBg}{rgb}{0.96,0.96,0.96}
%\definecolor{codeFg}{rgb}{0.2,0.2,0.2}
%\definecolor{brown}{rgb}{0.6,0.3,0.3}
\definecolor{grey}{rgb}{0.4,0.4,0.4}
\definecolor{dgrey}{rgb}{0.2,0.2,0.2}
%\newcommand{\codebox}[1]{\fcolorbox{codeFrame}{codeBg}{\texttt{#1}}}
%\newcommand{\code}[2][codeFg]{\codebox{\textcolor{#1}{#2}}}

% paragraph settings, http://docutils.sourceforge.net/docs/user/latex.html
\setlength{\parindent}{0pt}
\setlength{\parskip}{6pt plus 2pt minus 1pt}

\lstdefinelanguage{auk}%
	{morekeywords={while,forall,for,if,else,true,false,struct,new,delete},%
		sensitive=true,%
		morecomment=[l]//,%
		morecomment=[s]{/*}{*/}}[keywords,comments]

\lstset{% general command to set parameter(s)
    basicstyle=\ttfamily\footnotesize,%\footnotesize,          % print whole listing small
    keywordstyle=\ttfamily\bfseries\color{black},%\ttfamily,
    identifierstyle=,           % nothing happens
    commentstyle=\itshape, % white comments
    stringstyle=\color{brown}\ttfamily,      % typewriter type for strings
    showstringspaces=false,     % no special string spaces
    %backgroundcolor=\color{codeBg},%
    framerule=.3pt,%
    frame=single,%
		float=htbp,
    extendedchars=true,
    language=auk,
		mathescape}
\lstset{tabsize=2}

%\newcounter{chapter}
%\def\thechapter{\Alph{chapter}}
%\def\thesection{\Roman{section}}
%\def\thesubsection{\arabic{subsection}}
%\def\thesubsubsection{\alph{subsubsection}}
%\def\theparagraph{\numeric{paragraph}}
%\setcounter{tocdepth}{4}
%\setcounter{secnumdepth}{4}

% Alph, römisch, arabic, alph, { 'aa', 'bb' ... }, { 'aaa', 'bbb', ... }, ...

%opening
%\title{Algorithmen und Datenstrukturen}
%\author{Franz Brauße}

\begin{document}
%\maketitle
%\tableofcontents

%\chapter{Voll der fette Scheiß}
\section{Graphen}
%\subsection{Tolle Graphen}
\begin{enumerate}
	\item $e = (v, w) :$ $e$ inzident zu $v$
	\item ``einfacher Pfad'': Pfad ohne Schleifen, d.h. knotendisjunkt ($v_i \neq v_j$ für $i \neq j$)
	\item $m \leq n^2$, $m = \vert E\vert$, $n = \vert N\vert$
		\par falls $m = n^2 \Rightarrow E = V \times V$, $G$ heißt vollständig
\end{enumerate}

Die Kanten eines Graphen lassen sich wie folgt einteilen. Sie $e = (v,w) \in E$,
\begin{enumerate}
	\item $e \in T$ falls $w$ noch nicht besucht
	\item $e \in F$ falls $w$ besucht und $\exists$ Pfad aus Kanten aus $T$-Knoten der Länge $\leq 1$, $v \neq w$.
	\item $e \in B$ falls $w$ besucht und $\exists$ Baumpfad von $w$ nach $v$ der Länge $\leq 0$ (evtl. $v = w$).
	\item $e \in C$ falls $w$ besucht und $\nexists$ Baumpfad von $v$ nach $w$ (Länge $\leq 1$)
		und $\nexists$ Baumpfad von $w$ nach $v$ (Länge $\leq 0$).
\end{enumerate}


\subsection{DFS}
%\subsubsection{Noch tiefer geschachtelt}
%\paragraph{Der Paragraph! §§}
Zeitkomplexität von \texttt{dfs()} $\in \mathcal O(n+m)$
\begin{lstlisting}
	dfs(v) {
		besucht[v] = true;
		dfsnum[v] = ++dfscnt;
		forall (w $\in$ V, (v, w) $\in$ E) {
			if (!besucht[w]) {
				// (v,w) $\in T$
				dfs(w);
			} else if (dfsnum[v] < dfsnum[w] && comp[v] > comp[w]) {
				// (v,w) $\in F, T$
			} else if (dfsnum[w] < dfsnum[v]) {
				if (comp[w] == 0) {
					// (v,w) $\in B$ (Kreis)
				} else {	// comp[v] < comp[w]
					// (v,w) $\in C$
		}	}	}
		comp[v] = true;
	}
\end{lstlisting}


\subsection{Topologische Sortierung}
Zeitkomplexität von \texttt{topsort()} $\in \mathcal O(n+m)$
\begin{lstlisting}
	topsort() {
		list l = $\{ v \in V \;|\; \text{indeg}(v) = 0 \}$
		int i = 0;
		while (!l.empty()) {
			node n = l.pop();
			topsort[n] = i++;
			forall (v $\in$ V, (n,v) $\in$ E) {
				indeg[v]--;
				if (indeg[v] == 0)
					l.push_back(v);
	}	}	}
\end{lstlisting}

\subsection{Gegenkanten}
Zeitkomplexität von \texttt{rev()} und \texttt{bucketsort()} $\in \mathcal O(n)$
%TODO: wie gestartet? wann bucketsort() aufgerufen?
\begin{lstlisting}
	list E1;	// Kanten aus $E$ sortiert nach source, target
	list E2;	// Kanten aus $E$ sortiert nach target, source
	rev[];		// Array von Pointern auf Kantern ueber Kanten
	
	rev() {
		while (!E1.empty() && !E2.empty()) {
			e1 = E1.head();
			e2 = E2.head();
			
			if (source(e1) < target(e2)) {
				E1.pop_front();
			} else if (target(e1) < source(e2)) {
				E2.pop_front();
			} else {
				rev[e1] = e2;
				E1.pop_front();
				E2.pop_front();
	}	}	}
\end{lstlisting}
\begin{lstlisting}
	bucketsort(list el) {		// el: Liste aus Kanten
		buckets[];						// Feld von Listen von Kanten ueber Knoten
		while (!el.empty()) {
			e = el.pop_front();
			buckets[source(e)].push_back(e);
		}
		forall (n $\in$ V)
			el.concat(buckets[v]);
		return el;
	}
\end{lstlisting}

\subsection{Transitive Hülle}
Zeitkomplexität von \texttt{trans\_hull()} $\in \mathcal O(n^3)$
\begin{lstlisting}
	queue M;		// init: $\emptyset$
	visited[];	// init: 0
	round = 0;
	
	trans_hull() {
		forall (v $\in$ V) {
			visited[v] = ++round;
			M.push(v);
			while (!M.empty()) {
				w = M.pop();
				forall (x $\in$ V, (w,x) $\in$ E)
					if (visited[x] < round) {
						M.push(x);
						visited[x] = round;
						E_ = E_ $\cup\; \{ (v, x) \}$
		}	}	}	}
		return E_;
	}
\end{lstlisting}

\subsection{Berechnung starker Zusammenhangskomponenten}
Zeitkomplexität von \texttt{szk()} $\in \mathcal O(n+m)$, da \texttt{dfs()} $\in \mathcal O(n+m)$ und $\forall v \in V$ wird $v$ genau einmal in \texttt{unfertig} und \texttt{wurzeln} eingefügt und entfernt ($\in \mathcal O(n)$).
\begin{lstlisting}
	stack unfertig;	// init: $\emptyset$
	stack wurzeln;	// init: $\emptyset$
	besucht[];			// init: false
	dfsnum[];
	scc_num[];			// Nummer der SZK
	in_unfertig[];	// v $\in$ unfertig? init: false
	
	szk(v) {
		dfsnum[v] = ++dfs_count;
		besucht[v] = true;
		unfertig.push(v);				/* \									*/
		wurzeln.push(v);				/*  + Neue SZK { v }	*/
		in_unfertig[v] = true;	/* /									*/
		
		forall (w $\in$ V, (v,w) $\in$ E)
			if (!besucht[w]) {
				szk(w);
			} else if (in_unfertig[w]) {		// mischen
				while (dfsnum[wurzeln.top()] > dfsnum[w])
					wurzeln.pop();
			}
		
		// Abschluss
		if (v == wurzeln.top()) {
			scc_count++;
			do {
				w = unfertig.pop();
				in_unfertig[w] = false;
				scc_num[w] = scc_count;
			} while (v != w);
			wurzeln.pop();
	}	}
\end{lstlisting}


\subsection{Bipartitheit}
Erweiterter \texttt{dfs()} $\Rightarrow$ Laufzeit $\in \mathcal O(n+m)$
\begin{lstlisting}
	color[];	// Feld von Knoten -> Farben, init: not_visited
	stack s;
	
	is_bipartit() {
		forall (v $\in$ V) {
			if (color[v] == not_visited) {
				color[v] = red;
				s.push(v);
				while (!s.empty()) {
					w = s.pop();
					forall (v $\in$ V, (w,v) $\in$ E) {
						if (color[v] == not_visited) {
							if (color[w] == red) color[v] = blue;
							else								 color[v] = red;
							s.push(v);
						} else if (color[v] == color[w]) {
							return false;
		}	}	}	}	}
		return true;
	}
\end{lstlisting}

\subsection{Distanzwerte von $s$ ausgehend $\forall v \in V$}
Erweitertes \texttt{bfs()} $\Rightarrow$ Laufzeit $\in \mathcal O(n+m)$
\begin{lstlisting}
	dist[];		// Init: -1
	queue q;
	
	dist(s) {
		dist[s] = 0;
		q.push(s);
		while (!q.empty()) {
			v = q.pop();
			forall (w $\in$ V, (v,w) $\in$ E) {
				if (dist[w] == -1) {
					dist[w] = dist[v] + 1;
					q.push(w);
	}	}	}	}
\end{lstlisting}

\subsection{Knotendisjunkte Pfade von $s$ nach $t$}
\begin{lstlisting}
	pred[];		// Feld von Knoten auf Knoten, init: 0
	dist[];		// Init mit Distanzwerten von s (siehe dist())
	result;		// Liste v Knoten
	
	v: wird durchsucht
	x: Vorgaenger von v im DFS-Baum
	t: Zielknoten
	dfs_next_path(v, x, t) {
		if (v == t) {
			result.push(x);
			return;
		}
		pred[v] = x;
		forall (w $\in$ V, (v,w) $\in$ E) {
			if (pred[w] == 0 && dist[v] == dist[w] - 1 && dist[w] $\leq$ dist[t])
				dfs_next_path(w, v, t);
	}	}
\end{lstlisting}

% TODO: Algorithmus für maximales Matching (Hopcroft-Karp)
% =========================================================

% TODO: vertex cover [4.3c)] lernen

\subsection{Dijkstras Algorithmus}
Zeitkomplexität von \texttt{dijkstra()} abhängig von Implementierung von \texttt{PQ}. Generell:
\[ \mathcal O(n \cdot (1 + T_\text{insert} + T_\text{empty} + T_\text{delmin}) + m \cdot (1 + T_\text{decrease\_p})) \]
\begin{itemize}
	\item unsortierte Liste: $\mathcal O(n^2 + m)$: 
		\begin{itemize}
			\item $T_\text{insert} \in \mathcal O(1)$
			\item $T_\text{empty} \in \mathcal O(1)$
			\item $T_\text{delmin} \in \mathcal O(n)$
			\item $T_\text{decrease\_p} \in \mathcal O(1)$
		\end{itemize}
	\item Fibonacci-Heap: $\mathcal O(n\cdot \log n + m)$
		\begin{itemize}
			\item $T_\text{insert} \in \mathcal O(1)$
			\item $T_\text{empty} \in \mathcal O(1)$
			\item $T_\text{delmin} \in \mathcal O(\log n)$ (amortisiert)
			\item $T_\text{decrease\_p} \in \mathcal O(1)$ (amortisiert)
		\end{itemize}
\end{itemize}

\begin{lstlisting}
	c(v, w);	// Kostenfunktion: E -> $\mathbbm R_0^+$ fuer Kante (v, w)
	DIST[];		// Feld Knoten -> reelle Zahl
	PQ;				// priority-queue (theor. optimal: Fibonacci-Heap)
	
	dijkstra(s) {
		forall (v $\in$ V)
			DIST[v] = $\infty$;
		DIST[s] = 0;
		PQ.insert(s, 0);
		
		while (!PQ.empty()) {
			u = PQ.delmin();
			forall (v $\in$ V, (u,v) $\in$ E) {
				d = DIST[u] + c(u, v);
				if (d < DIST[v]) {
					if (DIST[v] == $\infty$) {
						PQ.insert(v, d);
					} else {
						PQ.decrease_p(v, d);
					}
					DIST[v] = d;
	}	}	}	}
\end{lstlisting}

\section{Fibonacci-Heap}
Warteschlange, realisiert als Menge sog. ``Heap-ordered Trees''. Ein Baum dessen Knoten mit Information ($Inf: V \to \mathbbm R$) beschränkt ist, heißt ``heap-ordered'', falls für alle Knoten $v \in V: Inf(v) \geq Inf(Eltern(v))$.
Fibonacci-Heap ist ein Wald von heap-ordered trees und einem Zeiger auf die Wurzel mit der kleinsten Information. Die trees sind Binomische Bäume.

Die Knoten auf einer Baumebene bilden mit ihren Pointern \texttt{leftsib} und \texttt{rightsib} eine zirkuläre, doppelt verkettete Liste.

$\forall T_i \in$ \texttt{f->roots}: max Rang$(T_i) \leq \log n$ ($n$ = Anzahl Knoten in $T_i$).

% TODO: Bildchen zu verschmelze(v,w) und binomischen Bäumen
\begin{lstlisting}
	struct node : dlist_item {
		K key;
		I inf;
		node *parent, *child, *leftsib, *rightsib;
		int rang = 0;
		bool marked = false;
	};
	
	struct fibheap {
		struct node *min;					// Zeiger auf item in Wurzelliste mit minimalem inf-Eintrag
		struct dlist *roots;			// Liste von Wurzeln struct node*
	}
	
	void init(struct fibheap *f) {
		f->min = NULL;
	}
	
	K find_min(f) {								// in O(1)
		return f->min->key;
	}
	
	struct node * insert(f, K k, I i) {		// in O(1)
		struct node *n = new node;
		n->key = k;
		n->inf = i;
		put_root(f, n);
		return n;
	}
	
	K delete_min(f) {
		struct node *n = dlist_del(f->min);
		K r = n->key;
		struct node *m = n->child;
		delete n;
		n = m;
		dlist_append_list(f->roots, n->child);		// in O(1)
		verschmelze_roots(f);											// in O(max rang)
		f->min = dlist_find_min(f->roots);				// in O(max rang)
		return r;
	}
	
	void verschmelze_roots(f) {
		struct node *rang_arr[f->roots->size()];	// Array von Zeigern auf Wurzelelemente, init: NULL
		struct node *w, *v;
		dlist_forall(f->roots, w) {
			while ((v = f->root_arr[w->rang]) != NULL) {
				f->root_arr[w->rang] = NULL;
				w = verschmelze(f, v, w);							// in O(1)
			}
			f->root_arr[w->rang] = w;
	}	}
	
	struct node * verschmelze(f, v, w) {
		if (v->inf > w->inf)
			swap(v, w);
		dlist_remove(f->roots, w);
		w->parent = v;
		v->rang++;
		dlist_insert(v->child, w);
	}
	
	void decrease_p(f, struct node *v, I i) {
		v->inf = i;
		if (v->parent != NULL)
			markiere(f, v->parent);
		put_root(f, v);
	}
	
	void markiere(f, v) {					// worst-case in O($\log |T_i|$), $v \in T_i$, amortisiert in O(1)
		struct node *p;
		while (v->marked && (p = v->parent) != NULL) {
			p->rang--;
			put_root(f, v);
			v = p;
		}
		if (v->parent != NULL)
			v->marked = true;
	}
	
	void put_root(f, v) {
		v->parent = NULL;
		v->marked = false;
		struct node *it = dlist_append(f->roots, n);
		if (f->min && f->min->inf < v->inf)
			f->min = it;
	}
\end{lstlisting}


\section{Amortisierte Analyse}
\begin{itemize}
	\item Datenstruktur $D$
	\item Potentialfunktion $pot: D \to \mathbbm R_0^+$ ordnet Zuständen von $D$ einen nicht-negativen reellen Wert zu.
	\item Operation $op$ überführt $D$ in neuen Zustand $D'$: $D \stackrel{op}{\longrightarrow} D'$
\end{itemize}
\subsection{Definition}
\begin{itemize}
	\item $T_\text{tats}(op) :=$ tatächliche Kosten (Ausführungszeit) der Operation $op$
	\item $T_\text{amort}(op) := T_\text{tats} + \underbrace{pot(D') - pot(D)}_{\Delta pot}$
\end{itemize}
Betrachte Folge von Operationen $D_0 \stackrel{op_1}{\longrightarrow} D_1 \stackrel{op_2}{\longrightarrow} \ldots \stackrel{op_n}{\longrightarrow} D_n$.

Gesucht: Obere Abschätzung von $\sum_{i=1}^n T_\text{tats}(op_i)$. Betrachte nun Teleskopsumme
\begin{eqnarray*}
	\sum_{i=1}^n T_\text{amort}(op_i) &\stackrel{\text{Def.}}{=}& \sum_{i=1}^n(T_\text{tats}(op_i)) + pot(D_i) - pot(D_{i-1})
	= \sum_{i=1}^n T_\text{tats}(op_i) + pot(D_n) - pot(D_0) \\
	\Rightarrow \underbrace{\sum_{i=1}^n T_\text{tats}(op_i)}_{\text{gesucht}} &=&
	\underbrace{\sum_{i=1}^n T_\text{amort}(op_i)}_{\text{leichte Abschätzung (*)}} +
	\underbrace{pot(D_0)}_{= 0\text{ (*)}} -
	\underbrace{pot(D_n)}_{\geq 0\text{ (*)}}
\end{eqnarray*}
(*): durch geeignete Wahl von $pot$ ($pot(D_i) \geq 0$ und $pot(D_0) = 0$):
\[ \Rightarrow \sum_{i=1}^n T_\text{pot}(op_i) \leq \sum_{i=1}^n T_\text{amort}(op_i) \]

\subsection{Zu Fibonacci-Heaps}
Ränge der Einträge in der Wurzelliste sind alle paarweise verschieden $\Rightarrow pot(D_i) = D_i$\texttt{->roots->size}.
\begin{itemize}
	\item \texttt{find\_min()}: $T_\text{tats} = \mathcal O(1)$, $\Delta pot = 0$
	\item \texttt{insert()}: $T_\text{tats} = \mathcal O(1)$, $\Delta pot = 1$
	\item \texttt{delete\_min()}: $\Delta pot \leq$ max Rang $-$ \#Verschmelzungen
		\[ \Rightarrow T_\text{amort} = \underbrace{\text{max Rang} + \text{\#Verschmelzungen}}_{T_\text{tats}} + \Delta pot
			= \text{max Rang} \leq 2 \cdot \log n \in \mathcal O(\log n) \]
	\item \texttt{decrease\_p()}: Für Kinder $w_1, \ldots, w_i$ von Knoten $v$ mit Rang$(v) = i$: Rang$(w_j) \geq j - 2$
		(da Kinder nur durch \texttt{verschmelze}-Operationen hinzukommen können).
		
		$S_i :=$ minimale Zahl von Knoten im Unterbaum mit Wurzel $v$ von Rang $i$ (inklusive $v$) $\Rightarrow S_0 = 1$, $S_1 = 2$.
		
		Für $i \geq 2: S_i = 2 + S_0 + S_1 + \ldots + S_{i-2} = 2 + \sum_{j=0}^{i-2}S_j$.
		
		\begin{enumerate}
			\item\label{a} Fibonacci-Zahlen: $F_0 = 0$, $F_1 = 1$, $F_i = F_{i-2} + F_{i-1}$ für $i \geq 2$
			\item\label{b} $S_i \geq F_{i+2} \quad\forall i \geq 0$
			\item\label{c} $\Phi = \frac{1+\sqrt{5}}{2}$, $\Phi^2 = \frac{1+2\cdot\sqrt{5}+5}{4} = \frac{3 + \sqrt{5}}{2} = \Phi + 1$
			\item\label{d} $F_{i+2} \geq \left(\frac{1+\sqrt{5}}{2}\right)^i$ als exponentielle untere Schranke für $F_i$
		\end{enumerate}
		$\Rightarrow$ exponentielle untere Schranke für $S_i$: $S_i \stackrel{\ref{d}}{\geq} F_{i+2} \stackrel{\ref{b}}{\geq} \Phi^i \geq 1,618^i$
		\par Sei $r$ max Rang $\Rightarrow$ Mindestens $\Phi^r$ Knoten im Unterbaum mit Wurzel von Rang $r \Rightarrow \Phi^i \leq n \Rightarrow r \leq \log_\Phi n = \frac{\log n}{\log \Phi} \leq 1,4404 \cdot \log_2 n$
		\par Modifiziertes $pot(D) :=$ \#Wurzeln $+2\cdot$ Länge Sequenz markierter Knoten
		\par Sei $k =$ \#markierte Knoten, die in $op$ zu Wurzeln werden, dann $T_\text{tats}(op) \in \mathcal O(k + 1)$
		\par Potentialänderung $\Delta pot = k + 1 - 2 \cdot (k - 1) = 3 - k$, da
		\begin{itemize}
			\item \#Wurzeln $to$ \#Wurzeln $+ k + 1$
			\item \#Markierungen $to$ \#Markierungen - k - 1
		\end{itemize}
		$\Rightarrow T_\text{amort} = T_\text{tats} + \Delta pot = k + 1 + 3 - k = 4 \in \mathcal O(1)$
\end{itemize}


\end{document}



















