Robert Sedgewick: Algorithmen

[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]


40. Parallele Algorithmen



Übungen

  1. Zeigen Sie zwei mögliche Wege zur Verwendung von Parallelität bei Quicksort auf.
  2. Beweisen Sie, daß bei Verfahren des »Aufspaltens und Schichtens« die Eigenschaft, daß die Spalten sortiert sind, erhalten bleibt.
  3. Erstellen Sie ein herkömmliches Pascal-Programm zum Mischen von Dateien unter Benutzung des Bitonic Merge von Batcher.
  4. Erstellen Sie ein herkömmliches Pascal-Programm zum Mischen von Dateien unter Benutzung des Bitonic Merge von Batcher, jedoch ohne tatsächlich Operationen von der Art des perfekten Mischens auszuführen.
  5. Wie viele Operation des perfekten Mischens bringen alle Elemente in einem Feld der Größe 2n zurück an ihre ursprünglichen Positionen?
  6. Skizzieren Sie ein Schema von der Art von Abbildung 40.7 zur Veranschaulichung der Arbeitsweise des systolischen Feldes zur Multiplikation einer Matrix mit einem Vektor für das folgende Problem:

    Formel

  7. Erstellen Sie ein herkömmliches Pascal-Programm, das die Arbeitsweise des systolischen Feldes für die Multiplikation einer NxN-Matrix mit einem N-Vektor simuliert.
  8. Zeigen Sie, wie man ein systolisches Feld zum Transponieren einer Matrix benutzen kann.
  9. Wie viele Prozessoren und wie viele Schritte sind für eine systolische Maschine erforderlich, die eine MxN-Matrix mit einem N-Vektor multiplizieren kann?
  10. Geben Sie ein einfaches paralleles Schema für die Multiplikation einer Matrix mit einem Vektor unter Verwendung von Prozessoren an, die die Fähigkeit haben, sich berechnete Werte zu »merken«.


[ Inhaltsverzeichnis ] [ vorhergehende Seite ] [ nächste Seite ] [ Stichwort ]