Probleme aus der Wissenschaft

aus ZUM-Wiki, dem Wiki für Lehr- und Lerninhalte auf ZUM.de
Wechseln zu: Navigation, Suche

Inhaltsverzeichnis

Sortiernetze

Das Sortieren von diversen Zahlenfolgen spielt eine zentrale Rolle in der Mathematik und insbesondere in der Informatik, wobei Sortiernetze als Sortierverfahren für dieses Anliegen notwendig sind.

Um diverse Zahlenfolgen zu sortieren wurden in der Mathematik einige Sortierverfahren entwickelt, welche das Sortieren von Daten mit Hilfe von Algorithmen ermöglichen, welche mit der Zeit optimiert und gerade für schnelle Prozesse in der Informatik erweitert wurden.

Allgemein entsteht ein Problem beim Sortieren von Zahlenfolgen, wenn lange Zahlenfolgen das Sortieren erschweren, sodass hierfür Mechanismen entwickelt wurden, welche das Sortieren nach bestimmten Schemata ermöglichen und das Sortieren somit auch mit Hilfe von technischen Geräten erleichtern.


Überlegungen zum Sortieren diverser Zahlenfolgen

Nun ist zu überlegen, wie eine Zahlenfolge, also eine Auflistung von fortlaufenden Zahlen, mit Hilfe mathematischer Mittel so sortiert werden kann, dass die kleinste Zahl nach dem Sortieren am Anfang der Folge steht und daraufhin jede folgende Zahl größer ist als die vorherige Zahl.

Als Beispiel betrachten wir uns die nun beschriebene Zahlenfolge, welche wir daraufhin systematisch sortieren möchten.

(3,1,2,4)

Nun könnte man die Zahlen wie beschrieben sortieren, indem man zwei Zahlen aus der Folge vergleicht und daraufhin entweder deren Positionen tauscht oder dies unterlässt.

Betrachten wir uns die ersten beiden Zahlen, so können wir feststellen, dass die Zahl 3 größer ist als die Zahl 1, woraufhin diese zum Sortieren vertauscht werden können, sodass wir daraufhin diese Folge erhalten.

(1,3,2,4)

Nun betrachten wir uns die Zahlen 3 und 2 und tauschen diese nach dem gleichen Prinzip aus.

(1,2,3,4)

Somit haben wir die Zahlenfolge systematisch sortiert.

Allgemein kann man eine Folge in dieser Weise formulieren.

Eine Folge ist eine Auflistung von Objekten, in unserem Fall Zahlen, welche mathematisch wie folgt ausgedrückt wird.

(a_1, a_2, a_3 ...., a_n)

Dabei steht der Buchstabe n für die Anzahl der Zahlen

Die Folge, welche soeben aufgelistet wurde, wird allgemein als die Folge ai dargestellt, wobei der Wert des Buchstaben i die Position der Zahl in der Folge wiedergibt.

In unserer Systematik sind wir wie folgt vorgegangen.

Ist die Zahl a1 größer als die Zahl a2, so tauschen wir die Zahlen in unserer Folge.

Damit können wir, falls wir diese Methode an einer beliebigen Folge von Zahlen ausführen, beim Vergleichen der Zahlen miteinander das Sortieren der Zahlen realisieren.

Das Vergleichen und einen daraufhin mögliches Austauschen, nennt man eine Vergleiche-Tausche-Operation.

Werden die Zahlen in der Folge miteinander verglichen, so ist es gleichgültig, welche Zahlen dies sind, da das Verfahren gleich bleibt, weshalb dieses Sortierverfahren als datenunabhängig bezeichnet wird.

Zu erwähnen ist zudem, dass wir hier mit Vergleichen arbeiten, weshalb diese Methode als vergleichsbasiertes Sortierverfahren bezeichnet wird.


Vergleichernetze

