Fragen

• Wie werden Präfixsummen bestimmt?
  • Parallele Berechnung genau erklärt
• Wo wird dieser Algorithmus verwendet?
  • Mir ist zunächst nur die Bestimmung von Abständen in Bämen eingefallen; aber er wird z.B. auch bei der Berechnung der Potenzen von w bei der FFT benutzt.
• Wie werden die Abstände in Bäumen bestimmt?
  • Gerichteten Baum per Eulerpfad bestimmen
  • Kanten des Eulerpfads mit List ranking durchnumerieren
  • Den Kanten die Gewichte +1 [p(v)®v] bzw. -1 [v®p(v)] zuordnen
  • Präfixsummen der Kantengewichte bestimmen
• Wie werden Matrizen effizient multipliziert?
  • Strassen-Algorithmus erläutert
  • Komplexität: M(n)=O(n^log₂7)=O(n^2.82)
  • Zerlegungsidee zur Verbesserung auf O(n^2.38) [steht nicht im Kurs]
• Geht das auch für Matrizen, die als Elemente nur Null und Eins enthalten, mit der Addition modulo 2?
  • Ja
• Ist der Algorithmus für boolesche Matrizen parallelisierbar?
  • Ich hatte schon im Zusammenhang mit der vorhergehenden Frage die Kernaussagen von Satz 4.1.2 erwähnt und wußte daher erst einmal nicht, worauf die Frage hinauslaufen sollte. Die Antwort ist natürlich nein, da die Struktur ({0,1},Ù, Ú) kein Ring ist und insbesondere keine "Subtraktion" definiert ist.
• Multiplikation von Polynomen
  • Fourier-Transformation erläutert
  • Zusammenhang mit Konvolutionssatz beschrieben
• Geht das auf jedem Ring?
  • Nein, w, w^-1 und n^-1 müssen Elemente des Rings sein.
• Ist das lineare Optimierungsproblem (LOP) parallelisierbar?
  • Rückführung des LOP auf Durchschnitt von Halbräumen
  • Einfach parallelisierbar im Fall n=2 (Durchschnitt von Halbebenen)
• Durchschnitt von Halbebenen
  • Duale Transformation auf Problem der konvexen Hülle
  • Vorgehensweise zur Bestimmung der konvexen Hülle erläutert

Eindruck

Dies war meine zweite Prüfung bei Dr. Damaschke, daher war ich etwas besser auf seinen Fragestil eingestellt. Die Prüfung verlief in ruhiger Atmosphäre. Die klar gestellten Fragen gingen mehr in die Breite als in die Tiefe. Details wurden kaum nachgefragt. Andererseits läßt Dr. Damaschke einem Zeit, auch Details zu erzählen, so man sie kennt. Genaue Angaben zur Komplexität der Algorithmen wurden nicht gefordert. Eine Darstellung der grundlegenden Sachverhalte reichte in der Regel aus. Kleine Aussetzer bei weniger wichtigen Gebieten (siehe boolesche Matrizen) führten nicht zu Punktabzug.

Viel Erfolg!