TU Wien:Algorithmics VU (Szeider)/Prüfung 2018-01-15
LV = Mein Lösungsvorschlag ohne Garantie
1. Ein Flow-Network war gegeben. Dazu den Residual Graph zeichnen und argumentieren, ob es sich bei dem Flow um einen Max-Flow handelt.
2a. Zwei Graphen waren gegeben. Man sollte beweisen, ob diese Graphen planar oder nicht waren. LV: Durch Minor-Bildung nach K5 oder K33 suchen.
2b. Angenommen man habe einen randomisierten Algorithmus mit Laufzeit O(n²logn) für eine bestimmte Graph-Klasse, der für jeden Graph dieser Klasse ein 5-Coloring mit einer Wahrscheinlichkeit von mindestens 1/n liefert: Hat jeder Graph dieser Klasse ein 5-Coloring? (LV: Ja, sonst wäre die Wahrscheinlichkeit für jenen Graphen 0 was kleiner als 1/n ist). Wie kann man den Algorithmus anpassen, damit er immer ein Coloring findet und wie ist die Laufzeit? (LV: Wiederholen, bis mans findet. O(n³logn)) Wie kann man den Algorithmus finden, damit man alle m möglichen Colorings findet und wie ist die Laufzeit? (LV: wiederholen bis man alle Colorings hat).
3a: Ein Voronoi-Diagramm war gegeben, wobei galt, dass keine 4 Punkte auf dem Rand eines Kreises liegen. Delaunay-Graph zeichnen. 3b: Multiple-Choice-Fragen zu Eigenschaften von bestimmten Voronoi-Diagrammen. 3c: SED von drei Punkten gegeben und sechs Positionen für einen möglichen vierten Punkt. Welche Position sorgt für die längste Laufzeit des (nicht-randomisierten) SED-Algorithmus und welche für die kürzeste? 3d: Gegeben ein Set P von Punkten mit der SED S. Gilt, dass die Voronoi Cells für alle Punkte innerhalb von S bounded sind? (LV: Nein, mittels Gegenbeispiel)
4: Ein Problem mit Zügen und Stationen, wobei gewisse Stationen ausgewählt wurden. Weiß die Angabe nicht mehr genau. Gefragt war ein FPT-Algorithmus dafür, wobei man Resultate aus der Vorlesung verwenden konnte. (LV: Darstellung als d-Hitting-Set)
5: Dynamic Programming Algorithmus für SAT mittels Tree Decomposition und Primal Graph. Man sollte für jede Art von Node einer nice tree decomposition (leaf, introduce, forget und join) anhand jeweils eines Beispiels die Records berechnen.
6. Ein großes Mixed Integer Linear Programming Modellierungsproblem. Ca wie folgt: Es gibt eine Fabrik und j=10 Kunden. Wir haben k=4 Trucks. Jeder Kunde hat einen Bedarf dj. Ein Truck kann bis zu 5 Kunden bedienen, wobei die Kunden 1 und 7 von anderen Trucks bedient werden müssen. Verwenden wir einen Truck, zahlen wir für diesen ck Kosten (insgesamt, nicht pro Fahrt oder ähnliches). Die Kosten sollen minimiert werden.