Um die Systematik des Verfahrens zu verbessern und die Geschwindigkeit des Verfahrens zu erhöhen, wurden die im Folgenden erklärten Sortiertechniken entwickelt.

Dabei ist zu nennen, dass auch in diesem Bereich der Informatik diverse Fachausdrücke existieren, welche zunächst zu klären sind.

Eine Folge, welche betrachtet und daraufhin sortiert wird, nennt man eine Eingabe und die Anzahl der Elemente n wird als Ordnung der Eingabe bezeichnet.

Des Weiteren wird eine Vergleiche-Tausche-Operation als Vergleicher bezeichnet, welcher zwei Elemente der Menge X, welche die Menge der Elemente der zu sortierenden Elemente sein soll, auch Grundmenge genannt, bei Bedarf vertauscht und wie folgt formuliert wird.

Vertauscht der Operator die Zahl in der zweiten Position mit der Zahl in der vierten Position, so wird der Vergleicher wie folgt formuliert.

Liberté Bildschirmfoto 2012-10-22 um 22.18.04.png

Allgemein können wir diesen Operator für den Vertausch der Zahlen in der Position i und der Position j wie folgt ausdrücken.

Liberté Bildschirmfoto 2012-10-22 um 22.59.46.png

Nun können wir diese Vergleicher nutzten, um die Positionen diverser Zahlen in den Folgen so zu tauschen, um letztlich die Zahlen nach der Größe zu sortieren.

Des Weiteren gilt es zu überlegen, wie diese Vergleicher für das Sortierverfahren genutzt werden können.

Dabei spielen Vergleichernetze eine zentrale Rolle, welche das Ordnen der Zahlenfolgen ermöglichen und die Entwicklung diverser Methoden zur schnelleren Sortierung ermöglichen.

Ein Vergleichernetz ordnet eine Zahlenfolge mit Hilfe von Vergleichern und kann wie folgt visualisiert werden.

Zunächst stellen wir eine beliebige Zahlenfolge, in diesem Beispiel die Zahlenfolge (3,1,2,4), untereinander gereiht dar, wobei die horizontalen Linien, auf welchen sich die Zahlen der Zahlenfolge befinden, als Datenleitungen beschrieben werden.

Liberté Bildschirmfoto 2012-10-22 um 23.21.33.png

Nun sollen die Vergleicher als Pfeile dargestellt werde, welche die Positionen zweier Zahlen vertauschen, falls dies im Sinne des Sortierens ist.

Daher verwenden wir nun einen Vergleicher, welcher die erste Zahl mit der zweiten Zahl vertauscht, um dem ersten Schritt zum Sortieren zu gehen.

Des Weiteren wird die veränderte Folge nach der Vertauschung rechts von der ursprünglichen Folge auf den Datenleitungen dargestellt.

Liberté Bildschirmfoto 2012-10-22 um 23.32.30.png

Nach diesem Schritt vertauschen wir die zweite und die dritte Zahl nach dem gleichen Prinzip.

Liberté Bildschirmfoto 2012-10-22 um 23.37.19.png

Formal können wir den Vorgang wie folgt ausdrücken.

Liberté Bildschirmfoto 2012-10-22 um 23.44.51.png

Somit haben wir diese Zahlenfolge mit Hilfe von Vergleichernetzen sortiert, wobei zu erwähnen ist, dass wir lediglich zwei untereinander stehende Zahlen ausgetauscht haben und beispielsweise keine aus der ersten Leitung in die vierte Leitung.

Vergleicher, welche sich lediglich auf benachbarte Positionen beziehen, werden als primitiv bezeichnet.

Zudem unterscheidet man zwischen unabhängigen und abhängigen Vergleichern.

Dies soll an unserem vorherigen Beispiel verdeutlicht werden.

Hätten wir zunächst die Zahlen in der zweiten und dritten Positionen verglichen und dann die Zahlen in der ersten und der zweiten Position, so hätte sich das Folgende ergeben.

