Optimale schnelle List-Ranking- und Präfix-Algorithmen
February 05, 1995
In dieser Seminararbeit für mein Hauptstudium habe ich 1995 das grundlegende Präfixsummen (prefix sum) im Rahmen meines Informatikstudiums behandelt.
Es ist eine Zusammenfassung und didaktische Ausarbeitung der folgenden beiden Artikel:
- Richard Cole, Vishkin. Deterministic Coin Tossing with Applications to Optimal Parallel List Ranking. Information and Control, 1986, No. 70, p. 32-53 x
- Richard Cole, Uzi Vishkin. Faster Optimal Parallel Prefix Sums and List Ranking. Information and Control, 1989, No. 81, p. 334-352
In Kapitel 1 werden die verwendendeten Notationen und Begriffe, sowie das List-Ranking- und das Präfixsummen-Problem eingeführt. Die Standard-Algorithmen für diese beiden Probleme werden angegeben. In Kapitel 2 wird ein optimaler Algorithmus für das Präfixsummen-Problem besprochen. Der sogenannte deterministische Münzwurf wird dazu benutzt um symmetrische Situationen zu entscheiden. Dieser wird in Kapitel 3 anhand des $r$-ruling set Problemes erklärt. In Kapitel 4 werden die in den vorherigen Kapiteln besprochenen Verfahren in einem optimalen Algorithmus für das List-Ranking-Problem benutzt.