Du befindest dich hier: FSI Informatik » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Seminar "Hallo Welt fuer Fortgeschrittene"

Seminar "Hallo Welt fuer Fortgeschrittene"

Prüfer: Tobias Werth, Daniel Brinkers

Graphalgorithmen 1:

  • Was sind implizite Graphen und was unterscheidet sie von expliziten?
  • Was sind Zusammenhangskomponenten?
  • Wie funktioniert der Algorithmus von Kosaraju und warum?

Graphalgorithmen 2:

  • Welche Moeglichkeiten gibt es, Graphen zu speichern?
  • Wie funktioniert der Algorithmus von Dijkstra?
  • Was genau speichert man beim Algorithmus von Dijkstra im Fibonacci-Heap?
  • Welchen Aufwand hat welche Operation im Fibonacci-Heap?
  • Wieso funktioniert der Algorithmus von Dijkstra bei negativen Kantengewichten nicht?
  • Wie loest man das Problem stattdessen?
  • Wie lautet der Algorithmus von Moore-Bellman-Ford? (incl. Pseudocode)

Fluesse, Schnitte und bipartite Graphen:

  • Was benoetigt man zum Finden eines Flusses?
  • Wodurch genau ist die Flusskapazitaet begrenzt?
  • Wie funktioniert das Finden der Fluesse theoretisch und algorithmisch?
  • Was sind Reduktionen und wo wendet man sie an?
  • Was sind Matchings und wie kann man ein maximales Matching finden?