Liberté Bildschirmfoto 2012-10-23 um 00.03.45.png

Zur Illustration:

Liberté Bildschirmfoto 2012-10-23 um 00.07.23.png

Wir erkennen nun, dass die Reihenfolge der Vergleicher nicht gleichgültig ist, wenn sich die Vergleicher auf eine gleiche Position beziehen, wobei dies in diesem Falle die zweite Position ist.

Solche Vergleicher in einem Vergleichernetz werden als abhängige Vergleicher bezeichnet.

Demgegenüber stehen die unabhängigen Vergleicher, welche sich nicht auf gleiche Positionen beziehen und somit auch vertauscht werden können.

Dies soll an unserem Beispiel verdeutlicht werden, wobei das folgende Vergleichernetz verwendet wird.

Liberté Bildschirmfoto 2012-10-23 um 12.22.10.png

Zur Illustration:

Liberté Bildschirmfoto 2012-10-23 um 12.19.24.png

Nun verändern wir die Reihenfolge der unabhängigen Vergleicher.

Liberté Bildschirmfoto 2012-10-23 um 12.23.47.png

Zur Illustration:

Liberté Bildschirmfoto 2012-10-23 um 12.20.11.png

Auch hier ist klar zu erkennen, dass die Reihenfolge der unabhängigen Vergleicher keinen Einfluss auf unser Ergebnis hat, weshalb wir diese Vergleicher auch parallel ablaufen lassen könnten, wie im Folgenden illustriert wird.

Liberté Bildschirmfoto 2012-10-23 um 12.38.03.png

Das Sortieren ist daher bei unabhängigen Vergleichen parallel möglich.

Betrachten wir uns nun ein weiteres Beispiel, bei welchem wir die nun genannte Folge zu sortieren versuchen.

\left( 2,4,1,5,3 \right)

Nun können wir die Zahlenfolge mit Hilfe eines Vergleichernetzes wie folgt sortieren.

Liberté Bildschirmfoto 2012-10-23 um 17.29.48.png

Formal können wir diesen Prozess wie folgt formulieren.

Liberté Bildschirmfoto 2012-10-23 um 18.00.33.png

Da sowohl sowohl die ersten beiden Vergleicher, sowie die letzten beiden Vergleicher unabhängig voneinander sind, können wir diese jeweils parallel zueinander ablaufen lassen, sodass wir das folgende Vergleichernetz erhalten.

Liberté Bildschirmfoto 2012-10-23 um 17.48.09.png

Dabei werden jeweils unabhängige Vergleicher, welche parallel zueinander ablaufen, als Vergleicherstufen zusammengefasst, weshalb uns hier ein zweistufiges Vergleichernetz vorliegt, wie in der folgenden Grafik illustriert wird.

Liberté Bildschirmfoto 2012-10-23 um 17.55.06.png

Durch parallel verlaufende Vergleicher in Stufen wird der Sortierungsprozess erheblich verkürzt, jedoch bedarf es auch hierbei einige Mechanismen, mit Hilfe derer man Zahlenfolgen systematisch sortieren kann.

Im Folgenden wird eine Methode zum systematischen Sortieren mit Hilfe von Vergleichernetzen vorgestellt.


Das Bubble-Sort-Verfahren

Hierbei handelt es sich um ein Sortierverfahren, welches sich nur primitiver Vergleicher bedient und mit der folgenden Systematik vorgeht.

Zunächst werden die ersten Zahlen in den ersten beiden Positionen verglichen und falls notwendig ausgetauscht. Daraufhin wird die letztere der beiden Zahlen, also die Zahl in der zweiten Position, und die darauf folgende positionierte Zahl verglichen, also die Zahl in der dritten Position.

Dieser Prozess wird so oft wiederholt, bis der Vergleicher die Zahl in der vorletzten Position mit der letzten Zahl vergleicht.

Dadurch ist sichergestellt, dass sich die größte Zahl am Ende an letzter Position befindet.

