Gedächtnisprotokoll zur mündl. Diplomprüfung
Kurs: 01824 - Parallele Algorithmen
Prüfer: Prof. Dr. Verbeek
Datum: 27.8.2001
Dauer: 25 min
-
Welche Maschinenmodelle wurden im Kurs verwendet ?
RAM, PRAM definiert
-
Wie funktioniert eine PRAM ?
Wichtig: die Prozessoren können nur durch die ihnen bekannte eigene
Adresse i auf unterschiedliche Operanden zugreifen (Adressierung über
i)
-
Wie werden gleichzeitige Zugriffe mehrerer Prozessoren auf die gleiche
Speicherzelle behandelt ?
EREW, CREW, common / arbitrary / priority CRCW
-
Wozu benötigt man die verschiedenen PRAM-Typen ?
Es gibt für das gleiche Problem unterschiedliche Algorithmen mit
unterschiedlichen Laufzeiten.
Z.B. Maximumsuche in O(1) Zeit auf einer common CRCW PRAM.
-
Welche Komplexitätsmaße gibt es ?
Laufzeit, Aufwand, Speicherplatz, Anzahl Prozessoren;
Unterschied zwischen Laufzeit und Aufwand.
-
Kann Sortieren parallelisiert werden ?
parallelen Mergesort in der einfachsten Variante mittels ranking erläutert.
Zeit und Aufwand anhand des Algorithmus hergeleitet.
Verbesserung mittels schneller Suche erläutert.
Weitere Details des Algorithmus (weitere Aufteilung der beiden zu mischenden
Mengen) wurden nicht verlangt.
-
Kann man die Matrixmultiplikation beschleunigen ?
Strassen-Algorithmus mit Herleitung der Komplexität.
-
Wie schnell kann man Matrizen invertieren ?
Rückführung auf Matrixmultiplikation, daher gleiche Komplexitätsordnung.
-
Stichwort NP, P: sind alle berechenbaren Funktionen parallelisierbar
?
Parallelisierbarkeit definiert, NC-P Problem und P-Vollständigkeit
erläutert.
Warum wird zur P-Vollständigkeit logarithmische Bandreduzierbarkeit
verlangt ?
Die Prüfung verlief ruhig und entspannt.
Die Problematik NC, P, NP scheint ein Lieblingsthema von Prof. Verbeek
zu sein. Es empfiehlt sich, das entsprechende Kapitel aus "Einf. Theo.
Inf. B" zu wiederholen.
Viel Erfolg und denke bitte daran, ebenfalls ein Protokoll zu schreiben.