Sommersemester 2006
Prof. Dr. Manfred Kunde

[Veranstaltungen] [Scheinerhalt] [Inhalte] [Literatur] [Materialien]

Mitteilung:

Der Abgabetermin 19.6. für Blatt 5 ist korrekt!
Blatt 6 wird am 26.6. herausgegeben und muss am 3.7. abgegeben werden!

Veranstaltungen

Vorlesungen

• Mo 17:30 Uhr, H 2507

• Do 17:30 Uhr, H 1520b

• Di (U) 13:00 Uhr, 1520b

Kriterien für den Scheinerhalt

Der Schein ist in zwei Varianten erhältlich, 3V und 3V+1Ü.

Für die Scheine müssen die folgenden Leistungen erbracht werden:

Die notwendigen Teilnahmen an den Veranstaltungen sind selbsterklärend.

Das Übungsprogramm umfasst 6 Blätter á 4 Aufgaben. Von diesen müssen insgesamt 6 Aufgaben auf mindestens 5 verschidenen Blättern erfolgreich bearbeitet worden sein.

Inhalte der Vorlesung

Der Entwurf und die Analyse paralleler Algorithmen ist ein Teilgebiet der Algorithmentheorie, dessen Methoden Anwendungen in vielen Bereichen der Informatik finden. In der Vorlesung wird die Wechselwirkung zwischen Lösungsmethoden für Probleme, deren Effizienz (Rechenzeit, Speicheraufwand, Anzahl der Prozessoren) und den wichtigsten zugrundeliegenden Architekturen (Bäume, Gitter, Hypercubes usw.) dargestellt.

Inhalte der Vorlesung:

• Einführung und Grundlagen

• Bäume und Gitter

• Parallele Präfixberechnung

• Matrizenalgorithmen

• Graphenalgorithmen

• Sortieren

• Datentransport

• Höherdimensionale Gitter

• Hypercube und verwandte Netzwerke

• PRAM-Modell

Literatur

• F. T. Leighton:
  Introductions to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes
  Morgan Kaufmann Publishers, 1992
  
  
• Joseph JaJa:
  An Introduction to Parallel Algorithms
  Addison-Wesley Publishing Company, Inc., 1992

Materialien und Übungsblätter

Übungsblätter

1. Übungsblatt
   Sortieren auf dem linearen Feld, Parallele Präfixberechnung, Graphmetriken
   Abgabe am 18.4.2006, 10 Uhr
   
   
2. Übungsblatt
   Summation, Multiplikation, Präfixberechnung, Approximation des Kehrwertes
   Abgabe am 2.5.2006, 10 Uhr
   
   
3. Übungsblatt
   Systolische Algorithmen
   Abgabe am 15.5.2006, 10 Uhr
   
   
4. Übungsblatt
   0-1-Prinzip, Sortierung durch Mischen
   Abgabe am 29.5.2006, 10 Uhr
   Version vom 24.5.2006
   
   
5. Übungsblatt
   1-1-Sortieren, Untere Schranken, Greedy, Hypercube
   Abgabe am 19.6.2006, 10 Uhr
   (Der Abgabetermin ist korrekt!)
   
   
6. Übungsblatt
   Hypercubes und verwandte Netzwerke, Routing
   Abgabe am 3.7.2006, 10 Uhr