Die Vorlesung am Donnerstag findet nur bis zum 26.5.2005 statt. Anschließend findet zu diesem Termin die Vorlesung Spezielle Algorithmen statt.

Scheinerwerb

Es ist möglich einen Schein über 3V+1Ü zu erwerben. Dazu sind die folgenden Leistungen erfordelich:

• Mindestens 12 Teilnahmen an der Vorlesung
• Mindestens 4 Teilnahmen an den Übungen ab dem 5.4. 2005
• Mindestens sechs erfolgreich bearbeitete Aufgaben von fünf verschiedenen Blättern.
• Erfolgreiche Teilnahme an der Klausur (Zulassung nach oberen drei Punkten)

Aufgabenzettel

Die bearbeiteten Aufagenzettel können im Briefkasten vor Raum 300 im Blechhaus abgegeben werden.
Die Ausgabe der Aufgaben im Netz erfolgt i.A. am Donnerstag in der ungeraden Woche. Abgabe ist i.A. am Donnerstag in der geraden Woche.

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.

• 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 zur Vorlesung

• 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
• Orginalliteratur

Ergänzungsmaterialien zur Vorlesung



Übungsblätter

Übungsblatt 7 (Offline-Routing, Benes-Netzwerke, Odd-Even-Merge-Sort)

Übungsblatt 6 (1-m-Routing, Hypercube)

Übungsblatt 5 (Untere Schranken für das Sortieren, h-h-Routing)

Übungsblatt 4 (Sortieren, 0-1-Prinzip)

Übungsblatt 3 (Matrizenmultiplikation)

Übungsblatt 2 (Summation auf linearen Feld,Multiplikation, Division, Präfixberechnung) 

Übungsblatt 1 (Sortieren auf dem linearen Feld, Effizienz und Kosten, Sortierung von Bits,
Graphenmetriken)