algorithms_theory: exzerpt.tex@c6cc84d9b6f4

     1 \documentclass[a4paper,11pt,twoside]{article}

     3 \usepackage[ngerman]{babel}

     4 \usepackage[T1]{fontenc}

     5 \usepackage[latin1]{inputenc}

     6 \usepackage[colorlinks=true,linkcolor=black]{hyperref}

     8 \usepackage{vaucanson-g}

     9 \usepackage{hyperref}

    10 \usepackage{hypcap}

    11 \usepackage{fancyhdr}

    12 \usepackage{graphicx}

    13 \usepackage{lastpage}

    14 \usepackage[cm]{fullpage}

    15 \usepackage{amsthm, amsmath, amsfonts}

    16 \usepackage{float}

    17 \usepackage{paralist}

    18 \usepackage{listings}

    19 \usepackage{color}

    20 \usepackage{bookmark}

    22 % Festlegung Art der Zitierung - Havardmethode: Abkuerzung Autor + Jahr

    23 \bibliographystyle{alphadin}

    25 \title{\underline{Exzerpt Algorithmentheorie WS10/11}}

    26 \author{Markus Lindenmann}

    27 \date{\today{} }

    29 \begin{document}

    30     \maketitle

    32     \tableofcontents

    33     \newpage

    35     \section{Einleitung}\label{sec:intro}

    36         Dozent:     Matthias Westermann\\

    37         Website:    lak.informatik.uni-freiburg.de\\

    38         Klausur:    09.03.2011\\

    39         Hilfsmittel:    Ein auf beiden Seiten handbeschriebenes DIN-A4-Blatt

    40         \subsection{Themen:}

    41             \begin{itemize}

    42                 \item[$\bullet$] Divide and Conquer

    43                 \item[$\bullet$] Greedy Prinzip

    44                 \item[$\bullet$] Dynamische Programmierung

    45                 \item[$\bullet$] Randomisierung

    46                 \item[$\bullet$] Amortisierte Analyse

    47             \end{itemize}

    48         \subsection{Problem-/Anwendungsbereiche:}

    49             \begin{itemize}

    50                 \item[$\bullet$] Geometrische Algorithmen

    51                 \item[$\bullet$] Algebraische Algorithmen

    52                 \item[$\bullet$] Graphenalgorithmen

    53                 \item[$\bullet$] Datenstrukturen

    54                 \item[$\bullet$] Internet-Algorithmen

    55                 \item[$\bullet$] ptimierungs-Verfahren

    56                 \item[$\bullet$] Zeichenkettenverarbeitung

    57             \end{itemize}

    58         \subsection{Literatur:}

    59             \bibliography{literatur}

    60             \cite{1}\cite{2}

    62     \newpage

    63     \section{Divide and Conquer}\label{sec:div&conq}

    64         \begin{itemize}

    65             \item[$\bullet$] Quicksort

    66             \item[$\bullet$] Formulierung und Analyse des Prinzips

    67             \item[$\bullet$] Geometrisches Devide and Conquer

    68             \begin{itemize}

    69                 \item[-] Closest-Pair

    70                 \item[-] Segmentschnitt

    71             \end{itemize}

    72         \end{itemize}

    74         \subsection{Formulierung des Divide and Conquer Prinzips}

    75             D\&C Verfahren zur Lösung eines Problems der Größe $n$

    76             \begin{itemize}

    77                 \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

    78                 \item[2.]   Conquer\\Löse die $k$ Teilprobleme auf dieselbe Art (rekursiv)

    79                 \item[3.]   Merge\\Füge die berechneten Teillösungen zu einer Gesamtlösung zusammen

    80             \end{itemize}

    82         \subsection{Quicksort}

    83             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.

    85             \subsubsection{Analyse}

    86                 $T(n)$ - maximale Anzahl von Schritten, um ein Problem der Größe $n$ zu lösen.

    87                 \[T(n)=\begin{cases}n\neq c&a \\ n>c&T(n_1+\ldots+T(n_k)+\text{Divide- und Mergeaufwand}\end{cases}\]

    88                 Best Case: $k=2, n_1=n_2=\frac{n}{2}$\\

    89                 Divide- und Mergeaufwand: $DM(n)$\\

    90                 $T(1)=a$\\

    91                 $T(n)=2T(\frac{n}{2})+DM(n)$

    93         \subsection{Nächste Paare}

    94             Eingabe:    $n$ Punkte in Ebene\\

    95             Ausgabe:    Punkt-Paar $q,r$ mit geringstem Abstand\\

    96             Abstand:    $d(q,r)$ bechreibt Abstand zwischen Punkten $q$ und $r$

    97             \subsubsection{Algorithmus}

    98                 \begin{itemize}

    99                     \item[$\bullet$] sortiere Punktmenge nach x-Koordinate

   100                     \item[$\bullet$] Teile Punktmenge in der Mitte L in die Mengen Q und R

   101                     \item[$\bullet$] Löse rekursiv auf Q und R

   102                     \item[$\bullet$] Sortiere Punkte nach y-Koordinate

   103                     \item[$\bullet$] Teste alle Paare, deren Abstand in der Sortierung kleiner als 16 ist (siehe unten)

   104                     \item[$\bullet$] Füge zusammen

   105                 \end{itemize}

   107                 $\delta=$ Minimum der Teillösungen\\

   108                 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.\\

   109                 \textbf{Problem:} alle Punkte können innerhalb der $\delta$-Zone liegen\\

   110                 \textbf{Lösung:}\begin{itemize}

   111                     \item[$\bullet$] Sortiere Punkte in $\delta$ Zone nach $y$-Abstand

   112                     \item[$\bullet$] Liegen in dieser Sortierung mehr als $c$ Punkte zwischen $q$ und $r$, dann kann $(q,r)$ nicht nächstes Paar sein

   113                 \end{itemize}

   115                 Dies kann für $c=15$ bewiesen werden (vgl. Abbildung \ref{cl_pair}):

   116                 \begin{itemize}

   117                     \item[$\bullet$] Seien min. 15 Punkte zwischen $q$ und $r$

   118                     \item[$\bullet$] Dann sind mindestens 3 Reihen Quadrate zwischen $q,r$, weil in jedem Quadrat höchstens ein Punkt ist.

   119                     \item[$\rightarrow$] Dann muss $d(q,r)$ mindestens $\frac{3}{2}\delta > \delta$ sein.

   120                 \end{itemize}

   122                 \begin{figure}[H]

   123                     \centering

   124                     \includegraphics[scale=0.5]{img/cl_pair}

   125                     \caption{Nächste Paare: Prüf Distanz}

   126                     \label{cl_pair}

   127                 \end{figure}

   129             \subsubsection{Analyse}

   130                 \[T(n)=\begin{cases}n\leq3&a \\ n>3&2T(\frac{n}{2})+an\end{cases}\]

   131                 \[T(n)\leq an \log n \]

   133         \subsection{Segmentschnitt}

   134             Eingabe:    Menge S bestehend aus vertikalen Segmenten und Endpunkten vn horizontalen Segmenten\\

   135             Ausgabe:    Alle Schnittpunkte von vertikalen Segmenten mit horizontalen Segmenten, von denen mindesens ein Endpunkt in S ist

   137             \subsubsection{Algorithmus}

   138                 \textbf{Divide \& Conquer:}\\Fallunterscheidung

   139                 \begin{itemize}

   140                     \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.

   141                     \item[2.] else: S enthält keine Schnitte

   142                 \end{itemize}

   144                 \textbf{Merge}\\

   145                 Bilde L(S), R(S) und V(S) (Definition am Beispiel $i=1,2$ berechnet: $S=S_1\cup S_2$):

   146                 \begin{itemize}

   147                     \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))$

   148                     \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))$

   149                     \item[$\bullet$] V(S): y-Intervalle der vertikalen Segmente in S\\$=V(S_1)\cup V(S_2)$

   150                 \end{itemize}

   151                 L,R sortiert nach steigender y-Koordinate\\

   152                 V sortiert nach steigendem unteren Endpunkt\\

   153                 \medskip

   155                 \textbf{Basisfälle}\\

   156                 S enthält nur ein Element s. Fallunterscheidung:

   157                 \begin{itemize}

   158                     \item[1.] $s=(x,y)$ ist ein linker Endpunkt:\\$L(S)=\{y\},\qquad R(S)=\emptyset,\qquad V(S)=\emptyset$

   159                     \item[2.] $s=(x,y)$ ist ein rechter Endpunkt:\\$L(S)=\emptyset,\qquad R(S)=\{y\},\qquad V(S)=\emptyset$

   160                     \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]\}$

   161                 \end{itemize}

   163             \subsubsection{Analyse}

   164                 Eingabe wird Anfangs sortiert und in Array gespeichert

   165                 \[T(n)=2T(\frac{n}{2}+an+\text{Größe der Ausgabe}\]

   166                 \[T(1)=O(1)\]

   167                 \[O(n \log n + k \mid k=\#Schnittpunkte\]

   169         \subsection{Polynomprodukt und Fast Fourier-Transformation}

   172 	\newpage

   173     \section{Randomisierung}

   174         \subsection{Hashing}

   176     \newpage

   177     \section{Amortisierte Analyse}

   178         \subsection{Binomial Heaps}

   179         \subsection{Fibonacci Heaps}

   180         \subsection{Union Find}

   182     \newpage

   183     \section{Greedy}

   185     \newpage

   186     \section{Anhang}

   187         \subsection{Landau-Symbole}

   188             \begin{figure}[H]

   189                 \centering

   190                 \includegraphics[scale=0.45]{img/landau_sym}

   191                 \caption{Definition der Landau Symbole}

   192                 \label{fig:landau_sym}

   193             \end{figure}

   194 \end{document}

author	lindenmannm
	Mon, 10 Jan 2011 00:16:59 +0100
changeset 0	c6cc84d9b6f4
child 1	ceae9bb06f42
permissions	-rw-r--r--