TU Wien:Algorithmics VU (Raidl)/Prüfungsfragen WS2013

From VoWi
Jump to navigation Jump to search

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