Fragenkatalog zum Selbsttest: ===================================================== Dies ist eine Fragenliste, die ich für mich selber machen würde, wenn ich mich auf eine Prüfung in EAKT vorzubereiten hätte. In diesem Sinne sind die Fragen nicht unbedingt als "Fragen, die in einer mündlichen Prüfung gestellt werden" zu verstehen. Sie sollen nur dazu dienen, den eigenen Wissensstand zu überprüfen. Nach dem "#" die jeweilige Skriptseite, wobei sich die Nummerierung auf das Semesteranfangsskript bezieht. Die Fragenliste ist nach diesen Skriptseiten geordnet. ===================================================== Wann heißen in einem ungerichteten Graphen zwei Knoten zusammenhängend? Wann heißen in einem gerichteten Graphen zwei Knoten zusammenhängend? #6 Definiere, was man unter den starken Zusammenhangskomponenten eines gerichteten Graphen versteht. #6 Gib einen Algorithmus an, mit Hilfe dessen man starke Zusammenhangskomponenten in einem gerichteten Graphen berechnen kann. Welche Laufzeit hat der Algorithmus? #6/7 Beweise, dass der von Dir beschriebene Algorithmus zur Berechnung von starken Zusammenhangskomponenten korrekt ist. Wieso hat er die Laufzeit O(n+m)? #7/8 Was versteht man unter einem Schnittpunkt in einem ungerichteten Graphen G? #8 Wann heißt ein Graph zweifach zusammenhängend? #8 Was versteht man unter einer Zweizusammenhangskomponente in einem ungerichteten Graphen G? #8 Zeichne ein Beispiel für einen Graphen und seine Zweizusammenhangskomponenten. #8 Warum betrachtet man Zweizusammenhangskomponenten? #9 Was kann man über den Schnitt zweier Zusammenhangskomponenten aussagen? Beweise Deine Aussage! #9 Wieso gibt der Algorithmus zur Bestimmung der Zweizusammenhangskomponenten Kantenmengen aus und nicht etwa Knotenmengen? #10 Wie ist der Lowpt definiert, den man zur Bestimmung der ZZK benötigt? #12 Wie kann man mit Hilfe der Lowpt-Werte erkennen, ob ein Knoten a ein Schnittpunkt ist? Beweise Deine Aussage! #12/13 Mit Hilfe welcher Gleichung ermittelt der Algorithmus BICON die Lowpt-Werte? Beweise, dass die Gleichung korrekt ist! #13 Beschreibe, wie Algorithmus BICON die ZZK berechnet. #14 Welche Laufzeit hat Algorithmus BICON? Wieso ist die Laufzeit so? #14 Warum machen die zusätzlichen Stackoperationen die Laufzeit O(n+e) des DFS-Algorithmus nicht "kaputt"? #14 Beweise, dass Algorithmus BICON tatsächlich alle ZZK berechnet. #14/15 Wie ist der transitive Abschluss von (un)gerichteten Graphen definiert? #15 In welcher Laufzeit kann man den transitiven Abschluss eines ungerichteten Graphen berechnen? Mit welchem Algorithmus geht das in der genannten Zeit? #15 Wie kann man effizient den transitiven Abschluss von gerichteten Graphen berechnen? #15 Zeige, dass man in Zeit O(M(n)*log n) den transitiven Abschluss eines gerichteten Graphen berechnen kann. #16 Welche drei Arten von Kürzeste-Wege-Problemen kennst Du? #16 Wie löst man das SSSP-Problem in Laufzeit O(n^2), wie in Zeit O(n+e*log n)? (Hier sind keine *Details* notwendig, Skizze reicht.) #17 Wieso machen negative Kantenkosten das SSSP-Problem "schwieriger"? #17 Wie löst man das APSP-Problem in kubischer Laufzeit, wenn alle Kreise nichtnegative Länge haben? #17 Beim Lösen des ungewichteten APSP-Problems durch den Algorithmus "APD" haben wir einen Graphen G^* definiert. Wie war er definiert? Zeichne ein Beispiel für G und G^*. #18 Wie berechnet man (beim APD-Algorithmus) den Graphen G^* aus dem Graphen G? #18 Wie ist der Durchmesser eines Graphen definiert? #19 (APD-Algorithmus:) Wenn G^* der vollständige Graph mit Adj.matrix A^* ist, wie berechnet man daraus die Distanzmatrix von G? #19 Welchen Zusammenhang gibt es (in Abhängigkeit von "gerade/ungerade") zwischen D_i,j und D^*_i,j? Beweis! #19 Wenn i und k Nachbarn sind, was kann man über die Distanzen D_i,j und D_k,j aussagen? #20 Wie kann man an den D^*_k,j-Werten ablesen, on D_i,j gerade oder ungerade ist? Beweis! #20, Lemma 2.23 Bei der Entscheidung, ob D_i,j gerade oder ungerade ist, muss man prüfen, ob eine Summe einen bestimmten Wert überschreitet oder nicht. Wie lautet die Aussage genau? Wie berechnet man für alle Paare i,j alle Summen mit Hilfe einer Matrixmultiplikation? #20, Satz 2.24 und die nachf. Bemerkungen Schreibe in Pseudocode den Algorithmus APD zur Lösung des ungewichteten APSP hin. #20 unten/21 Wieso ist die Laufzeit des Algorithmus APD O(M(n)*log n)? #21 Wie ist das MINCUT-Problem definiert? Wie die gewichtete Variante? Was bezeichnet man mit dem Wort "Schnitt"? #22 Wieso lässt man beim gewichteten MINCUT-Problem keine negativen Gewichte zu? #22 Zeichne ein (nichttriviales) Beispiel für einen ungerichteten Graphen G und einen minimalen Schnitt in G. #22 Erkläre, was man unter dem Q-S-MINCUT-Problem versteht. #22 Erkläre, wie die Operation "kontraktion" auf gewichteten Graphen abläuft. #22 (besser in der neuen Version des Skripts) Was besagt die Aussage "mincut(G) = min { mincut_Q,S(G), mincut(kontraktion(G,{Q,S}))}" und wie beweist man sie? Wie kann man diese Eigenschaft für einen Algorithmus zur MINCUT-Berechnung verwenden? #23 Erkläre den Algorithmus "Irgendein minimaler Q-S-Schnitt". Erkläre genau, welcher Knoten zur Menge A hinzugefügt wird. Welche Knoten werden als Q bzw. S ausgegeben und welcher Q-S-Schnitt ist dann ein minimaler Q-S-Schnitt? #24 Beweise, dass der Algorithmus "Irgendein minimaler Q-S-Schnitt" tatsächlich einen minimalen Q-S-Schnitt berechnet: Was versteht man unter einem aktiven Knoten? Welche "Zwischenbehauptung" gilt für aktive Knoten? Beweise die "Zwischenbehauptung" induktiv! Wieso folgt aus dieser Zwischenbehauptung, dass der berechnete Schnitt ein minimaler Q-S-Schnitt ist? #24/25. Wie sieht der auf der Unterroutine "Irgendein minimaler Q-S-Schnitt" basierende MINCUT-Algorithmus aus? #26 Wie ist die Laufzeit des Algorithmus "Irgendein minimaler Q-S-Schnitt"? Beschreibe dabei zwei mögliche Implementierungen und analysiere, wie die Laufzeiten sich dabei ergeben. #26 Was versteht man unter der amortisierten Rechenzeit/Laufzeit eines Algorithmus? Warum analysiert man diese? #28 Erkläre die UNION-FIND-Datenstruktur, die FIND-Operationen schnell unterstützt und beweise mit Hilfe einer Potenzialfunktion, dass die amortisierte Laufzeit O(n log n) ist. #29 Wie ist die amortisierte Laufzeit bei der UNION-FIND-Datenstruktur, die FIND-Operationen effizient unterstützt? #29 Wie sieht die UNION-FIND-Datenstruktur aus, die UNION-Befehle effizient unterstützt? #30 UNION-FIND mit Bäumen: Wenn ein Baum der Datenstruktur Tiefe h hat, wieviele Elemente enthält er dann mindestens? Beweise Deine Aussage (induktiv)! Gilt diese Aussage mit/ohne Pfadkomprimierung? #31/32 UNION-FIND mit Bäumen: Wie folgt aus der Aussage, dass ein Baum mit Tiefe h mindestens 2 hoch h Elemente enthält, dass eine FIND-Operation höchstens Laufzeit O(log n) hat? #(implizit auf S. 32) Bei der Analyse der amortisierten Laufzeit bei UNION-FIND mit Pfadkomprimierung verwenden wir Datenstrukturen U_i^ohne und U_i^mit. Was ist das? FIND-Befehle mit Pfadkmoprimierung können das Aussehen von Bäumen verändern. Was aber bleibt erhalten? #32 UNION-FIND mit Bäumen: Wie ist der Rang eines Elements definiert? Welchen Baum zieht man für die Definition des Rangs zu Rate? #33 UNION-FIND mit Bäumen: Was versteht man unter der Rangwachstumseigenschaft? Beweise, dass die Rangwachstumseigenschaft in allen Bäumen U_i^mit gilt. (Warum gilt diese nicht etwa *trivialerweise*?) #33 UNION-FIND mit Bäumen: Wieviele Elemente mit Rang r gibt es maximal? Beweise die Aussage. #34 UNION-FIND mit Bäumen: Wie ist die Funktion F(x) definiert, wie ist die Funktion log*(n) definiert, wie stehen die beiden in Beziehung zueinander? #34 UNION-FIND mit Bäumen: Wie sind die Ranggruppen definiert? #35 UNION-FIND mit Bäumen und Pfadkompression: Welche Kostenkonten gibt es bei der Analyse? Wenn man eine Kante von v_i nach v_{i-1} durchläuft, auf welchem Konto werden die Kosten 1 verbucht? #35 UNION-FIND mit Bäumen und Pfadkompression: Welche Laufzeit hat man maximal bei n-1 UNION-Befehlen und m FIND-Befehlen? Beweise Deine Aussage! #36 String Matching: Definiere das Problem. #36 Welchen Zusammenhang gibt es zwischen "String Matching" und endlichen Automaten? An welcher Stelle unterscheidet sich der vorgestellte KMP(Knuth-Morris-Pratt)-Algorithmus von einem endlichen Automaten? #36/37 String Matching: Wieso kann man gegenüber dem trivialen Algorithmus überhaupt etwas sparen? #37 String Matching: Wenn man F(j) kennt und an Stelle j ein Mismatch stattfindet, welche Aktion findet dann statt? #37/38 String Matching: Gib die F-Werte zum String ABACAB an. #38 Beschreibe (in Pseudocode oder auf andere Weise präzise) wie der String-Matching-Algorithmus von Knuth, Morris, Pratt funktioniert. #38 Welche Laufzeit hat der String-Matching-Algorithmus von Knuth, Morris, Pratt? Beweise Deine Aussage. (Auf zwei Arten: anschaulich/mit Potenzialfunktion). #38 Was ist ein Präfixmatch? #39 Wie kann man F(j) aus den Präfixmatchen berechnen? #39 Gib ein paar Präfixmatche für das Wort ABACABABA an. #39 Wie kann man beurteilen, ob (j,j') ein Präfixmatch ist, wenn man alle Präfixmatche (j-1,*) kennt? #39 Beschreibe (mit Pseudocode oder auf andere Weise hinreichend präzise), wie die Fehlerkantenberechnung funktioniert. Welche Laufzeit hat der Algorithmus, wieso ist sie so? (Beweis) #40 Wie ist die Preprocessing-Zeit beim String-Matching-Algorithmus von Knuth, Morris, Pratt? Wie die Query-Zeit? #40 Wieso betrachtet man Approximationsalgorithmen? #41 Wie ist die Güte einer von einem Algorithmus A berechneten Lösung definiert? #41 Wie ist die Güte eines Approximationsalgorithmus A definiert? #41 Was ist ein Approximationsschema, ein polynomielles Approximationsschema, was ein voll polynomielles Approximationsschema? Welche davon sind die praktisch relevanten? #41/Folien Gib Beispiele für (mögliche) Laufzeiten eines PTAS, Beispiele für Laufzeiten eines FPTAS. #41 Was versteht man unter einem Vertex Cover, was unter dem Vertex-Cover-Problem? Gib ein Beispiel an für einen Graphen und Vertex Cover in diesem Graphen. #42 Beschreibe einen Approximationsalgorithmus für Vertex Cover und beweise, dass er Güte 2 hat. #42/43 Wie ist das Set-Cover-Problem definiert? #43 Beweise, dass Set Cover eine Verallgemeinerung von Vertex Cover ist. Verwende dabei die "Matrixsichtweise". #43/44 Was ist (unter einer Annahme, die die Komplexitätstheoretiker für richtig halten) die beste Approximationsgüte, die man für Set Cover in Polynomialzeit erreichen kann? #44 Gib einen Greedy-Algorithmus für Set Cover an. Was versteht man unter den relativen Kosten? Welche Güte hat der Algorithmus? #44/45 Beweise, dass der Greedy-Algorithmus für das Set-Cover-Problem eine Güte von höchstens 1+ H(n) hat! #45 Gib ein Beispiel für eine Set-Cover-Instanz an, die zeigt, dass der Greedy-Algorithmus tatsächlich um fast den Faktor H(n) neben dem Optimum liegen kann. #46 Was versteht man unter dem TSP, was unter dem metrischen TSP? #46 Wieso ist ein minimaler Spannbaum nicht teurer als eine optimale Tour? #46 Was versteht man unter einem Eulerkreis, wann existiert ein solcher, wie schnell kann man einen solchen berechnen? #46 Wie erhält man aus einem Eulerkreis eine Tour? #46 Gib einen Approximationsalgorithmus für das metrische TSP an, der Güte 2 hat. Welche Laufzeit hat er? Beweise die Güte 2! #47 Gib das Verfahren von Christofides an. Welche Güte hat es? Welche Laufzeit? #47 Beweise, dass das Verfahren von Christofides die Güte 3/2 hat! (Wieso hat das kostenminimale Matching höchstens halb soviele Kosten wie eine optimale Tour?) #47 Gib den in der Vorlesung vorgestellten pseudopolynomiellen Algorithmus für das Rucksackproblem an. (Bellmansche Optimalitätsgleichung aufstellen und erklären, Parameter A(i,V) erklären.) Welche Laufzeit hat er? Wann ist er somit effizient? #48 Gib das in der Vorlesung beschriebene FPTAS für das Rucksackproblem an. Welche Laufzeit hat es? Wieso ist es ein FPTAS und nicht nur ein PTAS? #49 Beweise, dass das FPTAS für das Rucksackproblem tatsächlich ein FPTAS ist. #49 (besser: Beweis im aktualisierten Skript) Definiere das Problem Makespan Scheduling. #50 Erkläre den Algorithmus Least Loaded für das Makespan-Scheduling-Problem. Gib ein Beispiel an, wo die berechnete Lösung um (fast) den Faktor 2 schlechter als das Optimum ist. #50 Beweise, dass Least Loaded für das Makespan-Scheduling-Problem eine Güte von 2 hat. #51 Wie funktioniert der Algorithmus LPT für das Makespan-Scheduling-Problem? Welche Güte garantiert er? #51 Beweise, dass LPT für das Makespan-Scheduling-Problem eine Güte von 4/3 hat. #51 Detailfrage zum Beweis, dass LPT für das Makespan-Scheduling-Problem eine Güte von 4/3 hat: Wieso kann man im Beweis jeden *optimalen* Schedule so umbauen, dass die Lastverteilung so wie im Skriptbild aussieht? #52 (bzw. Details im aktualisierten Skript!) Detailfrage zum Beweis, dass LPT für das Makespan-Scheduling-Problem eine Güte von 4/3 hat: Wieso verteilt LPT die Jobs gerade so wie im Skriptbild skizziert? #52 (bzw. Details im aktualisierten Skript!) Beschreibe, wie man mit dynamischer Programmierung bei k verschiedenen Jobgrößen eine optimale Lösung in Zeit O(k*(n hoch (2k+1))) berechnen kann. Begründe dabei die bellmansche Optimalitätsgleichung. #55/56 im aktualisierten Skript Wie sieht das von uns angegebene PTAS für das Makespan-Scheduling-Problem aus? #57 im akt. Skript Zum Beweis, dass der Algorithmus "PTAS für Makespan Scheduling" auch tatsächlich ein PTAS ist: Wie macht sich quantitativ das Aufrunden von pi* zu pi' bemerkbar? #57 (Lemma 4.15) im akt. Skript Beweise, dass die Laufzeit des Algorithmus "PTAS für Makespan Scheduling" n hoch O(1/eps^2) ist. #57 im akt. Skript Zum Beweis, dass der Algorithmus "PTAS für Makespan Scheduling" auch tatsächlich ein PTAS ist: Zeige, dass in Phase 1 ein Schedule für die großen Jobs berechnet wird, dessen Makespan höchstens (1+eps)*OPT ist. #57/58 im akt. Skript Zum Beweis, dass der Algorithmus "PTAS für Makespan Scheduling" auch tatsächlich ein PTAS ist: Zeige, dass in Phase 2 das Verteilen der kleinen Jobs den Makespan auf höchstens (1+2eps)*OPT erhöht. #57 im akt. Skript Gibt es ein PTAS für das Makespan-Scheduling-Problem? Gibt es wohl ein FPTAS dafür? #58 im akt. Skript Was versteht man unter einem randomisierten Algorithmus? Wann heißt er Las-Vegas-, wann Monte-Carlo-Algorithmus? #57 bzw. Erklärung in Vorlesung/Folien Wie ist der Erwartungswert einer Zufallsvariablen definiert? Was versteht man unter der "Linearität der Erwartungswerte"? #57 Wenn X1 und X2 zwei Zufallsvariablen sind: Was kann man über E[X1 * X2] aussagen, was über E[X1+X2]? #58 Wie kann man sich randomisierte Algorithmen veranschaulichen? Wie definiert man die erwartete Laufzeit eines randomisierten Algorithmus? #58 Analysiere folgenden Algorithmus: repeat wirf faire Münze until Münze=0. Welche erwartete Laufzeit hat er? Wie ändert sich diese, wenn die Münze nicht mehr fair ist, sondern mit W'keit p den Wert 0 annimmr? (Rechnung!) #58/59 Algorithmus "Lotto": Zeige, wie man die erwartete Anzahl an Ziehungsversuchen ausrechnen kann! #60/61 Was versteht man unter: Literal, Klausel, reduzierte Klausel. Wie ist MAXSAT definiert, wie MAX-k-SAT? Wie ist der Status dieser beiden Probleme hinsichtlich NP-Härte? #61 Gib einen einfachen Algorithmus für das MAX-k-SAT-Problem an, gib seine Güte an und beweise sie. #61/62 Beschreibe am Beispiel eines einfachen MAX-k-SAT-Algorithmus, wie man diesen derandomisieren kann: a) Wie ist die Potenzialfunktion definiert? b) Welches sind die entscheidenden Eigenschaften dieser? c) Gib den deterministischen Algorithmus an, der sich aus dieser Derandomisierung ergibt. #63 Derandomisierung: Beweise, dass der derandomisierte Algorithmus tatsächlich das Gewünschte leistet, also für MAX-k-SAT-Instanzen eine Variablenbelegung berechnet, die mindestens (1-1/2hochk)*m viele Klauseln erfüllt. #63 Beschreibe, wie man das MAXSAT-Problem äquivalent als mathematisches Programm schreiben kann. Worin besteht dann die Relaxation? #64 Was versteht man unter einem Linearen Programm? Welche Eigenschaften davon sind für uns interessant? #65 Was versteht man unter "Randomisiertem Runden"? #65 Beschreibe einen verbesserten Algorithmus zum Approximieren eines MAXSAT-Problems. #65 Bei der Analyse des Algorithmus "MAXSAT mit LP-Hilfe" haben wir die Wahrscheinlichkeit, dass Klausel j durch das randomisierte Runden erfüllt ist, mit Hilfe von z_j-Dach abgeschätzt. Skizziere, wie man diese Wahrscheinlichkeit analysieren kann, und beschreibe die Ansätze der Rechnung. #65/66 Zeige, dass "MAXSAT mit LP-Hilfe" eine Güte von mindestens (1-1/e) hat. #66 Erkläre Algorithmus MIX für das MAXSAT-Problem. #66 Welche Güte hat Algorithmus MIX für das MAXSAT-Problem? Beweise Deine Aussage. #67 Erkläre den Algorithmus "Randomisierte Kontraktion" für MINCUT. #69 In welcher Laufzeit kann man "Randomisierte Kontraktion" durchführen? Wie ergibt sich diese? #69/70 Wenn mincut(G)=k ist, wieviele Kanten enthält G dann mindestens? Beweis? #70 Welcher Zusammenhang gilt zwischen mincut(G) und mincut(kontrahiere(G,e))? #70 Wie groß ist die W'keit, dass "Randomisierte Kontraktion" einen minimalen Schnitt liefert? Gib die entscheidenden Argumente an, mit denen man diese W'keit beweisen kann. #70/71 Wie verhält sich die Laufzeit/die W'keit, wenn man den Algorithmus "Randomisierte Kontraktion" iteriert? (Beweis!) #72 Welche Laufzeit bekommt man, wenn man "Randomisierte Kontraktion" so oft durchführt, bis die Erfolgsw'keit garantiert von der Form 1-1/poly(n) ist? #73 Wie groß ist die W'keit, dass man den minimalen Schnitt nicht zerstört, wenn man die Kontraktionen bei "Randomisierte Kontraktion" bis zu t Knoten durchführt? #73 Erkläre den Algorithmus "FastCut". Wieso behandelt man den Fall n<=6 extra? #73/74 Welche Laufzeit hat der Algorithmus "FastCut"? Skizziere, wie man diese Laufzeit analysiert! #74/75/76 Wie ist die Erfolgsw'keit von Algorithmus "FastCut"? Wie läuft die Analyse dieser W'keit? #74/75/76 Im Zusammenhang mit dem 2SAT-Problem haben wir einen Random Walk analysiert. Wie sah der Random Walk aus, wie ist die erwartete Laufzeit, bis man in Position 0 ist und wie haben wir diese Laufzeit analysiert? #78/79/80 Wie sah der randomisierte Algorithmus für 2SAT aus? Analysiere diesen Algorithmus: Seine erwartete Laufzeit! #80/81 Wie ist die Entropiefunktion definiert? #81 Wie kann man die Entropiefunktion zur Abschätzung der Binomialkoeffizienten verwenden? #82 Wir haben einen RandomWalk-Algorithmus für das 3SAT-Problem vorgestellt. Wie sah dieser aus? #82 Wie groß ist die W'keit, dass beim 3SAT-Problem der Algorithmus RandomWalk eine erfüllende Belegung findet? #82 Skizziere, wie man die folgende Aussage beweist: die Erfolgsw'keit von RandomWalk bei 3SAT ist im Wesentlichen (1/2) hoch j. j ist dabei der Hammingabstand, den zu Beginn der Algorithmus von einer erfüllenden Belegung hat. #82/83 Wie könnte man die Aussage, dass RandomWalk bei 3SAT Erfolgsw'keit im Wesentlichen (1/2) hoch j hat, direkt zu einem 3SAT-Algorithmus mit erwarteter Laufzeit ca. 1.42 hoch n verwenden? #83 Analysiere die Erfolgsw'keit des 3SAT-Algorithmus, der eine Initialbelegung a auswürfelt und dann RandomWalk(a) startet. Wie analysiert man E[(1/2)^{X_1+...+X_n)]? #84 Beweise, dass der in der Vorlesung vorgestellte 3SAT-Algorithmus erwartete Laufzeit im Wesentlichen (4/3)^n hat. #84 Wann heißen zwei Klauseln unabhängig? #84 In der Vorlesung haben wir einen Algorithmus für 3SAT vorgestellt, der eine erwartete Laufzeit von ca. 1.3302 hoch n hat. Wie funktioniert dieser Algorithmus, was ist seine wesentliche Idee? Skizziere, welche Schritte man machen muss, um die Laufzeit zu analysieren. #85/86 Wir haben in der Vorlesung einen Algorithmus vorgestellt, der bei 3SAT effizient ist, wenn man (nur) eine kleine inklusionsmaximale unabhängige Klauselmenge gefunden hat. Wie funktioniert dieser? #87 Gegeben zwei Algorithmen für das 3SAT-Problem: Der eine ist effizient, wenn "mdach" klein ist, der andere, wenn "mdach" groß ist. Wie analysiert man die "Kombination" der beiden? #87 Was ist die beste Laufzeit eines randomisierten Algorithmus für 3SAT, den wir in der Vorlesung vorgestellt haben? #87 Was versteht man unter einer randomisierten Suchheuristik? Was ist die Grundidee? #88/89 Wann setzt man zum Beispiel evolutionäre Algorithmen ein? #89 Welche Laufzeit analysieren wir immer bei evolutionären Algorithmen? #89/90 Gib an, wie der (1+1)EA funktioniert. Wieso wählt man die Mutationsw'keit so, wie man sie wählt? #90 Was versteht man unter einer f-basierten Partition? Wie ist s(a), s(i) definiert? #90 Wie kann man eine f-basierte Partition benutzen, um die erwartete Optimierzeit eines (1+1)EA zu analysieren? Beweis dazu! #91 Was versteht man unter der Funktion ONEMAX? Welche erwartete Optimierzeit haben wir für den (1+1)EA für ONEMAX bewiesen? #91 Beweise, dass die erwartete Optimierzeit des (1+1)EA auf ONEMAX durch O(nlogn) beschränkt ist. #91 Wann heißt eine Funktion unimodal? #91 Was kann man über die erwartete Optimierzeit des (1+1)EA auf unimodalen Funktionen aussagen? #92 Beweise, dass die erwartete Optimierzeit des (1+1)EA auf unimodalen Funktionen im Wesentlichen n*I(f) ist. #92 Ist die Schranke für (1+1)EAs auf unimodalen Funktionen immer scharf? #92 Wie sind lineare Funktionen definiert? #92 Wieso können wir uns bei der Analyse des (1+1)EAs auf linearen Funktionen auf positive Gewichte und nicht-vorhandenes w_0 beschränken? #92 Wie ist die erwartete Optimierzeit des (1+1)EAs auf linearen Funktionen? #92 Zeige, dass die erwartete Optimierzeit des (1+1)EAs auf linearen Funktionen O(n^2) ist. #92 Wie ist die erwartete Optimierzeit des (1+1)EAs auf Polynomen vom Grad k, die N Terme haben? Beweise Deine Aussage! #92/93 Flussprobleme: Wie ist ein Netzwerk definiert? Wie kann man die Einschränkung der Asymmetrie "aushebeln"? #94 Wie ist ein Fluss in einem Netzwerk definiert? Was versteht man unter einem ganzzahligen Fluss? Wie ist der Wert eines Flusses definiert? Wann heißt ein Fluss maximal? #94/95 Was versteht man unter einem Matching? Was kann man über den Greedy-Algorithmus zur Berechnung eines Matchings aussagen? Beweis! #95 Wann heißt ein Graph bipartit? Warum sind Matchings in bipartiten Graphen praktisch relevant? #96 Erkläre, wie man mit Hilfe eines Flussproblems das Problem "Maximale Matchings in bipartiten Graphen" lösen kann. Beweise Deine Aussagen! #96/97 Wieso scheitert der Versuch, einen maximalen Fluss zu finden, wenn man immer nur "Fluss entlang von Kanten erhöht"? (Beispiel!) #97 Wie ist der Restgraph zu einem Netzwerk und einem Fluss phi definiert? #97 Was versteht man unter einem FV-Weg? #98 Beschreibe den Algorithmus von Ford und Fulkerson. #99 Zeige: Wenn der Markierungsalgorithmus von Ford und Fulkerson die Senke markiert, dann kann man den Wert des aktuellen Flusses erhöhen. Gib an, wie die Flüsse auf den einzelnen Kanten erhöht werden. #99 Flussalgorithmen: Was versteht man unter einem Q-S-Schnitt? Wie ist der Wert eines Q-S-Schnitts definiert? Beispiel zeichnen! #100 Was sagt der Satz "MAXFLOW=MINCUT" aus? Beweise ihn! (Bei der einen Richtung argumentiere einmal intuitiv und einmal "formal präzise"). #100/101 Wieso ist die folgende Aussage richtig:? Wenn der Algorithmus von Ford und Fulkerson die Senke nicht mehr markiert, dann liegt ein maximaler Fluss vor (Beweis!). #101 Analysiere die Laufzeit des Algorithmus von Ford und Fulkerson. Handelt es sich dabei um eine polynomielle Laufzeit? #101 Gib ein Beispiel an, wo der Algorithmus von Ford und Fulkerson tatsächlich eine exponentielle Laufzeit haben kann. #102 Gib von den Flussalgorithmen, die wir in der Vorlesung genauer betrachtet haben, alle Laufzeiten an. #103etc. Ein Graph G mit Distanzen d(v), die den Abstand von einem Knoten Q zu v messen. Wenn d(v) >= d(w)-1 ist und wir fügen eine Kante von v nach w hinzu, was ändert sich dann nicht? (Beweis!) #103 Ein Graph G mit Distanzen d(v), die den Abstand von einem Knoten Q zu v messen. Wenn wir eine Kante von v nach w entfernen: Welche Distanzen können sich dann wie verändern? (Beweis!) #104 Algorithmus von Dinic: Wie ist das Niveaunetzwerk definiert? Wie sind die Knotenmenge V_i definiert, wie die Mengen E_i? #104 In welcher Laufzeit kann man das Niveanetzwerk (für den Algorithmus von Dinic) berechnen? #105 Wann heißt eine Kante saturiert? Was versteht man unter einem Sperrfluss in einem Niveaunetzwerk? #105 Gib einen Algorithmus an, mit Hilfe dessen man einen Sperrfluss berechnen kann. (Den ersten vorgestellten Algorithmus) Erkläre, warum er einen Sperrfluss berechnet. Wie ist seine Laufzeit? Beweise die Laufzeit! #105/106 Wenn man einen Algorithmus A hat, der einen Sperrfluss im Niveaunetzwerk berechnet: Wie erhält man daraus einen Algorithmus zur Berechnung eines maximalen Flusses? #106 Beweise, dass durch das Hinzufügen eines Sperrflusses im Niveaunetzwerk zu einem Fluss phi die Entfernung der Quelle von der Senke um mindestens eins größer wird. #106 Erkläre den Algorithmus von Malhotra, Kumar, Maheshwari zur Berechnung eines Sperrflusses: Wie ist das Potenzial eines Knotens definiert? Beschreibe zunächst intuitiv, dann anhand von Pseudocode, wie die Prozedur Forward(v) funktioniert. Erkläre dabei, wofür die Queue benutzt wird, was man mit dem Parameter Überschuss[v] erreichen will etc. #107 Beschreibe den Algorithmus Forward-Backward-Propagation in Pseudocode. Du darfst dabei Backward(v) und Forward(v) als Unterroutinen benutzen. Erkläre, warum dieser Algorithmus einen Sperrfluss berechnet. Wie ist seine Laufzeit? #108 Welche Laufzeit hat der Algorithmus Forward-Backward-Propagation? Beweise, dass die Laufzeit so ist. Zu welcher Laufzeit kommt man dann zur Berechnung eines maximalen Flusses? #108 Algorithmenfamilie von Goldberg und Tarjan: Wie ist für einen Knoten v der Wert e(v) definiert? #109 Welche Eigenschaften müssen für einen Preflow erfüllt sein? (Definition!) #109 Algorithmenfamilie von Goldberg und Tarjan: Was versteht man unter einem aktiven Knoten? #109 Zeige, dass es für jeden aktiven Knoten v im Restgraphen Rest_phi einen Weg nach Q gibt, wenn phi ein Preflow ist. #109 Was versteht man unter einer gültigen Knotenmarkierung d für einen Preflow phi? #109 Beweise folgendes Lemma: Wenn phi ein Preflow ist und d eine gültige Markierung für phi, dann gibt es im Restgraphen keinen Weg von Q nach S. #110 Flussalgorithmus von Goldberg/Tarjan: Wann heißt eine Kante "wählbar"? #110 Beschreibe den generischen Preflow-Push-Algorithmus. Was passiert bei der Push(v,w)-Operation, was bei Relabel(v)? Wann sind diese Operationen anwendbar? #110 Wann heißt eine Push-Operation saturierend? #110 Zeige, dass beim Flussalgorithmus von Goldberg und Tarjan d stets eine gültige Knotenmarkierung bleibt! #111 Wieso ist phi ein maximaler Fluss, wenn der Algorithmus von Goldberg und Tarjan stoppt? #111 Algorithmus von Goldberg und Tarjan: Wieso wird d(v) nie kleiner? Beweis! Durch welchen Wert ist d(v) nach oben beschränkt? Beweis! #111 Algorithmus von Goldberg und Tarjan: Wieviele Relabel-Operationen gibt es maximal? Größenordnung reicht! Beweis! Wieviele saturierende Push-Operationen gibt es maximal? Größenordnung reicht! Beweis! #111 Algorithmus von Goldberg und Tarjan: Wieviele nicht-saturierende Push-Operationen gibt es maximal? Beweise mit Potenzialfunktion! #111/112 Algorithmus von Goldberg und Tarjan: Wieviele Basisoperationen reichen (bei beliebiger Reihenfolge der Operationen) maximal aus? #112 Algorithmus von Goldberg und Tarjan: Wie kann man an die nächste erlaubte Basisoperation effizient herankommen? (Wie implementiert man das?) #112 Algorithmus von Goldberg und Tarjan: Beschreibe Push/Relabel(v) und zeige, dass Relabel nur dann angewendet wird, wenn es angewendet werden darf. #112 Beschreibe den generischen Preflow-Push-Algorithmus, der die Operation Push/Relabel(v) verwendet! Welche Laufzeit hat er maximal? Beweis! #113 Mit welcher Strategie erreicht man beim Algorithmus von Goldberg und Tarjan die Laufzeit n hoch 3? #114 Algorithmus von Goldberg und Tarjan: Zeige, dass die FIFO-Strategie zu Laufzeit n hoch 3 führt. #114/115 Was besagt die Highest-Level-Selection Rule? #115 Motiviere, warum man sich mit Algorithmen für arithmetische Operationen wie Exponentiation etc. beschäftigt. #116 Wie funktioniert prinzipiell ein Public-Key-System? #118 Erkläre das RSA-System! #118/119 Schreibe in Pseudocode einen effizienten Potenzierungsalgorithmus hin! Wieviele Operationen werden bei der Berechnung von x hoch n ausgeführt? Beweis! #119 Gib in Pseudocode den ggT-Algorithmus an. Welche Laufzeit hat er? Beweis! #120 Gib in Pseudocode den Algorithmus zur Berechnung von Inversen modulo a an. Wie ist seine Laufzeit? Beweise, dass tatsächlich das Inverse berechnet wird. #121 Definiere die folgenden Begriffe: Z_n, Z_n^*, ord_n(a), quadratischer Rest, erzeugendes Element. #122 Zahlentheoretische Grundlagen: Was versteht man unter dem Index index_g(a)? Wann heißt eine Zahl n quadratfrei? Was ist lambda(n)? #122 Gib Beispiele an für quadratische Reste und erzeugende Elemente modulo 7. #122 Wie kann man (ineffizient) lambda(n) ausrechnen? #122 Zeige: Modulo einer ungeraden Primzahl p ist die Hälfte der Zahlen in Z_p^* quadratischer Rest. #122 Wann ist a hoch e äquivalent zu 1 modulo n? Beweis! #123 Wie lautet der (kleine) Satz von Fermat? #123 Was versteht man unter einer Carmichael-Zahl? Wie kann man eine Carmichael-Zahl n anhand ihres lambda(n)-Wertes erkennen? Beweis! #123 Welche Eigenschaften gelten für eine Carmichael-Zahl? Beweis! #124 Wie ist das Jacobi-Symbol definiert? Beispiele für einige Werte angeben! #124 Gib einige Rechenregeln für Jacobi-Symbole an. Was ist das quadratische Reziprozitätsgesetz? #124/125 Gib an, wie man das Jacobi-Symbol effizient berechnen kann. Wie ist die Laufzeit? Gib Argumente an, warum die Laufzeit so ist. #125 Was versteht man unter dem chinesischen Restsatz? #126 Gib einen effizienten Algorithmus an, der (beim chinesischen Restsatz) ein Gleichungssystem, das auf Modulo-Gleichungen besteht, löst. #127 Welche Beziehung besteht zwischen a hoch (n-1)/2 und dem Jacobisymbol (a|n)? Beweis in beiden Richtungen! #127/128 Gib den Algorithmus von Solovay und Strassen an. #128 Algorithmus von Solovay und Strassen: Welche Laufzeit hat er? Was kann man über sein Verhalten aussagen? #128 Beweise den Satz, dass E(n)= Z_n^* genau dann ist, wenn n prim ist. #129 Wieso ergibt sich die Fehlerwahrscheinlichkeit von 1/2 bei k=1 im Algorithmus von Solovay und Strassen? #129/130