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.
Nächste Überarbeitung | Vorherige Überarbeitung | ||
pruefungen:nebenfach:mathematik:linkomopt2017-02 [23.02.2017 16:23] – angelegt christian-de | pruefungen:nebenfach:mathematik:linkomopt2017-02 [23.02.2017 16:29] (aktuell) – christian-de | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
**Themen-Skizze der schriftlichen 10-ECTS-Prüfung vom 23.02.2017: | **Themen-Skizze der schriftlichen 10-ECTS-Prüfung vom 23.02.2017: | ||
- | Vom Schwierigkeitsgrad her machbar, zeitlich seeeeehr anspruchsvoll... | + | Vom Schwierigkeitsgrad her machbar, zeitlich seeeeehr anspruchsvoll... |
==== Flüsse (12 Punkte) ==== | ==== Flüsse (12 Punkte) ==== | ||
- | - MaxFlow mit augmentierenden Wegen berechnen (war relativ aufwändig mit 3 augmentierungen | + | - MaxFlow mit augmentierenden Wegen berechnen (war relativ aufwändig mit 3 Augmentierungen |
- 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/ | + | - Wahr/ |
- 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 | ||