| Tag | ||||
|---|---|---|---|---|
| 5.7 | Sa | Lernplan + Notizen Matching | ||
| 6.7 | So | Notizen Flows | ||
| 7.7 | Mo | Oma + BA | ||
| 8.7 | Di | Notizen Scheduling Problems & LP | ||
| 9.7 | Mi | Notizen Matroids | ||
| 10.7 | Do | Thema zum vorstellen entscheiden | ||
| 11.7 | Fr | Lisa | ||
| 12.7 | Sa | Lisa | ||
| 13.7 | So | Lisa | ||
| 14.7 | Mo | Übungen durch gehen | ||
| 15.7 | Di | Auswendig lernen + Präsi üben | ||
| 16.7 | Mi | Auswendig lernen + Präsi üben | ||
| 17.7 | Do | AA Fachgespräch |
Themen
Aufgaben
- Notizen vervollständigen
- Übungen durch gehen
- Themen map machen
- Thema zum vorstellen entscheiden
- Auswendig lernen
- Präsi üben
TODO
- Dinitz’ Algorithm
- Preflow Push
- Generic Cycle-Canceling Algorithm
Aus Vorbereitungs Stunde
-
blossom nicht exact → grob
-
stable matching ziemlich gut
was sind die probleme die wir angschaut haben
ist es in poly zeit
laufzeiten genauer -
push relable erst generisch → schlect, aber dann können wir den verbessern
-
beweis idee → potential function number pushes bounden
-
cycle canceling → netzwerk kann zerlegt werden
-
scheduling probleme erklären
-
probleme erklären
-
matching als LP / ILP
-
erst als ILP → LP
-
LP können in poly zeit gelöst werden aber egal in welchen
-
LP relaxation speration orical verstehen → kann erkennen wo das problem liegt (das muss in poly zeit gehen)
-
ILP kann man nicht in poly Zeit lösen, da man damit NP probleme darstellen kann
-
primal zu dual LP
-
unimodular → die optimale LP lösung ist immer integer
-
TU → matching
-
Matroid → welche Probleme sind matriod
-
greed erklären können
-
matroid genau dann wenn greedy
-
dann beispiel für matroid problem
-
wie bei kuskal
-
wie zählen wie oft wir das orical aufrufen → linear
-
MST Beispiel malen für matriods
-
Struktur ist das und das
-
Was wollen wir das damit machen
vorstellung + noch 3 Themen