algo2algorithmen.tex

\section{Appendix A: Algorithmen und Erklärungen}

Aufstellung und Erläuterung aller Algorithmen der Vorlesung Vorlesung "`Algorithmen II"' aus dem Wintersemester 2014.\footnote{\url{http://geom.ivd.kit.edu/ws14_algo2.php}}

\subsection{Algorithmus von Ford und Fulkerson}
\input{algo2/algo_ford-fulkerson}

\subsubsection{Eingaben}
\begin{itemize}
	\item Rationale Eingaben: Terminiert sicher für alle rationalen Eingaben
	\item Irrationale Kapazitäten: Muss nicht terminieren, da der Algorithmus unendliche lange laufen kann (und auch nicht gegen den maximalen Fluss konvergieren muss) oder ein falsches Ergebnis liefert\footnote{\url{http://www.cs.huji.ac.il/~nati/PAPERS/ALGORITHMS/zwick.pdf}}
\end{itemize}

\subsubsection{Korrektheit}
\begin{itemize}
	\item Beweis von Ford und Fulkerson: Ein \(q-s\) - Fluss ist dann maximal, wenn es keinen augmentierenden (erhöhenden) Pfad gibt
	\item Während der Durchführung erhöht sich der Fluss in jedem Schritt
	\item Terminiert bei ganzzaligen Eingaben, da \(W_f\) immer um mindestens \(1\) erhöht wird und \(W_f \leq \sum k(q,V) < \infty\)
	\item Terminiert bei rationalen Eingaben, da der Fluss stets mindestens um \(\frac{1}{Hauptnenner}\) erhöht wird
\end{itemize}

\subsubsection{Laufzeit}
\begin{itemize}
	\item Pro Schleifendurchlauf benötigt der Algorithmus \(\mathcal{O}(|V|+|E|)\) Zeit
	\item Insgesamt: \(\mathcal{O}(|E| \cdot max\{W_f~|~Fluss~in~F\})\), denn ein Pfad \(q \rightarrow^* s\) in \(|E|\) gefunden werden kann.
	\item Die Laufzeit hängt stark von der Anzahl der Schleifendurchläufe ab, da flussvergrößernde Pfade sehr ungünstig gewählt werden können.
\end{itemize}


\subsection{Algorithmus von Edmonds und Karp}
Erhöht man den Fluß in Ford-Fulkerson immer längs eines kürzesten Pfads (Breitensuche), erhält man den \textit{Edmonds-Karp-Algorithmus}.

\begin{itemize}
	\item Die Länge \(l_f x\) der kürzesten Pfade \(q \rightarrow^* s\) in \(G_f\) wächst monoton
	\item Terminiert für reelle Eingaben
\end{itemize}

\subsubsection{Laufzeit}
\begin{itemize}
	\item In jedem Schritt verliert \(E_f\) eine Kante
	\item Wird die Gegenkante durch einen kürzesten Pfad erhöht, kommt diese wieder zurück \(\rightarrow l_fy\) ist um mindestens \(2\) gewachsen 
	\item Da \(l_f y < |V|-1\) verliert \(E_f\) eine Kante maximal \(\frac{|V|}{2}\)-Mal \(\rightarrow\) Anzahl der Edmonds-Karp-Iterationen \(\in \mathcal{O}(|V| \cdot |E|)\)
    %\item Wird eine Kante rückwärts benutzt, wächst die Länge des Flusses um mindestens \(2\), weil gelten muss: $l(s \rightarrow^{\ast} x) \le l(s \rightarrow^{\ast} y)$.\\
    %Wird $x \rightarrow y \rightarrow^{\ast} s$ hinzugefügt, gilt $\forall \text{ Wege } x \rightarrow^{\ast} s : l(x \rightarrow^{\ast} s) > l(y \rightarrow^{\ast} s)$.\\
    %Wird $y \rightarrow x$ eingefügt, gilt die Abschätzung $l(s \rightarrow^{\ast} x) = l(s \rightarrow^{\ast} y)$ und es folgt $l(s \rightarrow^{\ast} y \rightarrow x \rightarrow^{\ast} s) \ge l(s \rightarrow^{\ast} x \rightarrow y \rightarrow^{\ast} s)+2$
	\item Durch die Breitensuche (Worstcase-Laufzeit \(\mathcal{O}(|V|+|E|)\)) ergibt sich eine Gesamtlaufzeit von \(\mathcal{O}(|E|^2 \cdot |V|)\)
\end{itemize}


\subsection{Die Präfluss-Pusch-Methode}
Jeder Knoten erhält zusätzlich eine Höhe und ein Reservoir, um vorübergehend beliebig viel Fluss speichern zu können. Letztere könnten nur bergab entleert werdern.\footnote{\url{http://de.wikipedia.org/wiki/Goldberg-Tarjan-Algorithmus}}

\subsubsection{Pusch}
\(Push(x,y)\) ist nur erlaubt, wenn Überschuss bei \(x\) vorhanden und \(h(x)-h(y) \geq 1\) ist.
\input{algo2/algo_praeflusspusch_pusch}

\subsubsection{Lifte}
\(Lifte(x)\) ist nur erlaubt, wenn Überschuss bei \(x\) vorhanden und \(h(x) \leq \min_{((x,y) \in E_f}{h(y)}\) ist.
\text{}\\
\input{algo2/algo_praeflusspusch_lifte}

\subsubsection{Durchführung}
\input{algo2/algo_praeflusspusch}

\subsubsection{Korrektheit}
\begin{itemize}
	\item Im Verlauf des Algorithmus bleibt \(h\) immer eine gültige Höhenfunktion, da alle erlaubten Operationen die Grundbedingungen des Flussnetzwerks nicht verletzen.
	\item Terminiert der Algorithmus, ist \(f\) maximal, da es keinen weiteren Pfad \(q \rightarrow^* s\) gibt (da ansonten gelten müsste: \(h(s) \geq h(q)-|V|+1=1\))
\end{itemize}

\subsubsection{Laufzeit}
\begin{itemize}
	\item \textit{Lifte} wird höchstens \(2 \cdot |V|^2\) aufgerufen
	\item Saturierendes \textit{Pusch}: Die Kante ist überbelegt, d.h. \(u(x) \geq k_f(x,y)\)
	\item Anzahl durchgeführte, saturierende \textit{Präfluss-Pusch-Operationen} \(< 2 \cdot |V| \cdot |E|\), da um ein saturierendes \textit{Pusch} erneut ausführen zu können, \(h(y)\) um mindestens \(2\) erhöht und ein \(Pusch(y,x)\) ausgeführt werden muss.
	\item Anzahl durchgeführte \textit{Pusch-} und \textit{Lifte}-Operationen \(\in \mathcal{O}(|V|^2\cdot |E|)\)
\end{itemize}


\subsection{"`An die Spitze"' Präfluss-Pusch-Algorithmus}
Formalisierung bzw. Erweiterung des \textit{Präfluss-Pusch-Algorithmus}.
\begin{itemize}
	\item Verwaltung einer Knotenliste \(L\) in der \(x\) vor \(y\) auftritt, falls \((x,y)\) puschbar ist
	\item Verwaltung einer Liste \(i_x\) von Nachbarknoten \(n_x\) pro Knoten
\end{itemize}
\input{algo2/algo_an-die-spitze_leere}
\text{}\\
\input{algo2/algo_an-die-spitze}

\subsubsection{Laufzeit}
Faktoren, welche die Laufzeit beeinflussen:
\begin{itemize}
	\item Anzahl Aufrufe von \(Leere(x)\) mit \(u(x) = 0\)
	\begin{itemize}
		\item Da \textit{Lifte} höchstens \(3\)-mal aufgerufen wird, folgt \(|Aufrufe(Leere)| < 2\cdot |V|^3\)
	\end{itemize}
	\item Anzahl der Aufrufe der Hauptschleife
	\begin{itemize}
		\item Höchstens \(\mathcal{O}(|V| \cdot |E||)\) Aufrufe von \textit{Lifte} und saturierendem \textit{Pusch} \(\rightarrow\) Gesamtaufwand \(\mathcal{O}(|V|^3)\)
	\end{itemize}
\end{itemize}
Laufzeit damit \(\in \mathcal{O}(|V|^3)\).



\subsection{Paare (Paaren in bipartiten Graphen)}
\input{algo2/algo_paare}

\subsubsection{Laufzeit}
Aufwand \(\in \mathcal{O}(|E|\cdot \sum f(q, V_1)) \subset \mathcal{O}(|E| \cdot |V_1|)\), da ein Pfad \(q \rightarrow^* s\) in \(|E|\) Schritten gefunden werden kann (siehe Laufzeit von \textit{Ford-Fulkerson}).

\subsection{Quicksort (Sortieren durch stochastisches Teilen)}
Zunächst wird die zu sortierende Liste in zwei Teillisten („linke“ und „rechte“ Teilliste) getrennt. Dazu wählt Quicksort ein sogenanntes Pivotelement aus der Liste aus. Alle Elemente, die kleiner als das Pivotelement sind, kommen in die linke Teilliste, und alle, die größer sind, in die rechte Teilliste. Die Elemente, die gleich dem Pivotelement sind, können sich beliebig auf die Teillisten verteilen. Nach der Aufteilung sind die Elemente der linken Liste kleiner oder gleich den Elementen der rechten Liste.

Anschließend muss man also nur noch jede Teilliste in sich sortieren, um die Sortierung zu vollenden. Dazu wird der Quicksort-Algorithmus jeweils auf der linken und auf der rechten Teilliste ausgeführt. Jede Teilliste wird dann wieder in zwei Teillisten aufgeteilt und auf diese jeweils wieder der Quicksort-Algorithmus angewandt, und so fort. Diese Selbstaufrufe werden als Rekursion bezeichnet. Wenn eine Teilliste der Länge eins oder null auftritt, so ist diese bereits sortiert und es erfolgt der Abbruch der Rekursion.\footnote{\url{http://de.wikipedia.org/wiki/Quicksort\#Prinzip}}
\text{}\\\\
\input{algo2/algo_quicksort}

\subsubsection{Laufzeit}
\begin{itemize}
	\item Aufwandsabschätzung anhand der in Schritt 3 durchgeführten Vergleiche
	\item Wahrscheinlichkeit, dass \(s_i\) und \(s_j\) verglichen werden steigt mit der Anzahl der Zwischenelemente (\(p_{ij}=\frac{2}{|j-i|+1}\))
	\item Daraus ergibt sich ein Aufwand \(\in \mathcal{O}(nlogn)\) (Summe der Erwartungswerte der Einzelwahrscheinlichkeiten)
\end{itemize}


\subsection{Minimaler Schnitt}
Ist \(E\) eine Folge in \(V^2\) heißt \((V,E)\) Multigraph, weil Kanten mehrfach vorkommen können. \(S \subset E\) heißt \textit{Schnitt} von \((V,E)\), wenn \((V, E \backslash S)\) unzusammenhängend ist, also mindestens zwei Komponenten hat.
\text{}\\
\input{algo2/algo_schnitt}


\subsection{Finde}
Findet das \(k\)-kleinste Element in einer unsortierten Liste.
\text{}\\
\input{algo2/algo_finde}

\subsubsection{Laufzeit}
\(\mathcal{O}(n)\)

\subsection{Spielbaumauswertung}
Binärer Spielbaum: Balancierter Binärbaum gerader Höhe \(2k\), mit Knotenwerten \(\in \{0,1\}\). Dies entspricht einem Spiel, bei dem zwei Spieler abwechselnd ihren Gewinn maximieren.

Es gilt außerdem:
\begin{itemize}
	\item \(Wert(x) = Wert(y) \downarrow Wert(z)\)
	\item \(a \downarrow b := a~NOR~b := \overline{a \vee b}\)
	\item \((a \downarrow b) \downarrow (c \downarrow d) = \overline{\overline{a \vee b} \vee \overline{c \vee d}} = (a \vee b) \wedge (c \vee d)\)
\end{itemize}

\subsubsection{Extrema}
\begin{itemize}
	\item Minima: Werte der Nicht-Blatt-Knoten auf gerader Höhe
	\item Maxima: Werte der Nicht-Blatt-Knoten auf ungerader Höhe
\end{itemize}

\input{algo2/algo_wert}


\subsection{BZR (Binäre Zerlegung des Raum)}
Rekursive Zerlegung eines Polyeders des \(\mathbb{R}^3\) anhand einiger Polygone. Pro Iterationsschritt wird jeweils ein Polygon bestimmt (bevorzugt eines, das den Polyeder komplett zerlegt). Dieses teilt den Polyeder in einen linken und einen rechten Teilpolyeder, die jeweils weiter zerlegt werden.
\text{}\\
\input{algo2/algo_brz}


\subsection{Konstruktion konvexer Hüllen}
Die konvexe Hülle einer Teilmenge ist die kleinste konvexe Menge, die die Ausgangsmenge enthält.\footnote{\url{http://de.wikipedia.org/wiki/Konvexe_Hülle}}

\subsubsection{Annahmen}
\begin{itemize}
	\item Die Reiehenfolge der \(p_i\) sei gleichverteilt zufällig
	\item Keine vier der Ebenen \(p_i^{*}\) schneiden sich in einem Punkt
	\item Jeder Knoten hat den Grad \(3\)
\end{itemize}
\input{algo2/algo_konvexe-huelle}
\text{}\\
Gesamtlaufzeit \(\in \mathcal{O}(nlogn)\).


\subsection{Pledge Startegie}
\begin{itemize}
	\item Ziel: Finde einen Weg aus einem Labyrinth.
	\item Der Roboter kann erkennen, wenn er das Labyrinth verlassen hat.
	\item Bei jeder Drehung wird die Änderung zum Startwinkel \(\phi\) aktualisiert.
\end{itemize}
\input{algo2/algo_pledge}


\subsection{Wanze}
Findet ein Ziel in einer Umgebung mit Hindernissen.
\text{}\\
\input{algo2/algo_wanze}

\textit{Wanze} terminiert, da \(R\) das Ziel spätestens dann findet, wenn er alle \(P_i\) maximal einmal umlaufen hat (bei jedem Umlaufen verkleinert sich die Distanz zum Ziel).


\subsection{Türsuche 1}
Roboter steht vor einer langen Wand und sucht die Tür.
\text{}\\
\input{algo2/algo_tuersuche-1}


\subsubsection{Kompetitivität}
Weglänge: Ist die Tür \(d = n + (0,1)\) Meter vom Ausgangspunkt entfernt, gilt:\newline
\(w \geq 2 \cdot 1 + 2 \cdot 2 + ... + 2n +n = O(n^2) \rightarrow\) \textit{Türsuche 1} ist nicht kompetitiv.


\subsection{Türsuche 2}
Roboter steht vor einer langen Wand und sucht die Tür.

\begin{algorithm}[H]
	\caption{Türsuche 2}
	\SetKwData{Left}{left}\SetKwData{This}{this}\SetKwData{Up}{up}
	\SetKwFunction{Union}{Union}\SetKwFunction{FindCompress}{FindCompress}
	\SetKwInOut{Input}{input}\SetKwInOut{Output}{output}

	$i \longleftarrow 1$
	\BlankLine
	
	\While{Tür noch nicht gefunden}{	
		gehe $i$ Meter der Wand entlang\newline
		\tcc{ändert die Laufrichtung}
		gehe i Meter zurück\newline
		$i \longleftarrow 2i$\\
	}
\end{algorithm}

\subsubsection{Kompetitivität}
Weglänge: Ist die Tür \(d = 2^{n+\delta}\) Meter vom Ausgangspunkt entfernt, gilt:\newline
\(w \leq 2 \sum\limits_{i=0}^{n+1} 2^i + d \leq 2 ^{n+3+\delta} + d \le 9 \cdot d \rightarrow\) \textit{Türsuche 2} ist 9-kompetitiv.


\subsection{Sternsuche}
Verallgemeinerung der \textit{Türsuche}: Roboter steht in der Mitte eines Kreuzes aus \(m\) Halbgeraden.
\text{}\\
\input{algo2/algo_sternsuche}

\subsubsection{Kompetitivität}
Sternsuche ist kompetetiv mit dem Faktor \(c = 2m \left(\frac{m}{m-1}\right)^{m-1}+1\).


\subsection{Simplex}
Um \(z\) zu maximieren, machen wir sukzessiv neue \(y_i\) zu neuen Koordinaten, so dass der Ursprung von Ecke zu Ecke von \(s\) wandert und der Wert von \(z\) im Ursprung wächst. Dazu tauschen wir immer eine Koordinate von \(\overline{y}\) mit einer von \(\overline{\overline{y}}\).
\text{}\\
\input{algo2/algo_simplex_austausch}
\text{}\\
\input{algo2/algo_simplex}


\subsection{Zufallsgesteuerte Optimierung}
Optimierungsaufgaben bestehen aus 
\begin{enumerate}
	\item Suchraum $Q$, Teil des Zustandsraumes $Z$,
	\item Bewertungsfunktion $c: Z \rightarrow \mathbb{R}$, die jedem Zustand $q$ seine Kosten $c(q)$ zuweist,
	\item Eine Funktion $l: Z \rightarrow \mathbb{R}$, die für alle $q \in Q$ die Nebenbedingungen charakterisiert.
\end{enumerate}

\subsubsection{Definitionen}
\begin{itemize}
	\item Gesucht wird ein \(q \in Q\) mit minimalen oder maximalen Kosten
	\item Eine Optimierungsaufgabe heißt kombinatorischen, wenn \(Q\) diskret ist
	\item Nebenbedingungen können vermieden werden, indem man \(c\) so umformuliert, dass \(q \not\in Q\) so schlecht bewertet werden, dass sie nicht als Lösung in Frage kommen: \(c'(q) = c(q) + \gamma \cdot l^2(q)\)
	\item \(q\) ist globales Optimum: \(\forall p \in Q~|~p \ne q: c(q) \le c(p)\)
	\item \(q\) ist lokales Optimum: \(\forall p \in Nachbar(q): c(q) \le c(p)\)
\end{itemize}

\subsubsection{Gradientenverfahren}
Zustandsraum \(Z \in \mathbb{R}^n\), jeder Zustand ist ein Punkt \(x = [x_1, ... , X_n]^T\).
Ausgehend vom Startpunk $x_0$ wird der Gradient der Kostenfunktion an der aktuellen Stelle berechnet:
\[\Delta c(x_0) = \left[ \diffp{c}{{x_{1}}}, ... , \diffp{c}{{x_{n}}} \right]\]

\begin{itemize}
	\item Die Nachfolger werden definiert durch \(x_{i+1} = x_i + h \cdot \delta c(x_i)\), wobei \(h > 0\) wenn \(c\) maximiert wird, bzw. \(h < 0\) wenn \(c\) minimiert wird
	\item Der Gradient ist die Richtung des steilsten Auf-/Abstiegs $\rightarrow$ Methode des steilsten Auf-/Abstiegs
	\item Gradientenverfahren sind deterministisch
	\item Es kann passieren, dass nur ein lokales Optimum gefunden wird \(\rightarrow\) nur anwenden, wenn es keine lokalen Optima/Minima gibt; Ableitung und Straftherme einfach zu berechnen sind
\end{itemize}

\subsubsection{Suchverfahren}
Ist der Suchraum diskret, definiert man für alle \(q\) die Menge der direkten Nachbarn \(N(q) \subset Q \rightarrow\) man kann \(Q\) von einem Anfangszustand aus durchsuchen.

Alle folgenden Algorithmen sind Suchverfahren.

\paragraph{Simuliertes Tempern}
\text{}\\
\input{algo2/algo_simuliertes-tempern}


\paragraph{Schwellwert Algorithmus}
\begin{itemize}
	\item Wähle zufälligen Nachbarn, gilt \(c(p) \geq c(q) - \sigma\), fahre fort mit \(q = p\)
	\item Schwellwert \(\sigma\) wird mit der Zeit kleiner
	\item Besser als Simuliertes Tempern, kann trotzdem in lokalem Maxima hängen bleiben
\end{itemize}

\paragraph{Sintflut Algorithmus}
\begin{itemize}
	\item Starte mit $\sigma = 0$. Wähle zufälligen Nachbarn. Gilt $c(p) > \sigma$, fahre fort mit $q = p$
	\item $\sigma$ wird mit der Zeit größer
	\item Besser als Simuliertes Tempern, kann trotzdem in lokalem Maxima hängen bleiben
\end{itemize}

\paragraph{Rekordjagt Algorithmus}
\begin{itemize}
	\item Bisher höchster Wert (Rekord) wird gespeichert
	\item Akzeptanzbedingung: \(c(p) \geq Rekord - \sigma\)
	\item \(\sigma\) wird mit der Zeit abgesenkt
	\item Besser als Simuliertes Tempern, kann trotzdem in lokalem Maxima hängen bleiben
\end{itemize}

\subsubsection{Evolutionäre Algorithmen}
\begin{itemize}
	\item Eine Population besteht aus Individuen
	\item Individuen haben einen Genotyp / Merkmalsvektor \(q \in \mathbb{R}^n\) und einen Phänotyp/Bewertungsfunktion \(c(q)\)
	\item Individuen können sich fortpflanzen. Haben sie zwei oder mehr Eltern $\rightarrow$ Kreuzung, haben sie einen Elter $\rightarrow$ Klon
	\item Die Größe der Population wird konstant gehalten
\end{itemize}

\paragraph{Plus oder $(\mu + \lambda)$ Strategie}
\begin{itemize}
	\item Die Population \(Q\) ändert sich mit der Zeit, ihre Größe \(\mu = |Q|\) bleibt konstant
	\item Die \(\mu\) Individuen mit der besten Fitness \(c(q)\) und \(\lambda\) Nachkommen bilden die nächste Generation, \(\lambda\) Eltern sterben
	\item Eltern werden gleichverteilt aus \(Q\) gewählt
	\item Es wird nicht gekreuzt, sondern nur geklont und mutiert. Zumindest steht nichts davon im Skript, sollte aber möglich sein...
\end{itemize}

\paragraph{Mehrere Eltern}
\text{ }\\Es kann auch mehrere Eltern geben, die Merkmalsvektoren werden entweder gemischt oder gemittelt.


\paragraph{Allgemeine Strategie $((\mu, k, \lambda, p) - ES)$}
\begin{itemize}
	\item \(\mu\): Populationsgröße - Für jede Generation konstant.
	\item \(\lambda\): Anzahl der Nachkommen pro Generation
	\item \(k\): Maximale Lebenszeit - \((k = 1)\) bei Komma-, \((k=\infty)\) bei Plus-Strategie
	\item \(p\): Anzahl der Eltern eines Individuums
\end{itemize}

\subsubsection{Genetische Algorithmen}
Merkmale in binärem Merkmalsvektor gespeichert, starke Eltern pflanzen sich häufiger fort als schwache.

\begin{itemize}
	\item Fortpflanzung: Jedes Individuum wird mit der Wahscheinlichkeit \(W(q) = \frac{c(q)}{\sum\limits_{p \in Q}c(p)}\) Elter. die \(\mu\) Individuen erzeugen \(\mu\) Nachkommen, nur diese überleben.
	\item Kreuzung: Von den \(\mu\) Nachkommen werden \(p\%\) einer Kreuzung unterzogen. Die Kreuzungspaare sind zufällig.
	\item Mutation: Jedes Bit des Merkmalsvektors wird mit einer sehr kleinen Wahscheinlichkeit \(p_m\) invertiert.
\end{itemize}

\paragraph{Schema-Theorem:} Merkmale werden häufiger reproduziert, wenn sie 
\begin{enumerate}
	\item durch weniger Bits dargestellt werden,
	\item diese Bits eng zusammenstehen (im Vektor),
	\item sie eine hohe Fitness bedeuten.
\end{enumerate}

\subsubsection{Vergleich: Evolutionsstrategien vs. Genetische Algorithmen}
\begin{itemize}
	\item Evolutionsstrategien $\rightarrow$ konvergieren schneller, enden aber öfter in lokalem Max/Min.\\
	\item Genetische Algorithmen $\rightarrow$ bevorzugen Kreuzung statt Mutation, größere Sprünge im Suchraum, finden öfter globales Optimum, konvergieren schlechter.
\end{itemize}

\subsubsection{Partikelschwarmoptimierung (P-S-O)}
\input{algo2/algo_pso}


\subsection{Algorithmus von de Casteljau}
Der Algorithmus von de Casteljau ermöglicht die effiziente Berechnung einer beliebig genauen Näherungsdarstellung von Bézierkurven durch einen Polygonzug.\footnote{http://de.wikipedia.org/wiki/De-Casteljau-Algorithmus}

Der de Casteljau-Algorithmus angewendet auf ein Polygon \(B_0^0\) ist die Konkatenation von \(B_0^1\) und \(B_1^1\): \(C(B_0^0,t) := B_0^1 B_1^1\).
\text{}\\
\input{algo2/algo_de-casteljau}


\subsection{Der Algorithmus von Lane und Riesenfeld (LR-Algorithmus)}
Dient dazu, stückweise polynomielle Kurven (Splines) zu erzeugen. Dazu erzeugt er wie der \textit{de Casteljau-Algorithmus} eine Folge von Polygonen(Kontrollpolygone), welche den Grenzwert der Folge(Limeskurve) definieren.

Im Gegensatz zum \textit{de Casteljau-Algorithmus} wird der \textit{LR-Algorithmus} meist für biinfinite Kontrollpolygone \(c_\mathbb{Z} := (c_i)_{i \in \mathbb{Z}} = (...,c_{-1},c_0,c_1,...)\) beschrieben. Hierbei können endliche Polygone als biinfinite aufgefasst werden, bei denen nur endlich viele Kontrollpunkte \(c_i\) von \(\mathbb{D}\) verschieden sind.
\text{}\\
\input{algo2/algo_lr}


\subsection{Naive Textsuche}
Im Folgenden ist \(A\) ein Alphabet, \(t = t_1,...,t_n \in A^n\) ein Text und \(s = s_1,...,s_m \in A^m\) mit \(m<n\) ein Suchtext.

Der einfachste Algorithmus besteht darin, ein so genanntes Suchfenster von der Länge der Suchmaske über den Text zu schieben. In jeder Position der Suchmaske werden die Symbole der Maske mit denen des darunterliegenden Textes verglichen. Wenn ein nicht übereinstimmendes Symbol gefunden wird, wird das Fenster um eine Position verschoben, und erneut ein Vergleich angestellt; wenn alle Symbole im Fenster übereinstimmen, ist die Suchmaske gefunden worden. Der Algorithmus endet, wenn der ganze Text vom Fenster abgesucht worden ist.\footnote{\url{http://de.wikipedia.org/wiki/String-Matching-Algorithmus\#Naiver_Algorithmus}}
\text{}\\
\input{algo2/algo_naive-textsuche}

Laufzeit in \(\mathcal{O}(n\cdot m)\), wenn der ganze Text abgesucht werden muss.

\subsection{Algorithmus von Boyer und Moore}
Das Muster wird am Anfang linksbündig unter den Text geschrieben und dann von rechts nach links Zeichen für Zeichen mit dem Text verglichen. Sobald ein Mismatch auftritt, berechnen zwei Heuristiken, wie weit das Suchmuster nach rechts verschoben werden kann.\footnote{\url{http://de.wikipedia.org/wiki/Boyer-Moore-Algorithmus}}

Es kommt vor, dass die beiden Heuristiken unterschiedliche Verschiebungen berechnen. Der Algorithmus wählt immer das Maximum der beiden Vorschläge, um das Muster nach rechts zu verschieben.
\text{}\\
\input{algo2/algo_boyer-moore}

\subsubsection{Vorkommensfunktion}
Im Naiven Algorithmus wird der Suchtext, wenn er nicht übereinstimmt, immer um eine Stelle weitergeschoben, dies kann man verbessern wenn man die Position \(\nu\) kennt an der ein Zeichen a im Suchtext s zuletzt vorkommt vorkommt (oder falls es gar nicht vorkommt gilt \(nu(a) = 0)\).

\(\nu(a) = min\{k|a \notin s_{k+1},...,s_m\}\) und \(a = s_k \lor k = 0\)

\subsubsection{Bad-Character-Heuristik}
Stimmt beim Vergleich des Musters mit dem Text von rechts nach links ein Zeichen des Musters nicht mit dem Zeichen des Textes überein („Bad-Character“), wird im Muster nach dem letzten Vorkommen dieses Bad-Characters gesucht und das Muster soweit verschoben, bis beide Buchstaben übereinander liegen. Existiert dieser Bad-Character nicht im Muster, wird das Muster um seine volle Länge nach rechts verschoben. Es kann vorkommen, dass die Bad-Character-Heuristik eine Verschiebung des Musters nach links vorschlägt. In diesem Fall wird um eine Position nach rechts geschoben.

Der Boyer-Moore-Algorithmus arbeitet am effizientesten, wenn er ein Zeichen vorfindet, das im Suchmuster nicht vorkommt. Die Bad-Character-Regel kommt dann zum Tragen. Dies ist sehr wahrscheinlich bei einem relativ kleinen Muster und einem großen Alphabet, was ihn für einen solchen Fall besonders geeignet macht. In diesem Fall arbeitet der Algorithmus mit einer Effizienz von \(\mathcal{O}(\frac{n}{m})\) Vergleichen.

\subsubsection{Good-Suffix-Heuristik}
Stimmt beim Vergleich des Musters mit dem Text von rechts nach links ein Suffix des Musters mit dem Text überein und tritt danach aber ein Mismatch auf, wird das Muster soweit nach rechts geschoben, bis ein Teilwort des Musters wieder auf das Suffix passt. Existiert das Suffix kein zweites Mal im Muster, wird das Muster um seine volle Länge nach rechts verschoben.

\subsubsection{Vorberechnung des größten, echten Präsuffixes pro Zeichen im Suchwort}
Ein Präfix eines Wortes \(w\), das zugleich ein Suffix von \(w\) ist, nennen wir \textit{Präsuffix} von \(w\). Weiter sei \(\gamma(j) := | geps(w_j)|\).
\text{}\\
\input{algo2/algo_boyer-moore_gamma}

\subsubsection{Berechnung der Heuristik}
Die Heuristik berechnet für jedes Zeichen des Suchworts, wie weit dieses verschoben werden kann. Grundlage ist dabei die Gamma-Funktion, welche für jedes Zeichen des Suchworts die Länge des größten, echten Präsuffixes angibt.
\text{}\\
\input{algo2/algo_boyer-moore_sigma}