Optimale schnelle List-Ranking- und Präfix-Algorithmen

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.

Anmerkung: Dieser Artikel wurde im November 2016 an das neue Blog-Format angepasst.

 "Moduswechsel - TrueColor-Programmierung der Diamond Speedstar 24x" "Dynamisches Scheduling in Realzeitsystemen"