Ohne Beachtung der Zahlen könnte man die Systematik in einem Netz mit 4 Elementen wie folgt darstellen.

Liberté Bildschirmfoto 2012-10-23 um 20.21.31.png

Nun müssten auch die restlichen Elemente sortiert werden.

Da die Zahl in der letzten Position schon in der korrekten Position steht, müssen nur die restlichen Elemente nach dem gleichen Prinzip verglichen werden.

Diese Systematik wird so lange angewendet, bis die Zahlen in der richtigen Reihenfolge stehen, wobei die gesamte Systematik wie folgt dargestellt werden kann.

Liberté Bildschirmfoto 2012-10-23 um 20.20.54.png

Nun besteht die Möglichkeit der Einteilung des Vergleichernetzes in Stufen, sodass wir die folgende Struktur erhalten.

Liberté Bildschirmfoto 2012-10-23 um 20.26.16.png

Schon im vorherigen Aufbau konnten wir erkennen, dass wir für den ersten Vorgang der Methode zunächst drei Vergleicher, dann zwei und letztlich einen Vergleicher verwendet haben.

Die Anzahl der Vergleicher ist im ersten Teil des Verfahrens daher um eins kleiner als die Anzahl der Elemente der Folge und nimmt pro Teilverfahren um einen weiteren Vergleicher ab, bis nur noch ein Vergleicher verwendet wird und das Sortieren abgeschlossen ist.

Um die Gesamtanzahl der Vergleicher allgemein herauszufinden, können wir daher die folgende Gleichung aufstellen.

n-1+ n-2 + n-3 + .... + 1 = \sum_{i=1}^{n-1} i

Da uns die Gaußsumme bekannt ist, können wir zunächst die folgende Aussage treffen.

\sum_{i=1}^{n} i= (1+n) \cdot \frac{n}{2}

Nun wollen wir eine Formel für die für uns interessante Summe erstellen, weshalb wir wie folgt vorgehen.

\sum_{i=1}^{n-1} i =\left( \sum_{i=1}^{n} i \right) -n

Nachdem wir diese mathematische Aussage getroffen haben, können wir nun mit Hilfe der obigen Gleichung das Folgende formulieren.

\sum_{i=1}^{n-1} i =\left( \sum_{i=1}^{n} i \right) -n=(1+n) \cdot \frac{n}{2} - n

Nun formen wir die Gleichung um.

\sum_{i=1}^{n-1} i =\left( \sum_{i=1}^{n} i \right) -n=(1+n) \cdot \frac{n}{2}- n= (1+n)\cdot \frac{n}{2} - 2 \cdot \frac{n}{2}

Nach diesem Schritt klammern wir den Bruch aus und ermitteln die folgende Formel.

(1+n)\cdot \frac{n}{2} - 2 \cdot \frac{n}{2}=\frac{n}{2} \cdot (1+n-2) = \frac{n \cdot (n-1) } {2}

Bezeichnen wir die Anzahl der Vergleicher als #V, so können wir nun die folgende Formel formulieren.

Fehler beim Parsen(Lexikalischer Fehler): #V=\frac{n \cdot (n-1)}{2}


Nun, nachdem wir ermittelt haben, wie man allgemein die Anzahl der Vergleicher in diesem Verfahren ermittelt, können wir auch versuchen, eine Formel für die Anzahl der Stufen in unserem System allgemein aufzustellen.

Dazu ist zunächst zu klären, welche Faktoren für die Anzahl der Stufen eine Rolle spielen.

Da bei zwei Elementen nur eine eine Stufe vorhanden ist, da auch nur ein Vergleicher für zwei Elemente benötigt wird, betrachten wir uns als Beispiel zum Feststellen der Faktoren zunächst das Bubble-Sort-Verfahren für drei Elemente, wobei dieses im Folgenden illustriert wird.

Liberté Bildschirmfoto 2012-10-23 um 21.33.15.png

