Parallele Algorithmen

24. June 2011 Informatik
  • Titel: Parallele Algorithmen
  • Organisation: LUG JENA
  • Seitenzahl: 67

Skript herunterladen (PDF)

Inhalt

  • Inhaltsverzeichnis
  • Auflistung der Sätze
  • Sätze
  • Definitionen und Festlegungen
  • Literaturverzeichnis
  • 1 Einleitung
  • 1.1 Modelle für parallele Algorithmen
  • 1.1.1 DAG – Modell eines gerichteten, kreisfreien Graphen
  • 1.1.2 Netzwerkmodell
  • 1.1.3 Synchrones Shared-Memory-Modell
  • 2 Die Güte von parallelen Algorithmen und das Theorem von Brent
  • 3 Die sieben Paradigmen zum Entwurf paralleler Algorithmen
  • 3.1 Binärbaumparadigma
  • 3.1.1 Rekursiver Ansatz
  • 3.1.2 Nichtrekursiver Ansatz
  • 3.2 Pointer Jumping
  • 3.2.1 Parallel Prefix
  • 3.3 Teile und Herrsche
  • 3.4 Partitioning
  • 3.5 Pipeline-Verfahren
  • 3.6 Accelarated Cascading
  • 3.7 Aufbrechen von Symmetrien
  • 4 Listen und Bäume
  • 4.1 List-Ranking
  • 4.2 optimales Listranking
  • 4.2.1 Pointer Jumping
  • 4.2.2 Optimales Listranking
  • 4.3 Eulertour-Technik
  • 4.4 Baumkontraktion
  • 4.5 Das LCA-Problem
  • 4.6 Das Range-Minima-Problem
  • 5 Suchen, Mischen, Sortieren
  • 5.1 Suchen in einer sortierten Menge nach Kruskal
  • 5.2 Mischen
  • 5.3 Sortieren
  • 5.3.1 Merge with the help of a cover
  • 5.3.2 Optimales Sortieren – Pipeline Merge Sort
  • 5.4 Selektion
  • 6 Parallelisierbarkeit
  • 6.1 P-vollständige Probleme
  • 6.1.1 Maximaler Fluss in einem Netzwerk
  • 6.1.2 Lineare Optimierungsprobleme
  • 6.1.3 Das circuit value problem
  • 6.2 P-Vollständigkeit von CVP
  • 6.3 DFS-Theorem (geordnete Tiefensuche)
  • Index

Vorschau

Parallele Algorithmen

Prof. Dr. Hans-Dietrich Hecker SS 2005 / 2007, WS 2010

Vorwort

Dieses Skript ist im Rahmen des Projekts „Vorlesungsskripte der Fakultät für Mathematik und Informatik“ entstanden und wird im Rahmen dieses Projekts weiter betreut. Das Skript ist nach bestem Wissen und Gewissen entstanden. Dennoch garantiert weder der auf der Titelseite genannte Dozent, noch die Mitglieder des Projekts für dessen Fehlerfreiheit. Für etwaige Fehler und dessen Folgen wird von keiner der genannten Personen eine Haftung übernommen. Es steht jeder Person frei, dieses Skript zu lesen, zu verändern oder auf anderen Medien verfügbar zu machen, solange die Adresse der Internetseiten des Projekts http://www.minet.uni-jena.de/ ~joergs/skripte/ genannt wird. Diese Ausgabe trägt die Versionsnummer 3237 und ist vom 7. Februar 2011. Eine neue Ausgabe könnte auf der Webseite des Projekts verfügbar sein. Jeder ist aufgerufen, Verbesserungen, Erweiterungen und Fehlerkorrekturen für das Skript einzureichen bzw. zu melden oder selbst einzupflegen – einfach eine E-Mail an die Mailingliste senden. Weitere Informationen sind unter der oben genannten Internetadresse des Projekts verfügbar. Hiermit möchten wir allen Personen, die an diesem Skript mitgewirkt haben, vielmals danken: • Jörg Sommer (2004, 2005, 2007) • Fred Thiele (2005) • Christian Raschka (2005) • Michael Preiss (2007) • Jörg Bader (2011)