Sie befinden sich hier: Termine » Prüfungsfragen und Altklausuren » Hauptstudiumsprüfungen » Lehrstuhl 2 » Seminar "Hallo Welt fuer Fortgeschrittene"   (Übersicht)

Seminar "Hallo Welt fuer Fortgeschrittene"

Prüfer: Tobias Werth, Daniel Brinkers

Graphalgorithmen 1:

  1. Was sind implizite Graphen und was unterscheidet sie von expliziten?
  2. Was sind Zusammenhangskomponenten?
  3. Wie funktioniert der Algorithmus von Kosaraju und warum?

Graphalgorithmen 2:

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

Fluesse, Schnitte und bipartite Graphen:

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