Teilen wir diese Vergleicher in Stufen ein, so erhalten wir die folgende Grafik.

Liberté Bildschirmfoto 2012-10-23 um 21.32.58.png

Wir erkennen, dass die Anzahl der Stufen definitiv von der Anzahl der Vergleicher in der ersten Leitung abhängen, da jeder Vergleicher in der ersten Leitung eine eigene Stufe benötigt.

Zudem ist die Anzahl der Stufen auch von der Anzahl der Vergleicher in der zweiten Leitung abhängig, da diese Vergleicher auch jeweils zusätzliche Stufen benötigen, da diese nicht parallel zu den ihnen abhängigen Vergleichern in der ersten Datenleitung ablaufen können.

Hierbei können wir feststellen, dass die Anzahl der Vergleicher in der ersten und in der zweiten Datenleitung die Anzahl der Stufen beeinflusst.

Nun betrachten wir uns als weiteres Beispiel ein nach dem Bubble-Sort-Verfahren sortierte, beliebige Folge mit fünf Elementen.

Hierbei würden wir das folgende Vergleichernetz erstellen.

Liberté Bildschirmfoto 2012-10-23 um 21.35.20.png

Nun teilen wir dieses in Stufen ein und analysieren dieses bezüglich der für die Stufen abhängigen Faktoren.

Liberté Bildschirmfoto 2012-10-23 um 21.36.33.png

Auch hier wird ersichtlich, dass die Vergleicher in der ersten und der zweiten Datenleitung entscheidend für die Anzahl der Stufen sind.

Betrachten wir uns nun die Vergleicher in der dritten und vierten Datenleitung.

Die Vergleicher in der dritten Leitung sind zwar abhängig von den Vergleichern in der zweiten Leitung, jedoch nicht von denen in der ersten Leitung, weshalb Vergleicher aus der dritten Datenleitung in einer Stufe mit den Vergleichern aus der ersten Gleichung dargestellt werden können.

Da allgemein die Anzahl der Vergleicher in der ersten Datenleitung höher ist als die Anzahl der Vergleicher in der dritten Datenleitung, können die Vergleicher in der dritten Datenleitung immer in den Stufen, welche wegen der ersten Vergleicher erstellt werden, untergebracht werden.

Somit haben diese keinen Einfluss auf die Anzahl der Stufen.

Zudem haben auch die Vergleicher in der vierten Datenleitung keinen Einfluss auf die Anzahl der Stufen, da diese in den Stufen, welche wegen der Vergleicher in der zweiten Datenleitung erstellt werden, postiert werden können.

Allgemein haben auch keine weiteren Vergleicher aus weiteren Datenleitungen Einfluss auf die Anzahl der Stufen, da diese in die Stufen, welche durch die Vergleicher in den ersten und den zweiten Datenleitungen erstellt werden, postiert werden können.

Somit, da eine Stufe durch jeweils einen Vergleicher in der ersten oder zweiten Datenleitung erstellt wird, gleicht die Anzahl der Vergleicher in den ersten und zweiten Datenleitungen der Anzahl der Stufen.

Die Anzahl der Vergleicher in der ersten Datenleitung ist immer um eins kleiner als die Anzahl der Elemente der Folge und die Anzahl der Vergleicher in der zweiten Datenleitung ist immer um zwei kleiner als die Anzahl der Elemente der Folge.

Somit können wir die folgende Gleichung für die Anzahl der Stufen, welche fortan als #S bezeichnet wird, formulieren.

Fehler beim Parsen(Lexikalischer Fehler): #S=n-1+n-2=2n-3


Um den Vorgang und zu illustrieren, bieten einige Internetseiten Programme an, welche diese Sortiermethode verdeutlichen und auf den entsprechenden Internetseiten ausführbar sind.

--Liberté 22:17, 23. Okt. 2012 (CEST)


Quellen

Pdf20.gif Zahlensymmetrien