Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Nebenfächer » mathematik » Flüsse (12 Punkte)   (Übersicht)

Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen der Seite angezeigt.

Link zu der Vergleichsansicht

Beide Seiten, vorherige ÜberarbeitungVorherige Überarbeitung
pruefungen:nebenfach:mathematik:linkomopt2017-02 [23.02.2017 16:23] – christian-depruefungen:nebenfach:mathematik:linkomopt2017-02 [23.02.2017 16:29] (aktuell) – christian-de
Zeile 4: Zeile 4:
  
 ==== Flüsse (12 Punkte) ==== ==== Flüsse (12 Punkte) ====
-  - MaxFlow mit augmentierenden Wegen berechnen (war relativ aufwändig mit 3 augmentierungen und hat viel Zeit gekostet. Hier sollte man auf jeden Fall nicht mehr denken müssen)+  - MaxFlow mit augmentierenden Wegen berechnen (war relativ aufwändig mit 3 Augmentierungen und hat viel Zeit gekostet. Hier sollte man auf jeden Fall nicht mehr denken müssen, um Zeit zu sparen.)
   - MinCostFlow-Problem mit schon gegebenem zulässigen Fluss und einer durchzuführenden Kreislöschung + Angabe Gesamtkosten    - MinCostFlow-Problem mit schon gegebenem zulässigen Fluss und einer durchzuführenden Kreislöschung + Angabe Gesamtkosten 
 Beide Graphen hatten Umfang ~6 Knoten Beide Graphen hatten Umfang ~6 Knoten
Zeile 24: Zeile 24:
 ==== Verständnis (~12 Punkte) ==== ==== Verständnis (~12 Punkte) ====
   - Angabe ob Laufzeiten (z.B. O(c log n)) polynomiell sind oder nicht (ohne Begründung)   - Angabe ob Laufzeiten (z.B. O(c log n)) polynomiell sind oder nicht (ohne Begründung)
-  - Wahr/Falsch-Aussagen (ohne Begründung) zu Graphen-Problemen+  - Wahr/Falsch-Aussagen (ohne Begründung) zu Graphen-Problemen (kürzeste Teilwege, ...)
   - Optimalitätskriterium für kürzeste Wege angeben   - Optimalitätskriterium für kürzeste Wege angeben
   - 1x beweisen und 1x widerlegen, dass gegebene Mengen Matroide sind   - 1x beweisen und 1x widerlegen, dass gegebene Mengen Matroide sind