|
||
|
||
 Download MS-Word File |
|
Datum: 25.05.2001 Prüfer: Dr. Thomas Hofmeister Note: 2.3 Dauer: 35 min. Skripten: EA-Skript 2000 von Susanne Albers Literatur: T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, MIT Press, 1994 I. Wegener: Effiziente Algorithmen für grundlegende Funktionen, Teubner, 1996 Erzähl etwas über den Algorithmus von Dijkstra und die Fibonacci Heaps. Die dist-Funktion als Dreiecksungleichung definiert, mit einer Skizze Ablauf des Algos beschrieben, Vorteil der Prioritätswarteschlange genannt. Dann Fibonacci Heaps definiert und die unterstützenden Operationen genannt (Create, Min, Insert, Empty, DeleteMin, DecreaseKey) Wie funktioniert DecreaseKey? Ablauf der Operation beschrieben. Thomas hat eine Skizze mit k markierten Knoten gezeichnet (wie im Skript) und ich sollte noch mal bestimmen welche Knoten markiert werden und welche in Wurzelliste aufgenommen werden. Bei einer der Operationen werden Bäume verschmolzen. Wie geht das? Die Operation DeleteMin beschrieben. Wie findet man dabei Baumpaare die verschmolzen werden? Den Einsatz des Arrays mit der Grösse R erklärt. Wie ist die amortisierte Analyse von DeleteMin? Tamort = Ttats + Potentialdifferenz. Potential über Anzahl der Knoten in der Wurzelliste. Danach hatte ich einige Hänger und hatte vergessen, wie man Tamort = O(logn) herleitet. Dann kommen wir zur Maximierung von Flüssen in Netzwerken. Definiere und beweise den Satz Maxflow = Mincut. Definition. Ersten Ansatz genannt. Da hat Thomas eine Skizze gezeichnet und ich habe irrtümlicher Weise die Definition von wert(VQ,VS) mit w(p) vertauscht. Dann den 2. Ansatz genannt und anhand der Markierungsbedingungen des Algos bewiesen. OK, dann ein anderer Algo. , Goldberg und Tarjan ? Die Idee und eine grobe Ablauf beschrieben. Wie funktionieren dann die Funktionen Push und Relabel? Die beiden Funktionen erklärt. Mit Hilfe von Thomas habe ich die Definition von einer gültigen Knotenmarkierung hinbekommen. Jetzt zur Zahlentheorie, Wie funktioniert der Algo. von Solovay und Strassen? verschärftem Satz von Fermat als Grundlage des Algos genannt. Den Ablauf des Algos beschrieben Wie ist die grobe Idee, die Wahrscheinlichkeit von 1–(1/2)k zu beweisen? Die Begriffe „Gruppe“ und „Untergruppe“ genannt, die Menge der schlechte Zufallzahlen als Untergruppe von Z* , und dass keine echte Teiler von |Z*| grösser als |Z*|/2 ist. Wie kann man xn berechnen? Algo Potenzierung erklärt. Laufzeit O(log n). Kommen wir jetzt zum Rucksack-Problem, was sind erst mal die Voraussetzungen für ein poly. Approximationsschema und ein echtes poly. Approximationsschemata? Bei poly. Approximationsschema soll die Güte r(A,I)<= 1+e sein. Ich bin da nicht auf die Bedingung e>0 gekommen, was Thomas hören wollte. Bei einem echt poly. Approximationsschemata soll die Laufzeit polynomiell in n und 1/e sein. Wie funktioniert dann der Algo zum Rucksack-Problem, der ein echt poly. Approximationsschemata ist? Die Zahl „mingewicht“ definiert, worauf der pseudopoly. Algo mit dem Ansatz von Dynamische Prog. basiert. Laufzeit O(n²cmax) genannt. Dann die Möglichkeit der Skalierung der Gewichte um Faktor R = ëe cmax/(1-e)nûund die Laufzeit O(n³/e) beschrieben. Fazit: Die Prüfungsatmosphäre war sehr locker. Ich war übertrieben nervös und vielleicht deswegen konnte ich nicht bei allen Fragen sofort antworten. Thomas hat mir aber auch die Zeit zum Überlegen gegeben und durch kürzen Fragen geholfen, dass ich den Einstig in den jeweiligen Themen schaffe. Mit der Benotung bin ich zufrieden. |