
lindenmannm@0: \documentclass[a4paper,11pt,twoside]{article}
lindenmannm@0: 
lindenmannm@0: \usepackage[ngerman]{babel}
lindenmannm@0: \usepackage[T1]{fontenc}
lindenmannm@0: \usepackage[latin1]{inputenc}
lindenmannm@0: \usepackage[colorlinks=true,linkcolor=black]{hyperref}
lindenmannm@0: 
lindenmannm@0: \usepackage{vaucanson-g}
lindenmannm@0: \usepackage{hyperref}
lindenmannm@0: \usepackage{hypcap}
lindenmannm@0: \usepackage{fancyhdr}
lindenmannm@0: \usepackage{graphicx}
lindenmannm@0: \usepackage{lastpage}
lindenmannm@0: \usepackage[cm]{fullpage}
lindenmannm@0: \usepackage{amsthm, amsmath, amsfonts}
lindenmannm@0: \usepackage{float}
lindenmannm@0: \usepackage{paralist}
lindenmannm@0: \usepackage{listings}
lindenmannm@0: \usepackage{color}
lindenmannm@0: \usepackage{bookmark}
lindenmannm@0: 
lindenmannm@0: % Festlegung Art der Zitierung - Havardmethode: Abkuerzung Autor + Jahr
lindenmannm@0: \bibliographystyle{alphadin}
lindenmannm@0: 
lindenmannm@0: \title{\underline{Exzerpt Algorithmentheorie WS10/11}}
lindenmannm@0: \author{Markus Lindenmann}
lindenmannm@0: \date{\today{} }
lindenmannm@0: 
lindenmannm@0: \begin{document}
lindenmannm@0:     \maketitle
lindenmannm@0:     
lindenmannm@0:     \tableofcontents
lindenmannm@0:     \newpage
lindenmannm@0: 
lindenmannm@0:     \section{Einleitung}\label{sec:intro}
lindenmannm@0:         Dozent:     Matthias Westermann\\
lindenmannm@1:         Website:    \url{http://lak.informatik.uni-freiburg.de}\\
lindenmannm@0:         Klausur:    09.03.2011\\
lindenmannm@0:         Hilfsmittel:    Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt
lindenmannm@0:         \subsection{Themen:}
lindenmannm@0:             \begin{itemize}
lindenmannm@0:                 \item[$\bullet$] Divide and Conquer
lindenmannm@0:                 \item[$\bullet$] Greedy Prinzip
lindenmannm@0:                 \item[$\bullet$] Dynamische Programmierung
lindenmannm@0:                 \item[$\bullet$] Randomisierung
lindenmannm@0:                 \item[$\bullet$] Amortisierte Analyse
lindenmannm@0:             \end{itemize}
lindenmannm@0:         \subsection{Problem-/Anwendungsbereiche:}
lindenmannm@0:             \begin{itemize}
lindenmannm@0:                 \item[$\bullet$] Geometrische Algorithmen
lindenmannm@0:                 \item[$\bullet$] Algebraische Algorithmen
lindenmannm@0:                 \item[$\bullet$] Graphenalgorithmen
lindenmannm@0:                 \item[$\bullet$] Datenstrukturen
lindenmannm@0:                 \item[$\bullet$] Internet-Algorithmen
lindenmannm@0:                 \item[$\bullet$] ptimierungs-Verfahren
lindenmannm@0:                 \item[$\bullet$] Zeichenkettenverarbeitung
lindenmannm@0:             \end{itemize}
lindenmannm@0:         \subsection{Literatur:}
lindenmannm@0:             \bibliography{literatur}
lindenmannm@1:             \nocite{*}
lindenmannm@0:     
lindenmannm@0:     \newpage
lindenmannm@0:     \section{Divide and Conquer}\label{sec:div&conq}
lindenmannm@0:         \begin{itemize}
lindenmannm@0:             \item[$\bullet$] Quicksort
lindenmannm@0:             \item[$\bullet$] Formulierung und Analyse des Prinzips
lindenmannm@0:             \item[$\bullet$] Geometrisches Devide and Conquer
lindenmannm@0:             \begin{itemize}
lindenmannm@0:                 \item[-] Closest-Pair
lindenmannm@0:                 \item[-] Segmentschnitt
lindenmannm@0:             \end{itemize}
lindenmannm@0:         \end{itemize}
lindenmannm@0:         
lindenmannm@0:         \subsection{Formulierung des Divide and Conquer Prinzips}
lindenmannm@0:             D\&C Verfahren zur Lösung eines Problems der Größe $n$
lindenmannm@0:             \begin{itemize}
lindenmannm@0:                 \item[1.]   Divide\\$n>2$:  Teile das Problem in $k$ Teilprobleme der Größe $n_1,\ldots n_k$ ($k\geq2$)\\$n\leq c:$ Löse das Problem direkt
lindenmannm@0:                 \item[2.]   Conquer\\Löse die $k$ Teilprobleme auf dieselbe Art (rekursiv)
lindenmannm@0:                 \item[3.]   Merge\\Füge die berechneten Teillösungen zu einer Gesamtlösung zusammen
lindenmannm@0:             \end{itemize}
lindenmannm@0:         
lindenmannm@0:         \subsection{Quicksort}
lindenmannm@0:             Wähle beliebiges Pivot Element $v$ und sortiere alle Elemente aus der Menge, die größer sind als $v$ rechts von $v$ ein, die anderen links. Verfahre im selben Muster mit den neuen Teilmengen links und rechts des Pivot Elements. Wenn die zu sortierende Folge $F$ nur ein Element beinhaltet, gebe $F$ zurück.
lindenmannm@0: 			
lindenmannm@0:             \subsubsection{Analyse}
lindenmannm@0:                 $T(n)$ - maximale Anzahl von Schritten, um ein Problem der Größe $n$ zu lösen.
lindenmannm@0:                 \[T(n)=\begin{cases}n\neq c&a \\ n>c&T(n_1+\ldots+T(n_k)+\text{Divide- und Mergeaufwand}\end{cases}\]
lindenmannm@0:                 Best Case: $k=2, n_1=n_2=\frac{n}{2}$\\
lindenmannm@0:                 Divide- und Mergeaufwand: $DM(n)$\\
lindenmannm@0:                 $T(1)=a$\\
lindenmannm@0:                 $T(n)=2T(\frac{n}{2})+DM(n)$
lindenmannm@0:         
lindenmannm@0:         \subsection{Nächste Paare}
lindenmannm@0:             Eingabe:    $n$ Punkte in Ebene\\
lindenmannm@0:             Ausgabe:    Punkt-Paar $q,r$ mit geringstem Abstand\\
lindenmannm@0:             Abstand:    $d(q,r)$ bechreibt Abstand zwischen Punkten $q$ und $r$
lindenmannm@0:             \subsubsection{Algorithmus}
lindenmannm@0:                 \begin{itemize}
lindenmannm@0:                     \item[$\bullet$] sortiere Punktmenge nach x-Koordinate
lindenmannm@0:                     \item[$\bullet$] Teile Punktmenge in der Mitte L in die Mengen Q und R
lindenmannm@0:                     \item[$\bullet$] Löse rekursiv auf Q und R
lindenmannm@0:                     \item[$\bullet$] Sortiere Punkte nach y-Koordinate
lindenmannm@0:                     \item[$\bullet$] Teste alle Paare, deren Abstand in der Sortierung kleiner als 16 ist (siehe unten)
lindenmannm@0:                     \item[$\bullet$] Füge zusammen
lindenmannm@0:                 \end{itemize}
lindenmannm@0:             
lindenmannm@0:                 $\delta=$ Minimum der Teillösungen\\
lindenmannm@0:                 Gibt es $q\in Q$ und $r\in R$ mit $d(q,r)<\delta$, dann sind sowohl $q$ als auch $r$ höchstens $\delta$ von $L$ (Mitte) entfernt.\\
lindenmannm@0:                 \textbf{Problem:} alle Punkte können innerhalb der $\delta$-Zone liegen\\
lindenmannm@0:                 \textbf{Lösung:}\begin{itemize}
lindenmannm@0:                     \item[$\bullet$] Sortiere Punkte in $\delta$ Zone nach $y$-Abstand
lindenmannm@0:                     \item[$\bullet$] Liegen in dieser Sortierung mehr als $c$ Punkte zwischen $q$ und $r$, dann kann $(q,r)$ nicht nächstes Paar sein
lindenmannm@0:                 \end{itemize}
lindenmannm@0:                 
lindenmannm@0:                 Dies kann für $c=15$ bewiesen werden (vgl. Abbildung \ref{cl_pair}):
lindenmannm@0:                 \begin{itemize}
lindenmannm@0:                     \item[$\bullet$] Seien min. 15 Punkte zwischen $q$ und $r$
lindenmannm@0:                     \item[$\bullet$] Dann sind mindestens 3 Reihen Quadrate zwischen $q,r$, weil in jedem Quadrat höchstens ein Punkt ist.
lindenmannm@0:                     \item[$\rightarrow$] Dann muss $d(q,r)$ mindestens $\frac{3}{2}\delta > \delta$ sein.
lindenmannm@0:                 \end{itemize}
lindenmannm@0:                 
lindenmannm@0:                 \begin{figure}[H]
lindenmannm@0:                     \centering
lindenmannm@0:                     \includegraphics[scale=0.5]{img/cl_pair}
lindenmannm@0:                     \caption{Nächste Paare: Prüf Distanz}
lindenmannm@0:                     \label{cl_pair}
lindenmannm@0:                 \end{figure}
lindenmannm@0: 
lindenmannm@0:             \subsubsection{Analyse}
lindenmannm@0:                 \[T(n)=\begin{cases}n\leq3&a \\ n>3&2T(\frac{n}{2})+an\end{cases}\]
lindenmannm@0:                 \[T(n)\leq an \log n \]
lindenmannm@0: 
lindenmannm@0:         \subsection{Segmentschnitt}
lindenmannm@0:             Eingabe:    Menge S bestehend aus vertikalen Segmenten und Endpunkten vn horizontalen Segmenten\\
lindenmannm@0:             Ausgabe:    Alle Schnittpunkte von vertikalen Segmenten mit horizontalen Segmenten, von denen mindesens ein Endpunkt in S ist
lindenmannm@0:             
lindenmannm@0:             \subsubsection{Algorithmus}
lindenmannm@0:                 \textbf{Divide \& Conquer:}\\Fallunterscheidung
lindenmannm@0:                 \begin{itemize}
lindenmannm@0:                     \item[1.] $\left| S\right| > 1$:\\ Teile S mittels einer vertikalen Gerade G in 2 gleichgroße Mengen $S_1$ (links von G) und $S_2$ (rechts von G). Führe rekursiv auf beiden Hälften aus.
lindenmannm@0:                     \item[2.] else: S enthält keine Schnitte
lindenmannm@0:                 \end{itemize}
lindenmannm@0:                 
lindenmannm@0:                 \textbf{Merge}\\
lindenmannm@0:                 Bilde L(S), R(S) und V(S) (Definition am Beispiel $i=1,2$ berechnet: $S=S_1\cup S_2$):
lindenmannm@0:                 \begin{itemize}
lindenmannm@0:                     \item[$\bullet$] L(S): y-Koordinate aller linken Endpunkte in S, deren rechter Partner nicht in S\\$=L(S_2)\cup(L(S_1)-R(S_2))$
lindenmannm@0:                     \item[$\bullet$] R(S): y-Koordinate aller rechten Endpunkte in S, deren linker Partner nicht in S\\$=R(S_1)\cup(R(S_2)-L(S_1))$
lindenmannm@0:                     \item[$\bullet$] V(S): y-Intervalle der vertikalen Segmente in S\\$=V(S_1)\cup V(S_2)$
lindenmannm@0:                 \end{itemize}
lindenmannm@0:                 L,R sortiert nach steigender y-Koordinate\\
lindenmannm@0:                 V sortiert nach steigendem unteren Endpunkt\\
lindenmannm@0:                 \medskip
lindenmannm@0:                 
lindenmannm@0:                 \textbf{Basisfälle}\\
lindenmannm@0:                 S enthält nur ein Element s. Fallunterscheidung:
lindenmannm@0:                 \begin{itemize}
lindenmannm@0:                     \item[1.] $s=(x,y)$ ist ein linker Endpunkt:\\$L(S)=\{y\},\qquad R(S)=\emptyset,\qquad V(S)=\emptyset$
lindenmannm@0:                     \item[2.] $s=(x,y)$ ist ein rechter Endpunkt:\\$L(S)=\emptyset,\qquad R(S)=\{y\},\qquad V(S)=\emptyset$
lindenmannm@0:                     \item[3.] $s=(x,y_1,y_2)$ ist ein vertikales Segment:\\$L(S)=\emptyset,\qquad R(S)=\emptyset,\qquad V(S)=\{[y_1,y_2]\}$
lindenmannm@0:                 \end{itemize}
lindenmannm@0:             
lindenmannm@0:             \subsubsection{Analyse}
lindenmannm@0:                 Eingabe wird Anfangs sortiert und in Array gespeichert
lindenmannm@0:                 \[T(n)=2T(\frac{n}{2}+an+\text{Größe der Ausgabe}\]
lindenmannm@0:                 \[T(1)=O(1)\]
lindenmannm@0:                 \[O(n \log n + k \mid k=\#Schnittpunkte\]
lindenmannm@0:         
lindenmannm@0:         \subsection{Polynomprodukt und Fast Fourier-Transformation}
lindenmannm@0:             
lindenmannm@0:             
lindenmannm@1: 	  \newpage
lindenmannm@0:     \section{Randomisierung}
lindenmannm@0:         \subsection{Hashing}
lindenmannm@0:     
lindenmannm@0:     \newpage
lindenmannm@0:     \section{Amortisierte Analyse}
lindenmannm@0:         \subsection{Binomial Heaps}
lindenmannm@0:         \subsection{Fibonacci Heaps}
lindenmannm@0:         \subsection{Union Find}
lindenmannm@0:     
lindenmannm@0:     \newpage
lindenmannm@0:     \section{Greedy}
lindenmannm@1:         \subsection{Kürzeste (billigste) Wege}
lindenmannm@0:     
lindenmannm@0:     \newpage
lindenmannm@1:     \section{Bin Packing}
lindenmannm@1:         \textbf{Problembeschreibung:}\\
lindenmannm@1:         Man hat $n$ Objekte verschiedener Größe mit $0<s_i\leq1\mid 1\leq i\leq n$. Gesucht ist die kleinst mögliche Anzahl an Kisten (Bins) der Größe 1, mit der alle Objekte verpackt werden können.
lindenmannm@1:         \subsection{Online Verfahren}
lindenmannm@1:             Jedes (ankommende) Objekt muss verpackt sein, bevor das nächste Objekt betrachtet wird. Ein Objekt verbleibt in derjenigen Kiste, in die es zuerst gepackt wird.\\
lindenmannm@1:             Kein Online Bin Packing Verfahren kann stets eine optimale Lösung finden!\\            
lindenmannm@1:             \textbf{Satz 1}: Es gibt Eingaben, die jeden Online Bin Packing Algorithmus zwingen, wenigstens $\frac{4}{3} OPT$ Bins zu verwenden, wobei $OPT$ die minimal mögliche Binzahl ist.\\
lindenmannm@1:             \textbf{Beweis} Annahme: Online Bin Packing Algorithmus benötigt stets weniger als $\frac{4}{3}OPT$ Bins.\\
lindenmannm@1:             Es wird eine Eingabe mit $2m$ Objekten angenommen. Die ersten $m$ sind um $\epsilon$ kleiner als $\frac{1}{2}$, die zweiten $m$ um $\epsilon$ größer. Die optimale Lösung sind $m$ Kisten, da immer ein großes mit einem kleinen Paket kombiniert werden kann. Nun teilt man die Analyse in zwei Zeitpunkte: nach $m$ Objekten und nach $2m$ Objekten. Laut Annahme gilt nach nach $m$ Objekten, dass die Anzahl der Bins $b$ nur maximal $\frac{4}{3} OPT$ groß sein darf. Mit $OPT=\frac{m}{2}$ gilt somit: $b=\frac{4}{3}\cdot\frac{m}{2}=\frac{2}{3}m$. Sei $b=b_1+b_2\mid b_1=\#$Bins mit einem Objekt, $b_2=\#$Bins mit zwei Objekten, so folgt $b_1+2b_2=m\implies b_1=m-2b_2\implies b=b_1+b_2=m-b_2$. Nach $2m$ Objekten ist $OPT=m$, wie zuvor beschrieben. $b_1$ Bins können zu diesem Zeitpunkt mit Objekten des zweiten Bereichs gefüllt werden, für die verbleibenden muss man neue Bins öffnen. Die Anzahl der neu zu öffnenden beträgt damit genau $b_2\implies \#$Bins $\geq b+m-b_1=m+b_2$. Die Annahme besagt $m+b_2\leq\#$Bins $<\frac{4}{3}m \wedge b_2<\frac{m}{3}$. Dies ist nur möglich, wenn $b=m-b_2>\frac{2}{3}m$ - Dies führt zu einem \underline{Widerspruch}, da $b$ zum Zeitpunkt 1, nach $m$ Objekten $<\frac{2}{3}m$ sein muss.
lindenmannm@1:             
lindenmannm@1:             \subsubsection{Next Fit (NF)}
lindenmannm@1:                 Verpacke das nächste Objekt in dieselbe Kiste wie das vorherige, wenn es dort noch hineinpasst, sonst öffne eine neue Kiste und verpacke es dort.\\
lindenmannm@1:                 \textbf{Satz 2}: (a) Für alle Inputfolgen $I$ gilt: $NF(I)\leq2OPT(I)$. (b) Es gibt Inputfolgen I mit $NF(I)\geq2OPT(I)-2$.\\
lindenmannm@1:                 \textbf{Beweis}\\
lindenmannm@1:                 (a) Betrachte zwei beliebige aufeinanderfolgende Kisten $B_{2k-1}, B_{2k}$. Man weiß, dass die beinhalteten Objekte eine Summengröße $>1$ haben, sonst wären selbige in einer Kiste. Daraus folgt, man kann nicht mehr als die doppelte Anzahl an Kisten als beim Optimum erreichen!\\
lindenmannm@1:                 (b) Inputfolge: $0.5, \frac{2}{n}, 0.5, \frac{2}{n}, 0.5, \frac{2}{n}, \ldots 0.5, \frac{2}{n}$.\\Next-Fit liefert nun immer Bins gefüllt mit $0.5 + \frac{2}{n}$. Darausfolgt $NF(I)=\frac{n}{2}$ und $OPT=\frac{n}{4}+1$ (weil $\frac{n}{2}$ mal 0.5er Objekte in $=\frac{n}{4}$ Kisten passen und $\frac{n}{2}$ $\frac{2}{n}$er Objekte in eine Kiste passen)\\
lindenmannm@1:                 Laufzeit für Inputfolgen der Länge $n$: NF $O(n)$
lindenmannm@1:             \subsubsection{First-Fit (FF)}
lindenmannm@1:                 Packe nächstes Objekt in die erste Kiste, in die es noch hineinpasst, wenn es eine solche Kiste gibt, sonst in eine neue Kiste.\\
lindenmannm@1:                 \textbf{Beobachtung}: Zu jedem Zeitpunkt kann es höchstens eine Kiste geben, die weniger als halb voll ist. ($\implies FF(I) \leq 2OPT(I)$)\\
lindenmannm@1:                 \textbf{Satz 3}: (a) Für alle Inputfolgen $I$ gilt $FF(I)\leq \lceil\frac{17}{10} OPT(I)\rceil$. (b) Es gibt Inputfolgen $I$ mit $FF(I)\geq\frac{17}{10}(OPT(I)-1)$. (b') Es gibt Inputfolgen $I$ mit $FF(I)=\frac{10}{6}OPT(I)$.\\
lindenmannm@1:                 \textbf{Beweis}\\
lindenmannm@1:                 (b') Inputfolge der Länge $3\cdot6m$. Dabei je $6m$ Objekte der Größen $\frac{1}{7}+\epsilon, \frac{1}{3}+\epsilon, \frac{1}{2}+\epsilon$, welche in gegebener Reihenfolge in Gruppen eingegeben werden. FF liefert hierbei $m$ Kisten gefüllt mit den Objekten der Größe $\frac{1}{7}+\epsilon$ (jeweils 6 pro Kiste) gefolgt von $\frac{6m}{2}=3m$ Kisten gefüllt mit Objekten der Größe $\frac{1}{3}+\epsilon$ (jeweils 2 pro Kiste) und schlussendlich $6m$ Kisten mit je einem Objekt der Größe $\frac{1}{2}+\epsilon$. Das macht in der Summe $10m$ Kisten. Die optimale Lösung packt je ein Objekt jeder Größe in eine Kiste und benötigt somit nur $6m$ Kisten.\\
lindenmannm@1:                 Laufzeit für Inputfolgen der Länge $n$: FF $O(n^2) \rightarrow O(n \log n)$
lindenmannm@1:             \subsubsection{Best-Fit (BF)}
lindenmannm@1:                 Verpacke das nächste Objekt in diejenige Kiste, in die es am besten passt (d.h. den geringsten Platz ungenutzt lässt).
lindenmannm@1:                 Verhalten von BF ähnlich zu FF.
lindenmannm@1:                 Laufzeit für Inputfolgen der Länge $n$: BF $O(n^2) \rightarrow O(n \log n)$
lindenmannm@1:         \subsection{Offline Verfahren}
lindenmannm@1:             \underline{NP-schwieriges Problem! Entscheidungsproblem ist NP-vollständig!}\\
lindenmannm@1:             Zunächst wird die Anzahl $n$ und alle $n$ Objekte vorgegeben. Dann beginnt die Verpackung.\\
lindenmannm@1:             $n$ und $s_1, ..., s_n$ sind gegeben, bevor die Verpackung beginnt!\\
lindenmannm@1:             $\rightarrow$ \underline{Optimale Verpackung} kann durch erschöpfende Suche bestimmt werden. ABER: Benötigt exponentielle Zeit! Daher Approximimationsalgorithmen, die schneller sind aber dafür unter Umständen nicht optimal!\\
lindenmannm@1:             Idee für Offline Approximationsalgorithmen: Sortiere die Objekte zunächst nach abnhemender Größe und verpacke größere Objekte zuerst!
lindenmannm@1:             \subsubsection{First Fit Decreasing (FFD oder FFNI)}
lindenmannm@1:                 \textbf{Lemma 1}: Sei $I$ eine Folge von $n$ Objekten mit Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann haben alle von FFD in den Bins $B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackten Objekte eine Größe von höchstens $\frac{1}{3}$.\\
lindenmannm@1:                 \textbf{Beweis}: \$\$\$TODO:Elsässer hat das in seiner VL gemacht - aber hässlich lang\$\$\$\\
lindenmannm@1:                 \textbf{Lemma 2}: Sei $I$ eine Folge von $n$ Objekten mit Größen $s_1\geq s_2\geq\ldots\geq s_n$ und sei $m=OPT(I)$. Dann ist die Anzahl der Objekte, die FFD in die Kisten $B_{m+1},B_{m+2},\ldots,B_{FFD(I)}$ verpackt, höchstens $m-1$.\\
lindenmannm@1:                 \textbf{Beweis}: Annahme: Es gibt mehr als $m-1$ Objekte. $x_1,\ldots,x_m$ in $I$, die FFD in extra Kisten verpacken. Dies führt zu einem Widerspruch. \$\$\$TODO:Warum?\$\$\$\\
lindenmannm@1:                 \textbf{Satz}: Für alle Inputfolgen I gilt $FFD(I)\leq(4 OPT(I)+\frac{1}{3})$.\\
lindenmannm@1:                 \textbf{Satz}:
lindenmannm@1:                 \begin{itemize}
lindenmannm@1:                     \item[1.] Für alle Inputfolgen $I$ gilt: $FFD(I)\leq \frac{11}{9} OPT(I)+4$
lindenmannm@1:                     \item[2.] Es gibt Inputfolgen $I$ mit: $FFD(I)=\frac{11}{9}OPT(I)$.
lindenmannm@1:                 \end{itemize}
lindenmannm@1:                 \textbf{Beweis}: \$\$\$TODO\$\$\$
lindenmannm@1:             \subsubsection{Best Fit Decreasing (BFD)}
lindenmannm@1:                 Nicht im Script???
lindenmannm@1:     
lindenmannm@1:     \newpage
lindenmannm@1:     \section{Dynamische Programmierung}
lindenmannm@1:         
lindenmannm@1:         
lindenmannm@1:     \newpage
lindenmannm@1:     \begin{appendix}
lindenmannm@1:         \section{Landau-Symbole}
lindenmannm@0:             \begin{figure}[H]
lindenmannm@0:                 \centering
lindenmannm@0:                 \includegraphics[scale=0.45]{img/landau_sym}
lindenmannm@0:                 \caption{Definition der Landau Symbole}
lindenmannm@0:                 \label{fig:landau_sym}
lindenmannm@0:             \end{figure}
lindenmannm@1:     \end{appendix}
sawine@2: \end{document}




