Systolische Algorithmen

Systolische Algorithmen sind ein Begriff aus der theoretischen Informatik. Es handelt sich um Algorithmen, die eine Menge von Werten (hier: Zahlen) permutieren, also in eine anders-sortierte Menge überführen. Speziell interessant ist dabei die Frage, wieviele Vertauschungen dabei stattfinden müssen, um eine bestimmte Reihenfolge zu erhalten.

Um diese Algorithmen aufzuzeichnen, kann man links die ursprüngliche Menge, rechts die endgültige Menge und dazwischen Leitungen von jedem Platz zum gegebügerliegenden zeichnen. Im folgenden wird stets angenommen, dass die Zahlen von oben nach unten sortiert werden sollen. Was also noch benötigt wird, sind sogenannte "Vergleicher". Diese setzen sind an zwei Leitungen fest, vergleichen die darauf liegenden Werte miteinander und vertauschen die Werte so, dass der grössere Wert danach auf der unteren Leitung liegt. Der Algorithmus läuft von links nach rechts. Beispiel:

A---+-------+--------+---W
    |       |        |
B---+----+--+-----+--+---X
         |        |
C--------+-----+--+------Y
               |
D--------------+---------Z

setzt man im obigen Beispiel A=3, B=1, C=4, D=2, so befinden sich die Werte an folgenden Orten:

3---+1------+1-------+1--1
    |       |        |
1---+3---+3-+3----+2-+2--2
         |        |
4--------+4----+2-+3-----3
               |
2--------------+4--------4

Dies war nun eine Sortier-Schaltung mit 6 Vergleichern. Es geht aber auch mit 5:

A---+-------+-------------W
    |       |
B---+------ | ---+----+---X
            |    |    |
C-------+---+--- | ---+---Y
        |        |
D-------+--------+--------Z

Zu diesen systolischen Algorithmen gibt es ein paar Sätze, wovon folgender der grundlegende ist:

Gegeben eine monoton steigende Funktion f, den Eingabevektor x und den Ausgabevektor y.

1. Satz: Falls der Algorithmus (Das Netzwerk von Vergleichern) x in y transformiert, so transformiert er auch f(x) in f(y).

Damit ist gemeint, dass, falls der Algorithmus die Werte korrekt sortieren kann, er auch Transpositionen und Streckungen dieser Werte korrekt sortieren kann. Also beispielsweise: Wenn x=[3,1,4,2] korrekt zu [1,2,3,4] sortiert wird, wird auch f(x)=x+1=[4,2,5,3] zu [2,3,4,5] und auch f2(x)=x*2=[6,2,8,4] zu [2,4,6,8] korrekt sortiert, oder auch beispielsweise f3(x)=2^x=[8,2,16,4] wird zu [2,4,8,16].

Man könnte auch sagen, dass jeder Vektor, der gleich ungeordnet ist, wie x, gleich sortiert wird.

2. Satz: Wenn der Algorithmus jeden möglichen Eingabevektor x, der nur aus Nullen und Einsen besteht, korrekt sortiert, so sortiert er jeden (mit beliebigen Zahlen gefüllten) Eingabevektor korrekt.

Beweis: Bewiesen wird, dass, wenn einige beliebige Vektoren nicht korrekt sortiert werden, dazu auch 0-1-Vektoren existieren, die ebenfalls nicht korrekt sortiert werden.

Angenommen, durch den nicht-perfekten Sortieralgorithmus entsteht ein Fehler an der Stelle i, sodass y_i > y_i+1. Sodann definiert man die monoton wachsende Funktion f(x), die für jeden Wert des Eingabevektors 0 einsetzt, falls x < y_i und 1, falls x >= y_i. Nach obigem Satz wird dieser transformierte Eingabevektor genau gleich sortiert, und ergibt an der Stelle i und i+1 des Ausgabevektors f(y_i)=1 und f(y_i+1)=0. QED

Satz: Gegeben sei ein Algorithmus, der nur Vergleicher von benachba

rten Leitungen besitzt. Sortiert dieser Algorithmus den inversen Eingabevektor, so sortiert er jeden Vektor.

Beweis: Die Inverse ist die schlimmste Permutation: Das Element 1 muss n-1 Vertauscher durchlaufen, um an den unteren Rand zu kommen. Das Element 2 muss n-2 Vertauscher durchlaufen, um vor die 1 zu kommen, ...

1 --  2   2   2   2 | 3   3   3 | 4   4 | 5
2 --  1   3   3   3 | 2   4   4 | 3   5 | 4
3 --  3   1   4   4 | 4   2   5 | 5   3 | 3
4 --  4   4   1   5 | 5   5   2 | 2   2 | 2
5 --  5   5   5   1 | 1   1   1 | 1   1 | 1

Jede andere Permutation kann mit weniger Vertauschungen erreicht werden. Somit ist also jede Möglichkeit zu permutieren durch die Inverse abgedekt.

Satz: Gegeben sei ein Algorithmus, der nur Vergleicher von benachbarten Leitungen besitzt. Um jeden beliebigen Vektor zu sortieren, muss dieser Algorithmus mindestens n-tief-2 Vergleicher besitzen.

Beweis: Da der Algorithmus richtig ist, falls die Inverse richtig sortiert wird (Satz oben), betrachten wir diese. Die Anzahl Vertauschungen entspricht (Siehe Beispiel) der Summe n-1 + n-2 + ... + 2 + 1 und das ist gleich n*(n-1)/2.

Wandelt man nun den Ausdruch n-tief-2 um, so ergibt sich n!/(2*(n-2)!) = (n*(n-1))/2. QED