From 7bf98129333863afbc3a50bc164d505a8e1e2faf Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Mon, 21 Feb 2011 12:45:58 +0100 Subject: [PATCH] Viele Tippfehler entfernt. --- diplomarbeit.tex | 108 +++++++++++++++++++++++++++---------------------------- 1 file changed, 54 insertions(+), 54 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index f9b0caa..d4b14e7 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -90,7 +90,7 @@ Evolutionäre Algorithmen werden beschrieben und ein evolutionärer Algorithmus für die Optimierung von Sortiernetzwerken wird angegeben. Die mindestens von diesem Algorithmus erreichte Güte wird angegeben und die Transformation zu einer Markov-Kette wird gezeigt. {\em Natürlich: So fern ich -das hinbekomme bzw. Recht behalte.} +das hin bekomme bzw. Recht behalte.} \end{abstract} \newpage @@ -106,7 +106,7 @@ 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 +Komparatornetzwerk jede beliebige Eingabe sortiert, im Allgemeinen sehr schwierig und nach heutigem Kenntnisstand nur mit exponentiellem Aufwand zu bewältigen. @@ -161,11 +161,11 @@ verschiedene Eingänge und vier Ausgänge. Die Ein- und Ausgänge werden durch eine horizontale Linie dargestellt und als \emph{Leitung} bezeichnet. Die \emph{Komparatoren} sind durch vertikale Pfeile dargestellt und verbinden je zwei verschiedene \emph{Leitungen} miteinander. Die Verbindungsstellen von -\emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichlichkeit +\emph{Leitungen} und \emph{Komparatoren} sind zur besseren Übersichtlichkeit durch schwarze Punkte symbolisiert. Auf der linken Seite befinden sich die Eingänge. Hier wird eine Zahlenfolge in -das Netzwerk hineingegeben. Jeder Komparator vergleicht die Zahlen „auf“ den +das Netzwerk hinein gegeben. Jeder Komparator vergleicht die Zahlen „auf“ den beiden Leitungen, die er verbindet. Nach einem Komparator befindet sich die kleinere Zahl immer auf der Leitung, auf die der Pfeil zeigt, die größere Zahl befindet sich auf der Leitung, auf der der Pfeil seinen Ursprung hat. @@ -175,7 +175,7 @@ gleichzeitig angewandt werden. Das Beispiel in Abbildung~\ref{fig:einfaches_komparatornetzwerk} verwendet diesen Umstand und vergleicht die zwei oberen und die zwei unteren Leitungen gleichzeitig. Eine Gruppe von Komparatoren, die gleichzeitig angewendet werden können, nennt man -eine \emph{Schicht} des Komparatornetwerks. Die \emph{Verzögerung} eines +eine \emph{Schicht} des Komparatornetzwerks. Die \emph{Verzögerung} eines Komparatornetzwerks ist gleichbedeutend mit der Anzahl der Schichten, in die sich die Komparatoren mindestens gruppieren lassen, da sie die Anzahl der benötigten parallelen Schritte darstellt. @@ -184,7 +184,7 @@ benötigten parallelen Schritte darstellt. erzeugen, die der Sortierung der Eingabe entspricht, heißen \emph{Sortiernetzwerke}. Das in Abbildung~\ref{fig:einfaches_komparatornetzwerk} gezeigte Komparatornetzwerk -ist \emph{kein} Sotiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur +ist \emph{kein} Sortiernetzwerk: Die Eingabefolge ${(1, 2, 3, 4)}$ führt zur Ausgabe ${(2, 1, 3, 4)}$ -- die bestehenden Sortierung wird also sogar zerstört. @@ -263,7 +263,7 @@ ob ein Komparatornetzwerk mit 16~Leitungen die Sortiereigenschaft besitzt, sind mit dieser Methode nur 65.536 Tests notwendig -- eine Zahl, die für aktuelle Prozessoren keine Herausforderung darstellt. Für die Überprüfung eines Komparatornetzwerks mit 32~Leitungen sind jedoch bereits etwa -4,3~Millarden Tests notwendig, die einen Rechner durchaus mehrere Minuten +4,3~Milliarden Tests notwendig, die einen Rechner durchaus mehrere Minuten beschäftigen. \subsubsection{Evolutionäre Algorithmen} @@ -282,9 +282,9 @@ gefunden werden. Aus diesem Grund besteht die Notwendigkeit einen Kompromiss einzugehen: Statt die beziehungsweise eine der {\em optimalen} Lösungen als einzige Ausgabe des Algorithmus zuzulassen, wird eine "`möglichst gute"' Lösung ausgegeben. Viele -dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur, -beispielsweise imitieren die "`Ameisenalgorithmen"' das Verhalten von Ameisen -auf der Futtersuche um kurze Rundreisen auf Graphen zu berechnen. +dieser Optimierungsalgorithmen orientieren sich an Vorgängen in der Natur. +Beispielsweise imitieren die „Ameisenalgorithmen“ das Verhalten von Ameisen +auf der Futtersuche, um kurze Rundreisen auf Graphen zu berechnen. Bei {\em Evolutionären Algorithmen} stand die Evolution pate. Die Grundidee ist, bekannte Lösungen zu neuen -- unter Umständen besseren -- Lösungen zu @@ -366,7 +366,7 @@ Evolutionäre Algorithmen wurden bereits mehrfach eingesetzt, um Sortiernetzwerke zu untersuchen. \textit{W.~Daniel Hillis} verwendete \emph{Co-Evolution} um neben Komparatornetzwerken auch „schwierige Eingaben“ zu optimieren~\cite{H1992}. Diese \emph{Parasiten} genannten Eingaben wurden -daran gemessen, bei wievielen Komparatornetzwerken sie beweisen konnten, dass +daran gemessen, bei wie vielen Komparatornetzwerken sie beweisen konnten, dass sie keine Sortiernetzwerke sind. So mussten bei neuen Individuen~/ Komparatornetzwerken nicht alle 0-1-Folgen, sondern nur erfolgreiche Parasiten~/ schwierige Eingaben überprüft werden. Auf diese Art und Weise @@ -388,7 +388,7 @@ einen \emph{Evolutionären Algorithmus}, wie sie hier vorgestellt wurden, sondern um eine verteilte, probabilistische Breitensuche, die an die \emph{Strahlsuche} (englisch: \textit{beam search}), ein Verfahren der Künstlichen Intelligenz, angelehnt ist. Die aufwendigste Operation bei diesem -Ansatz ist die Bewertungsfunktion, die abschätzt, wieviele Komparatoren zu +Ansatz ist die Bewertungsfunktion, die abschätzt, wie viele Komparatoren zu einem Komparatornetzwerk hinzugefügt werden müssen, um ein Sortiernetzwerk zu erhalten. Mit diesem Ansatz gelang es \textit{Juillé} zwei 13-Sortiernetzwerke anzugeben, die mit 45~Komparatoren effizienter sind als alle bis dahin @@ -419,11 +419,11 @@ ${n = 8}$ Leitungen. \label{fig:odd-even-transposition-08} \end{figure} -Dass das Odd-Even-Transporitionsort-Netzwerk tatsächlich jede beliegibe +Dass das Odd-Even-Transpositionsort-Netzwerk tatsächlich jede beliebige Eingabe sortiert ist nicht offensichtlich. Leicht zu sehen ist jedoch, dass sowohl das Minimum als auch das Maximum durch das im Netzwerk enthaltene Treppenmuster auf die unterste beziehungsweise oberste Leitung gelangt. Beim -Odd-Even-Transporitionsort-Netzwerk mit drei Eingängen, +Odd-Even-Transpositionsort-Netzwerk mit drei Eingängen, $\operatorname{OET}(3)$, ist die Ausgabe folglich sortiert. Die Sortiereigenschaft größerer OET-Netzwerke lässt sich rekursiv beweisen, @@ -433,7 +433,7 @@ Abschnitt~\ref{sect:leitungen_entfernen} wird das Vorgehen im Detail beschrieben, Abbildung~\ref{fig:oe-transposition-cut} zeigt das Herausschneiden einer Leitung aus $\operatorname{OET}(8)$. -Das Odd-Even-Transporitionsort-Netzwerk ist weder in Bezug auf die Anzahl der +Das Odd-Even-Transpositionsort-Netzwerk ist weder in Bezug auf die Anzahl der Komparatoren noch in Bezug auf die Anzahl der Schichten, in denen sich die Komparatoren anordnen lassen, effizient. Es benötigt ${\frac12 n (n-1)} = \mathcal{O}(n^2)$~Komparatoren, die in $n$~Schichten @@ -541,7 +541,7 @@ Der bitonen Mischer kann auch zwei aufsteigende Folgen sortieren. Dazu ist lediglich eine etwas modifizierte Vergleichs-Kaskade im ersten Schritt notwendig. Die folgenden, kleineren Mischer erhalten als Eingabe wieder eine „echte“ bitone Folge. Abbildung~\ref{fig:bitonic-merge-tricheter} zeigt das -Schema des bitonen Mischers für zwei aufsteigend sortierte Foglen. Durch das +Schema des bitonen Mischers für zwei aufsteigend sortierte Folgen. Durch das Umdrehen einer Folge verändert sich das Muster der Komparatoren ein wenig: Statt an eine Treppe erinnert das Muster nun an einen Trichter. @@ -605,7 +605,7 @@ darin, dass es ebenfalls rekursiv durch einen Mischer definiert ist. \subsubsection{Der \emph{Odd-Even}-Mischer}\label{sect:der_odd_even_mischer} Der \emph{Odd-Even}-Mischer $\operatorname{OEM}(n,m)$ ist ein -Komperatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$ +Komparatornetzwerk, dass zwei sortierte Folgen mit $n$ beziehungsweise $m$ Elementen zu einer sortierten Ausgabefolge mit $N = n+m$~Elementen zusammenfügen kann. Dabei kommt es mit weniger Vergleichen aus als der \emph{bitone Mischer}, der im Abschnitt~\ref{sect:der_bitone_mischer} @@ -631,7 +631,7 @@ w_i = \left\{ \begin{array}{ll} \end{center} \caption{Schematischer Aufbau des {\em Odd-Even} Mischers. Im Vergleich zum bitonen Mischer für Acht kommt dieses Schema mit einem Komparator weniger - aus. Der Effekt wird duch den rekursiven Aufbau noch verstärkt.} + aus. Der Effekt wird durch den rekursiven Aufbau noch verstärkt.} \label{fig:oe-merge} \end{figure} @@ -696,7 +696,7 @@ $W_{\textrm{gerade}}$ und $W_{\textrm{ungerade}}$ entsprechend zu: Daraus folgt, dass $W_{\textrm{gerade}}$ $0$, $1$ oder $2$ Nullen mehr enthält als $W_{\textrm{ungerade}}$. In den ersten beiden Fällen ist die "`verzahnte"' Ausgabe der beiden kleineren Mischer bereits sortiert. Nur im letzten Fall, -wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthählt als +wenn $W_{\textrm{gerade}}$ zwei Nullen mehr enthält als $W_{\textrm{ungerade}}$, muss genau eine Vertauschung stattfinden, um die Ausgabe zu sortieren. Diese wird von den Komparatoren, die benachbarte Leitungen miteinander vergleichen, ausgeführt. Die jeweiligen Situationen sind @@ -875,7 +875,7 @@ Definition. In Abbildung~\ref{fig:bitonic-std} ist die normalisierte Version des bitonen Mergesort-Netzwerks zu sehen. Alle Komparatoren zeigen hier in die gleiche -Richtung. Statt dem typischen "`Treppenmuster"' sind abwechselnd das Treppen- +Richtung. Statt dem typischen „Treppenmuster“ sind abwechselnd das Treppen- und das Trichtermuster zu sehen. \subsection{Zwei Netzwerke kombinieren} @@ -941,12 +941,12 @@ Sortiernetzwerk mit $n$~Eingängen erhalten müssen. Man kann ein gegebenes Sortiernetzwerk mit $n$~Eingängen auf ein Sortiernetzwerk mit ${n-1}$~Leitungen verkleinern, indem man eine Leitung „eliminiert“. Dazu nehmen wir an, dass das Minimum oder das Maximum an einem -bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das Maxim -durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an einem der -„Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten Index. -Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und welche -dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum jeden -Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die +bestimmten Eingang anliegt. Der Weg, den das Minimum beziehungsweise das +Maximum durch das Sortiernetzwerk nimmt, ist eindeutig bestimmt und endet an +einem der „Ränder“, also auf der Leitung mit dem höchsten oder dem niedrigsten +Index. Insbesondere ist bekannt, welche Komparatoren „berührt“ werden und +welche dafür sorgen, dass der Wert die Leitung gewechselt, da das Minimum +jeden Vergleich „verliert“ und das Maximum jeden Vergleich „gewinnt“. Die Abbildung~\ref{fig:oe-transposition-cut0} zeigt den Weg eines Maximums durch das {\em Odd-Even-Transpositionsort-Netzwerk}. @@ -954,7 +954,7 @@ das {\em Odd-Even-Transpositionsort-Netzwerk}. \centering \subfigure[Auf der Leitung~4 wird $-\infty$ angelegt. Dadurch ist der Pfad durch das Sortiernetzwerk eindeutig festgelegt.]{\input{images/oe-transposition-cut0.tex}\label{fig:oe-transposition-cut0}} - \subfigure[Komparatoren, die einen wechsel der Leitungen bewirken, werden + \subfigure[Komparatoren, die einen Wechsel der Leitungen bewirken, werden durch sich kreuzende Leitungen ersetzt.]{\input{images/oe-transposition-cut1.tex}\label{fig:oe-transposition-cut1}} \subfigure[Leitung~4 wurde entfernt. Übrig bleibt ein Sortiernetzwerk mit 7~Leitungen.]{\input{images/oe-transposition-cut2.tex}\label{fig:oe-transposition-cut2}} @@ -965,7 +965,7 @@ das {\em Odd-Even-Transpositionsort-Netzwerk}. markierten Leitung wird $-\infty$ angelegt. Da der Wert bei jedem Komparator am unteren Ende herauskommt, ist der Pfad fest vorgegeben. Da die restlichen Werte trotzdem noch richtig sortiert werden müssen, kann dieser Pfad - herausgetrennt werden. In der letzten Abbildung ist \oet{7} markiert.} + heraus getrennt werden. In der letzten Abbildung ist \oet{7} markiert.} \label{fig:oe-transposition-cut} \end{figure} @@ -980,10 +980,10 @@ auf die keine Komparatoren mehr berührt (Abbildung~\ref{fig:oe-transposition-cut1}). Die Werte auf den verbleibenden $(n-1)$~Leitungen müssen vom restlichen -Komparatornetzwerk immernoch sortiert werden: Wir haben lediglich die Position -des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss die -Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum liegt. -Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme +Komparatornetzwerk immer noch sortiert werden: Wir haben lediglich die +Position des Minimums oder des Maximums angenommen. Ein Sortiernetzwerk muss +die Eingabe sortieren, egal auf welcher Leitung das Minimum~/ das Maximum +liegt. Wir haben lediglich angefangen, das Sortiernetzwerk unter diese Annahme auszuwerten -- über die verbleibenden Eingänge haben wir keine Aussage getroffen. Entsprechend müssen die verbleibenden Ausgänge eine sortierte Liste mit $(n-1)$~Elementen darstellen. @@ -998,7 +998,7 @@ einer Leitung als \emph{Minimum-Schnitt} beziehungsweise Die letzte Abbildung, \ref{fig:oe-transposition-cut3}, zeigt das Sortiernetzwerk wieder mit den üblichen geraden Leitungen und die rot markierten Komparatoren wurden verschoben, so dass sich eine kompaktere -Darstellung ergibt. Ausserdem ist das +Darstellung ergibt. Außerdem ist das \emph{Odd-Even-Transpositionsort}-Netzwerk für sieben Werte markiert. Der zusätzliche Komparator vor dem \oet{7} hat keinen Einfluss auf die Ausgabe und kann entfernt werden. @@ -1056,7 +1056,7 @@ Schnittmuster: Die Anzahl der möglichen Schnittmuster wird mit der Anzahl der zu entfernenden Leitungen sehr schnell sehr groß. Um ein Sortiernetzwerk mit 32~Eingängen auf -ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schmittmuster mit +ein Sortiernetzwerk mit 16~Eingängen zu reduzieren, ist ein Schnittmuster mit 16~Schnitten notwendig, für das es bereits etwa ${3,939 \cdot 10^{13}}$ Möglichkeiten gibt. Ein Ausprobieren aller Möglichkeiten ist für große Netzwerke nicht oder nur unter erheblichem Ressourcenaufwand möglich. @@ -1070,7 +1070,7 @@ der gleiche Wert angelegt wird, und sechs Konfigurationen, bei denen sich die Werte unterscheiden. Bei diesen letzten sechs Konfigurationen werden je zwei auf das selbe -Ausgangmuster abgebildet, weil die Position des Minimums beziehungsweise des +Ausgangsmuster abgebildet, weil die Position des Minimums beziehungsweise des Maximums durch den Komparator vorgegeben wird. Das heißt, dass die neun unterschiedlichen Eingangsmuster nur sechs unterschiedliche Ausgangsmuster erzeugen. In der zweiten und allen folgenden Schichten kann man diesen @@ -1135,14 +1135,14 @@ $k$~unterschiedlichen Schnittmustern. Anschließend werden $n$~Schnittmuster zufällig erzeugt und überprüft, ob sie in der Menge~$S$ enthalten sind. Unter der Annahme, dass das Verhältnis der zufälligen Schnittmuster, die in $S$ enthalten sind, und $n$ dem Verhältnis von $k$ und der Anzahl der -unterschiedlichen Schnittmuster ingesamt entspricht, kann man die Anzahl der +unterschiedlichen Schnittmuster insgesamt entspricht, kann man die Anzahl der unterschiedlichen Schnittmuster abschätzen. \begin{figure} \begin{center} \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-10000-1000000-32.pdf} \end{center} - \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der + \caption{Abschätzung der unterschiedlichen Schnittmuster mit der \emph{Monte-Carlo-Methode} für $\operatorname{OES}(32)$ und $\operatorname{BS}(32)$.} \label{fig:collisions-10000-1000000-32} @@ -1164,7 +1164,7 @@ und $3,4 \cdot 10^6$ für $\operatorname{BS}(32)$. \begin{center} \includegraphics[viewport=0 0 425 262,width=15cm]{images/collisions-100000-1000000-32-ps.pdf} \end{center} - \caption{Abschnätzung der unterschiedlichen Schnittmuster mit der + \caption{Abschätzung der unterschiedlichen Schnittmuster mit der \emph{Monte-Carlo-Methode} für $\operatorname{PS}(32)$. 385 von 1.000.000 zufälligen Schnittmustern waren äquivalent zu einem Schnittmuster in einer Menge von 100.000. Daraus ergibt sich eine Schätzung von $2,6 \cdot 10^8$ @@ -1182,12 +1182,12 @@ Anzahl für $\operatorname{OES}(16)$ beziehungsweise $\operatorname{BS}(16)$, ist dieser Umstand wenig verwunderlich. Entsprechend hätte man in einem kombinierten Graphen keine Details mehr erkennen können. Aufgrund der hohen Anzahl unterschiedlicher Schnittmuster, wurde für das gleiche Experiment mit -$\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedilchen +$\operatorname{PS}(32)$ eine initiale Menge von 100.000 unterschiedlichen Schnittmustern erzeugt. Trotzdem wurden nach 1.000.000 Iterationen nur 385 Schnittmuster gefunden, die zu einem Schnittmuster in der Menge äquivalent sind. Daraus ergibt sich eine Abschätzung von $2,6 \cdot 10^8$ unterschiedlichen Schnittmustern -- zwei Zehnerpotenzen mehr als bei den -vorherigen Sortiernetzwerken, aber immernoch fünf Zehnerpotenzen kleiner als +vorherigen Sortiernetzwerken, aber immer noch fünf Zehnerpotenzen kleiner als die Anzahl der \emph{möglichen} Schnittmuster. \newpage @@ -1204,7 +1204,7 @@ in Abschnitt~\ref{sect:bewertung} behandelt. \subsection{Bewertungsfunktion}\label{sect:bewertung} Um Sortiernetzwerke überhaupt optimieren zu können, muss zunächst die -{\em Güte} eines Netzwerkes definiert werden. Prinzipiell gibt es zwei Ziele, +{\em Güte} eines Netzwerks definiert werden. Prinzipiell gibt es zwei Ziele, die bei Sortiernetzwerken verfolgt werden können: \begin{itemize} \item Möglichst wenige Komparatoren („effizient“) @@ -1316,7 +1316,7 @@ eine Überprüfung eingebaut: Unmittelbar vor dem Einfügen in die Population wird nacheinander jeder Komparator entfernt und überprüft, ob das verbleibende Netzwerk die Sortiereigenschaft noch besitzt. -Trotz des hohen Rechenaufwandes -- bei 16-Sortiernetzwerken sind gut +Trotz des hohen Rechenaufwands -- bei 16-Sortiernetzwerken sind gut 4~Millionen Tests notwendig, um alle Komparatoren zu überprüfen -- waren die Ergebnisse ernüchternd: Nach circa 1~Million Iterationen mit 16-Sortiernetzwerken fand der so modifizierte Algorithmus keinen einzigen @@ -1436,8 +1436,8 @@ Um zwei Individuen zu rekombinieren werden die ersten $r$~Schnitte des einen Schnittmusters verwendet und die letzten ${c-r}$~Schnitte des zweiten Schmittmusters. $r$ ist eine Zufallsvariable mit $0 \leqq r \leqq c$. -Die Mutation setzt entweder die Leitungs-Nummer eines Schnitts~$i$ zufällig -auf einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die +Die Mutation setzt entweder die Leitungsnummer eines Schnitts~$i$ zufällig auf +einen neuen Wert $l$ mit $0 \leqq l \le n-i$ oder invertiert die Schnitt-Richtung. \subsection{Versuche mit dem bitonen Mergesort-Netzwerk} @@ -1573,8 +1573,8 @@ Obwohl das \emph{Pairwise-Sorting-Netzwerk} den \emph{Odd-Even}-Mischer nicht einsetzt und auch nicht auf einem Mischer basiert, ist der $\operatorname{OEM}(8,8)$ im Sortiernetzwerk in Abbildung~\ref{fig:16-ec-from-ps32} eindeutig erkennbar (Schichten~7--10). In -den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzerke, die -strukturell identisch zu $\operatorname{PS}(8)$ sind -- lediglich die +den Schichten~1--6 erkennt man zwei unabhängige Sortiernetzwerke, die +strukturell sehr ähnlich zu $\operatorname{PS}(8)$ sind -- lediglich die Schichten~1 und~2 sowie 4~und~5 sind vertauscht. \begin{figure} @@ -1622,7 +1622,7 @@ $\operatorname{PS}(16)$ anwendet: In diesem Fall kann man durch ein 8-Schnittmuster das \emph{Odd-Even-Mergesort}-Netzwerk \oes{8} erhalten. Für größere Sortiernetzwerke ist dies hingegen nicht mehr möglich, beispielsweise kann $\operatorname{PS}(32)$ nicht durch ein 16-Schnittmuster in \oes{16} -konvertiert werden. Die Verwandschaft von $\operatorname{PS}(n)$ und \oes{n} +konvertiert werden. Die Verwandtschaft von $\operatorname{PS}(n)$ und \oes{n} untersucht \textit{Moritz Mühlenthaler} ausführlich in~\cite{M2009}. \subsection{Versuche mit dem Odd-Even-Mergesort-Netzwerk} @@ -1716,11 +1716,11 @@ Die Graphen in Abbildung~\ref{fig:markov-comparators} zeigen die Anzahl der Komparatoren der Sortiernetzwerke, die \textsc{SN-Markov} auf seinem zufälligen Pfad durchläuft (rot). Für jeden Graphen wurde der \textsc{SN-Markov}-Algorithmus auf einem entsprechenden -\emph{Odd-Even-Transporitionsort}-Netzwerk gestartet hat mindestens +\emph{Odd-Even-Transpositionsort}-Netzwerk gestartet hat mindestens 1.000.000~Iterationen durchlaufen. In jedem Schritt wurde die Anzahl der Komparatoren des Sortiernetzwerks bestimmt und ein entsprechender Zähler erhöht. In Abbildung~\ref{fig:markov-comparators} ist die resultierende -prezenturale Verteilung zu sehen. +prozentuale Verteilung zu sehen. Ebenfalls in die Graphen in Abbildung~\ref{fig:markov-comparators} eingezeichnet ist eine \emph{Gamma-Verteilung} (grün), die die gemessenen @@ -1777,7 +1777,7 @@ Während nur $0,000017 \%$ der Individuen von \textsc{SN-Evolution} mit 63~Komparatoren auskamen, ist die Rate bei \textsc{SN-Markov} mit $0,000335 \%$ rund 20~mal höher. -Erwartunggemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem +Erwartungsgemäß sind die besten Netzwerke, die \textsc{SN-Evolution} mit dem \emph{bitonen Mischer} findet, aus 67~Komparatoren aufgebaut. Überraschend ist jedoch, dass in dieser Konfiguration Sortiernetzwerke auftreten können, die mehr Komparatoren besitzen als \emph{Odd-Even-Transpositionsort} -- \oet{16} @@ -1876,8 +1876,8 @@ Sortiernetzwerke mit $\frac{n}{2}$~Leitungen verwenden. Dies ließe sich für \textsc{SN-Evolution} nutzen, um zwei Individuen zu rekombinieren. Da es für das \emph{Pairwise-Sorting}-Netzwerk sehr viele -\emph{unterscheidliche} Schnittmuster gibt -(Abbschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die +\emph{unterschiedliche} Schnittmuster gibt +(Abschnitt~\ref{sect:anzahl_schnittmuster}), ist es möglich, dass die Verwendung dieser Rekombinationsmethode neue Ergebnisse ermöglicht. Leider wird die Aussicht auf Erfolg durch die Tatsache geschmälert, dass keine $n$-Schnittmuster für \ps{2n} gefunden werden konnten, die zu besseren @@ -1902,7 +1902,7 @@ funktionieren. In jeder Iteration wendet man alle oder eine zufällige Menge Schnittmuster auf das zusammengeführte Netzwerk an und gibt dem besten Ergebnis den Zuschlag. Anschließend erfährt das entsprechende Schnittmuster eine Aufwertung, so dass es wahrscheinlicher wird, dass \emph{dieses} -Schnittmuster zur nächten Generation beiträgt. Im Gegensatz zum Ansatz der +Schnittmuster zur nächsten Generation beiträgt. Im Gegensatz zum Ansatz der parasitären Eingaben entsteht eine \emph{Synergie} zweier Populationen, die das Gesamtergebnis oder zumindest die Konvergenzgeschwindigkeit verbessern könnte. @@ -1950,7 +1950,7 @@ Anwendung von Schnittmustern auf Sortiernetzwerke und Anwendung eines Komparatornetzwerks auf eine Eingabe-Permutation. \textit{libsortnetwork} kann unter der Web-Adresse -\url{http://octo.it/libsortnetwork/} unentgeldlich heruntergeladen werden. +\url{http://octo.it/libsortnetwork/} unentgeltlich heruntergeladen werden. \newpage \bibliography{references} -- 2.11.0