TU Wien:Algorithmics VU (Szeider)/Prüfung 2013W

Aus VoWi
Zur Navigation springen Zur Suche springen

Prüfungsfragen: alles ohne gewähr

  • Nennen Sie einen shortest path algorithmus der für einen bestimmten Knoten alle shortest paths zu den anderen Knoten berechnen kann und mit negativen Kanten/Cycles umgehen kann
    • Bellman Ford
    • Nennen Sie weitere Shortest path algorithmen + Erklärung
  • Wieso sind beim Programmierbeispiel SCF, MCF oder MTZ notwendig? Was garantieren sie?
    • ohne diese methoden keine Garantie, dass Lösung wirklich ein Spanning Tree ist. Graph kann nicht zusammenhängend sein.
    • Weitere Fragen zur Programmierabgabe. Was manche Constraints garantieren?
  • Wie arbeitet CPLEX?
    • Branch and Bound erklären
    • Was macht die Relaxation?
    • Wieso ist die LP-Relaxation von Vorteil?
      • ermöglicht polynomielle Laufzeit
Abgerufen von „https://vowi.fsinf.at/index.php?title=TU_Wien:Algorithmics_VU_(Szeider)/Prüfung_2013W&oldid=188802“