Klausurvorbereitung

Was sind wahre Aussagen über heuristische Algorithmen?

• Heuristische Algorithmen funktionieren nur bei kleinen Problemgrößen.

• Heuristische Algorithmen garantieren die optimale Lösung.

• Heuristische Algorithmen liefern oft gute, aber nicht notwendigerweise optimale Lösungen.

• Heuristische Algorithmen nutzen Näherungsverfahren oder Erfahrungswerte, um Entscheidungen zu treffen.

Ist diese Heuristik konsistent?

• Ja

• Nein

Welche dieser Regeln gelten immer bei einer konsistente Heuristik?
h(n):= Heuristikfunktion eines Knoten n

c(n,n'):= Kantengewicht der Kante zwischen Knoten n zu n'

d(n) := minimale tatsächlichen Kosten zum Ziel vom Knoten n

• Wenn für alle Knoten n und deren Nachfolger n′ gilt:
  h(n)-h(n′)≤c(n,n′)

• Wenn für alle Knoten n und deren Nachfolger n′ gilt:
  h(n)≤h(n′)

• Die Heuristik überschätzt immer die tatsächlichen Kosten zum Ziel, also
  d(n) < h(n)
  für alle Knoten n.

• Jede konsistente Heuristik ist auch immer zulässig.

Welche der folgenden Eigenschaften treffen auf Schnittstellen/Interfaces zu?

• Sie haben fast nur Methodensignaturen.

• Sie können instantiiert werden.

• Sie können konstante Attribute haben.

• Sie können nur statische Methoden haben.

Was ist die Laufzeit von diesem dynamisch programmatischen Code?
(@cache Annotation ins Python sorgt dafür dass berechnete Ergebnise gecached werden und der Code "memoization" nutzt)

• O(n^2)

• O(n)

• O(n^3)

• O(Anzahl an eindeutigen states) * O(cached Komplexität)

Welche Laufzeit hat die Funktion f4?

• O(n log n)

• O(log n)

• O(n)

• O(n²)

Welche Aussagen über Branch and Bound sind wahr?

• Durch Schranken können Teilprobleme, die keine bessere Lösung mehr liefern ausgeschlossen werden

• Das Verfahren eignet sich nur für kontinuierliche Optimierungsprobleme und nicht für ganzzahlige oder diskrete Probleme.

• Branch and Bound liefert nur Näherungslösungen und keine exakten Optima.

• Im ungünstigsten Fall kann Branch and Bound auf eine vollständige Enumeration aller Lösungen hinauslaufen.

Welche Aussagen sind wahr?

• Djikstra mit indizierter Warteschlange hat einen Speicherbedarf in O(V).
  (bei nur positiven Kantengewichten)

• Kruskal hat eine Laufzeit in O(E log E)

• Djikstra mit PriorityQueue hat eine Laufzeit in O(E log V).
  (bei nur positiven Kantengewichten)

• Prim mit indizierten WarteSchlange hat einen Speicherbedarf von O(E LogV)