From: Florian Forster <octo@leeloo.octo.it>
Date: Mon, 21 Feb 2011 07:39:58 +0000 (+0100)
Subject: Motivation: Mal weng was geschrieben.
X-Git-Url: https://git.octo.it/?p=diplomarbeit.git;a=commitdiff_plain;h=000fbb9bcc639c35182711183d50d0cc46916aee

Motivation: Mal weng was geschrieben.
---

diff --git a/diplomarbeit.tex b/diplomarbeit.tex
index c4ac165..7dce1ff 100644
--- a/diplomarbeit.tex
+++ b/diplomarbeit.tex
@@ -81,6 +81,8 @@
 
 \maketitle
 \begin{abstract}
+\todo{Einleitung schreiben.}
+
 Sortiernetzwerke werden eingeführt und einige bekannte Konstruktionen werden
 vorgestellt (Odd-Even-Transposition, Bitonic-Merge, Odd-Even-Merge, Pairwise).
 Transformationsmöglichkeiten für Sortiernetzwerke werden besprochen.
@@ -99,13 +101,35 @@ das hinbekomme bzw. Recht behalte.}
 
 \subsection{Motivation}\label{sect:motivation}
 
-\todo{Schreibe noch etwas zu …}
-\begin{itemize}
-\item Sortiernetzwerke sind toll, weil $\ldots$
-\item Sortiernetzwerke sind einfach erklärt, aber trotzdem kompliziert.
-\item Bisher noch kein evolutionärer Algorithmus zur automatischen
-  Optimierung von Sortiernetzwerken bekannt. \textit{(Glaube ich zumindest.)}
-\end{itemize}
+\emph{Sortiernetzwerke} sind ein theoretisches Konstrukt, dass auch von
+Personen ohne Zugang zum Thema beziehungsweise der theoretischen Informatik
+schnell verstanden werden kann. Eine Einführung wird in
+Abschnitt~\ref{sect:einleitung_sortiernetzwerke} gegeben. Nichtsdestotrotz ist
+das Finden von Sortiernetzwerken sowie das Beweisen, dass ein
+Komparatornetzwerk jede beliegibe Eingabe sortiert, im Allgemeinen sehr
+schwierig und nach heutigem Kenntnisstand nur mit exponentiellem Aufwand zu
+bewältigen.
+
+Einfacher ist der Korrektheitsbeweis bei konstruktiven Verfahren, da hier die
+Konstruktionsvorschrift genutzt werden kann um die Korrektheit für beliebige
+Eingabegrößen zu beweisen. Im Abschnitt~\ref{sect:konstruktive_netzwerke}
+geschieht dies beispielsweise für zwei von \emph{Kenneth~E. Batcher} 1968
+gefundenen Konstruktionsvorschriften.
+
+Um effiziente und schnelle Sortiernetzwerke zu finden, wurden schon früh
+Computer und automatische Suchverfahren eingesetzt. Bisherige Ansätze
+versuchen meist, in der Menge aller Komparatornetzwerke jene zu finden, die
+die Sortiereigenschaft besitzen und aus wenigen Komparatoren bestehen. Die
+Eigenschaft, jede Eingabepermutation zu sortieren, ist also ein
+Optimierungsziel und nicht durch das Vorgehen gewährleistet. Dafür können
+theoretisch alle Sortiernetzwerke durch diese Algorithmen gefunden werden --
+genügend Laufzeit vorausgesetzt.
+
+In dieser Arbeit werden Methoden verwendet, die die Menge der Sortiernetzwerke
+nie verlassen, dafür aber auch nicht alle existierenden Sortiernetzwerke
+erzeugen können. So muss für ein gefundenes Komparatornetzwerk nicht mehr
+nachgewiesen werden, dass es jede beliebige Eingabe sortiert, weil diese
+Eigenschaft durch das Verfahren sichergestellt ist.
 
 \subsection{Einleitung}\label{sect:einleitung}