Correction Networks: Seminararbeit

Das Sortieren ist eines der fundamentalsten Probleme der Informatik, das vielfältig auftritt und insbesondere bei großen Datenmengen äußerst langwierig sein kann. Daher wurden in der Vergangenheit immer wieder intensive Anstrengungen unternommen, den Aufwand der verschiedenen Verfahren zu reduzieren.

Ein klassisches Verfahren ist die Anwendung eines Vergleichernetzwerkes. Neben einer langen Tradition zeichnet Vergleichernetze ihre potentielle Hardwarerealisierung aus. Ein Ansatz zur Verkürzung von Sortierzeiten ist die Berücksichtigung von Vorsortierungen. Geht man davon aus, dass eine Folge schon "fast ganz" sortiert ist, und maximal eine bestimmte Anzahl t "Fehleinträge" hat, lassen sich zum Teil beschleunigte Verfahren einsetzen.

Korrekturnetze (engl. correction networks) kombinieren die beiden oben beschriebenen Ideen. Bis vor Kurzem hatten die besten bekannten Korrekturnetze eine Zeitkomplexität von 4 log N. Der in dieser Arbeit vorgestellte Ansatz der Fibonacci-Netze  erzielt eine Reduzierung des Faktors vor log N auf etwa 1,44.

In der Arbeit werden zunächst verschiedene Definition mit Bezug auf Sortiernetze und Korrekturnetze vorgestellt. Weiterhin wird dann ein Vergleichernetz konstruiert, das einen Fehler korrigieren kann. Im nächsten Teil wird dann ein Netz vorgestellt, das die Streuung von t Fehlern auf ein bestimmtes Maß reduzieren kann. Abschließend wird dann gezeigt, wie das Gesamtkorrekturnetz mit der angestrebten Tiefe konstruiert werden kann.