Diplomprüfung Theoretische Informatik Teil 1
Kurs : Parallele Algorithmen 1824
Datum : 27.10.1998
Zeit : 11.00 Uhr
Dauer : 30 Minuten
Prüfer : Dr. Damaschke
Beisitzer : Herr Dipl. Inform. Robert Rettinger
Note : 1.3
(Karatsuba Algorithmus)
O(nlog3), Abschätzung mittels Rekurrenzgleichung gezeigt (Definition von Satz 2.1.4 war nicht en detail gefragt)
Ja, mittels FFT! Definition der Fouriertransformation und den Zusammenhang zu Polynomen erläutert. Konvolutionssatz zitiert und Vorgehensweise geschildert. Komplexität des Verfahrens genannt (O(log(n) bei paralleler Ausführung der FFT).
Rekursiven FFT geschildert (Zerlegung in gerade und ungerade Ergebniskomponenten, besondere Struktur der Matrix F, Gewinnung der ωk im voraus mittels Präfixsummenberechnung)
Nein, ω, ω
-1 ,n-1 müssen definiert sein.Strassen Algorithmus geschildert und Komplexität genannt (Details der Berechnung waren nicht verlangt "das kann man bei Bedarf nachlesen" so Dr. D.).
Nein {(0,1),⋀,⋁} ist kein Ring.
Man faßt die Elemente der Matrizen als Elemente einer Restklasse modulo n+1 auf!
Algorithmus bzw. Satz von Atallah Goodrich zitiert.
Paralleles Sortieren zum schnellen Sortieren der Punkte nach steigender x-Koordinate. Paralleles Suchen auf den Streckenstücken von up(S1) und up(S2) nach dem passenden Steigungsintervall der Tangentensteigung. (deshalb ist der Algorithmus so schnell, O(1) Zeit für die Such-Operation!)
Mergesort Algorithmus beschrieben (Reduktion auf das ranking Problem, Problematik des parallelen Mergings beschrieben, Lösung durch Zerlegung in m/log m große Blöcke und sequentielles Mischen dieser Blöcke)
Man greift mit mehreren Prozessoren gleichzeitig auf die zu durchsuchende Folge zu.
Voraussetzungen genannt (Operanden in Blättern eines geordneten Bin-Baumes, Operatoren in den Knoten)
Preorder-Numerierung des Bin-Baumes bzw. des Eulerkreises in ihm beschrieben. Zwischenfrage: Was muß man tun, um diesen Preorder Durchlauf mit dem Eulerkreis-Algorithmus zu erzeugen? Knotengewichte: linker Sohn, rechter Sohn, Vater. Blätter mit dem Gewicht 1 versehen, übrige Knoten mit 0. Prefixsums über die Blätter schafft Numerierung in O(log n) Zeit. Baumkontraktion mit Rake beschrieben und Werterhalt mit Hilfe der Variablen Av, Bv erläutert (nur verbal, Formalismus war nicht gefordert)
List-Ranking um überhaupt die Indizes der Listenelemente zu kennen!
Der Baum muß nicht unbedingt balanciert sein sondern kann beliebig entartet sein. Beim Rake erzielt man garantiert bei jedem Schritt eine Halbierung der Anzahl der Blätter (e.g. man hat eine logarithmische Zeitschranke), beim einfachen ‚Baumauswerten‘ verliert man diese Zeitschranke!
Insgesamt war die Prüfung angenehm und verlief in einer ruhigen freundlichen Atmosphäre. Dr. Damaschke hat einen ruhigen Prüfungsstil; er bat fast um Entschuldigung, wenn er mich bei meinen Ausführungen unterbrach, weil ihm die Antwort bis dahin schon genügte oder er noch eine ergänzende Erläuterung machen wollte. Seine Fragen bauten häufig auf meinen Antworten auf. Trotzdem hatte ich vor allem bei der Nachbereitung der Prüfung das Gefühl, daß er sich mit großer Systematik einen Überblick über meinen Wissensstand des gesamten Kurses verschafft hatte (es fehlte eigentlich nichts wesentliches, bis auf Spezialitäten wie Toeplitz Matrizen lineare Rekurrenzen oder lineare Optimierung)
Auch bei dieser Prüfung hat sich kurzes (oder in diesem Fall auch längeres) Zögern beim Antworten oder 'Verlaufen' nicht in – deutlichen - Notenabzügen niedergeschlagen. Dr. Damaschke gibt zum Teil Hilfestellung oder stellte bei meiner Prüfung auch eine Frage zurück um mir Gelegenheit zu geben, durch seine nächsten Fragen den ‚Groschen zum Fallen‘ zu bringen. Wichtig ist es vor allem bei diesem Prüfer einen guten Überblick über den Stoff zu haben und zu den allgemeineren Fragen ('Was wissen Sie über...' oder 'Erklären Sie ....') ein paar Sätze im Vortragsstil vorzubereiten. Er stellt gern etwas global gehaltene Fragen die eben auch etwas längere Antworten erfordern.
Dr. Damaschke ist auf alle Fälle ein empfehlenswerter Prüfer.