From 0d8ad84d3a94cc18581337be5177f4319b7502b8 Mon Sep 17 00:00:00 2001 From: Florian Forster Date: Sun, 27 Feb 2011 10:05:53 +0100 Subject: [PATCH] =?utf8?q?Einleitung:=20Formulierung=20bzgl.=20Komplexit?= =?utf8?q?=C3=A4t=20=C3=BCberarbeitet.?= MIME-Version: 1.0 Content-Type: text/plain; charset=utf8 Content-Transfer-Encoding: 8bit --- diplomarbeit.tex | 51 +++++++++++++++++++++++++++++---------------------- 1 file changed, 29 insertions(+), 22 deletions(-) diff --git a/diplomarbeit.tex b/diplomarbeit.tex index 6a77ae3..0e86f73 100644 --- a/diplomarbeit.tex +++ b/diplomarbeit.tex @@ -232,8 +232,8 @@ Sortiereigenschaft \emph{nicht} besitzt, da es in diesem Fall die Folge $(1, Insgesamt gibt es $n!$~Permutationen von $n$~Elementen. Wenn ein Komparatornetzwerk die Sortiereigenschaft besitzt, bildet es alle diese Permutationen auf die sortierte Reihenfolge ab. Allerdings wächst $n!$ -über-exponentiell schnell, so dass ein Ausprobieren aller möglichen -Permutationen schon bei 16~Leitungen praktisch nicht mehr zu bewerkstelligen +so schnell, dass ein Ausprobieren aller möglichen Permutationen schon bei +16~Leitungen praktisch nicht mehr zu bewerkstelligen ist.\footnote{1.307.674.368.000 Permutationen} \label{sect:0-1-prinzip} @@ -260,26 +260,33 @@ Verhalten jedes einzelnen Komparators nicht: Wenn bei der Permutation eine Zahl größer als $a_i$ und eine Zahl kleiner oder gleich $a_i$ verglichen wurden, liegen jetzt entsprechend eine Null und eine Eins an, die genauso vertauscht werden oder nicht, wie das bei der Permutation der Fall war. Liegen -zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als $a_i$ -oder zwei Zahlen größer oder gleich $a_i$. Da im Fall der 0-1-Folge zwei -gleiche Zahlen am Komparator anliegen, dürfen wir davon ausgehen, dass sich -der Komparator so verhält, wie er sich bei der Permutation verhalten hat -- -ohne das Ergebnis zu beeinflussen. Entsprechend kommen an den Ausgängen $i-1$ -und $i$ eine Null und eine Eins in der falschen Reihenfolge an. Das steht im -Widerspruch zu der Annahme, dass alle 0-1-Folgen sortiert werden. - -Im Gegensatz zum Überprüfen aller möglichen Permutationen, was der -Komplexitätsklasse -$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ zuzuordnen ist, -ist das Überprüfen aller 0-1-Folgen „nur“ mit dem Aufwand $\Theta(2^n)$ -verbunden. Entsprechend ist dieses Verfahren nicht \emph{effizient} -- ein -schnelleres Verfahren ist bisher allerdings nicht bekannt. Um zu überprüfen, -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~Milliarden Tests notwendig, die einen Rechner durchaus mehrere Minuten -beschäftigen. +zwei Nullen oder zwei Einsen an, entsprechen sie zwei Zahlen kleiner als +$a_i$, beziehungsweise zwei Zahlen größer oder gleich $a_i$. Da im Fall der +0-1-Folge zwei gleiche Zahlen am Komparator anliegen, dürfen wir davon +ausgehen, dass sich der Komparator so verhält, wie er sich bei der Permutation +verhalten hat -- ohne das Ergebnis zu beeinflussen. Entsprechend müssen an den +Ausgängen $i-1$ und $i$ eine Null und eine Eins in der falschen Reihenfolge +ankommen. Das steht im Widerspruch zu der Annahme, dass alle 0-1-Folgen +sortiert werden. + +Im Gegensatz zum Überprüfen aller möglichen Permutationen, was mit dem Aufwand +$\Theta\left(\sqrt{n}\left(\frac{n}{e}\right)^n\right)$ verbunden ist, besitzt +das Überprüfen aller 0-1-Folgen „nur“ den Aufwand $\Theta(2^n)$. Entsprechend +ist dieses Verfahren nicht \emph{effizient} -- ein schnelleres Verfahren ist +bisher allerdings nicht bekannt. + +Um zu überprüfen, 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~Milliarden Tests notwendig, die einen Rechner durchaus +mehrere Minuten beschäftigen. Das ist deshalb problematisch, weil die im +Folgenden vorgestellten \emph{Evolutionären Algorithmen} eine entsprechende +Überprüfung in jeder Iteration durchführen müssten. Wenn die Überprüfung eines +Zwischenergebnisses fünf Minuten in Anspruch nimmt, sind für eine Million +Iterationen fast zehn Jahre Rechenzeit notwendig. Selbst wenn die Berechnung +auf 1000~Computern mit je 4~Prozessoren verteilt wird, werden über 20~Stunden +für einen Lauf benötigt. \subsubsection{Evolutionäre Algorithmen} -- 2.11.0