Fragen

Da ich zur Vorbereitung meiner eigenen Prüfung eine Zusammenstellung von Fragen aus mehreren Prüfungsprotokollen sowie den Hinweisen aus dem Vorgespräch mit Dr. Damaschke geordnet nach Kurseinheiten gemacht habe, beschränke ich mich hier nicht auf die mir persönlich gestellten Fragen.

• Wann ist ein Problem NP-vollständig?
  • Definition
• Was ist ein Eulerkreis? Gibt es ein Kriterium für die Existenz?
  • Satz von Euler: Anzahl der Knoten mit ungeradem Grad ist 0 oder 2 (Beweis angeben)
• Wie sieht es mit der Umkehrung aus?
  • Gilt auch (Beweis angeben), Komplexität: linear
• Hamiltonkreis: Wie ist die Komplexität für das Entscheidungsproblem?
  • NP-vollständig (umfangreicher Beweis mit Reduktion auf 3SAT)
• Zusammenhang zwischen Hamiltonkreis und Problem des Handlungsreisenden
  • TSP definieren, die leichte Reduktion durchführen

• Wie bestimmt man die topologische Ordnung?
  • Knoten mit indeg(v) = 0 müssen in einer Schlange gespeichert werden, um Linearzeit zu wahren.
• Wie kann man feststellen, ob ein ungerichteter Graph zusammenhängend ist?
  • DFS mit nur einem Kellerdurchlauf
• Wie findet man die zweifach zusammenhängenden Komponenten? Was ist das überhaupt?
  • Lemma 3.2.11 und 3.2.12
  • Zusammenhängend und keine Artikulationspunkte
  • Wurzelknoten in DFS-Baum hat Grad > 1
• Was sind chordale Graphen? Gibt es Charakterisierungen?
  • Definition
  • jeder minimale Separator ist Clique
  • besitzt p.e.o.
  • Komplexität: polynomial
  • Verfahrensidee: simpliziale Knoten suchen
• Was ist eine p.e.o.? Wie benutzt man das, um Chordalität zu erkennen?

• Warum ist das Steinerbaum-Problem NP-vollständig?
• Was ist ein Minimalgerüst? Was für Algorithmen zur Erzeugung von Minimalgerüsten gibt es?
  • Definition
  • Algorithmen von Jarnik, Prim, Dijkstra, Kruskal
  • Komplexität nennen und begründen

• Wie kann man zu einem gerichteten Graphen die reflexive und transitive Hülle bestimmen?
  • Verallgemeinerte Matrixmultiplikation auf dem booleschen Semiring. (alternativ: auf Semiring R)
• Wie kann man in gerichteten azyklischen Graphen die kürzesten Wege bestimmen?
• Wie bestimmt man zu je zwei Knoten, ob ein Weg zwischen ihnen existiert?
  • Transitive Hülle, starker Zusammenhang
  • Lösung mit verallgemeinerter Matrixmultiplikation

• Definition von Netzwerken, zulässigem Fluß und Gesamtfluß
  • G gewichteter Graph ohne Schlinge, ohne parallele Kanten; Quelle und Senke; Kapazitätsfunktion
  • Fluß bestimmt durch zwei Kriterien: >= 0, <= c(E); Summe der Zu- und Abflüsse gleich 0 außer in Quelle und Senke
• max-flow-min-cut-Theorem
• Was ist die Kapazität eines Schnitts?
  • Summe V\S
• Gibt es effiziente Algorithmen? Gibt es immer eine Lösung?
  • Algorithmus von: Ford-Fulkerson, Diniek (flußvergrößernder Pfad gesucht)
  • Lösung nur bei ganzzahligen Flüssen garantiert

• Es gibt verschiedene Kenngrößen. Was können Sie über deren Komplexität sagen?
  • Gemeint waren a_E, a_E, a_V, b_E, b_V
  • In beliebigen bzw. paaren Graphen gilt:
    a_E polynomiell bzw. polynomiell
    a_V NP-vollständig bzw. polynomiell
• Unterscheidung zwischen allgemeinen und paaren Graphen
• Wie findet man die a_E?
  • Maximalflußproblem und Ergänzungspfadmethode
• Wie kann man erkennen, daß a_V NP-vollständig ist?
  • Zusammenhang a_V + b_V = |V|
• Wie sieht es mit der Komplexität von c_E und c_V aus?
  • 2COL, 3COL. Bestimmung des chromatischen Index mit Hilfe der Sätze von König, Hall, Mendelsohn/Dulmage
  • In beliebigen bzw. paaren Graphen gilt:
    c_E NP-vollständig bzw. polynomiell
    c_V NP-vollständig bzw. linear
• Knoten- und Kantenfärbungen
  • Färbungsproblem im allgemeinen NP-vollständig
  • Zerlegung in minimale Anzahl unabhängiger Knotenmengen
  • Algorithmus zur Erzeugung minimaler Zerlegungen
• Was ist die chromatische Zahl?
• Was ist ein paarer Graph?
• Was sind Zuordnungen? Maximale Zuordnungen, minimale Knotenüberdeckungen?
• Unabhängige Knotenmengen: Wie sieht die Komplexität aus?
  • NP-vollständig bei beliebigen Graphen, für paare Graphen polynomiell; Satz von König für paare Graphen
• Idee für Algorithmus für 2-Farbigkeit
  • Paare Graphen: Tiefensuche; Knoten immer abwechselnd färben, Rückwärtskanten betrachten, ob passend

Klar erkennbar ist, daß der Stoff der Kurseinheit 7 fast 50 % der Fragen ausmacht. Das war auch in meiner Prüfung so. Darauf sollte man sich wohl einstellen

Eindruck

Für die Vorbereitung dieser Prüfung hatte ich ein persönliches Vorgespräch mit Dr. Damaschke und habe außerdem - zum ersten Mal - von der Möglichkeit Gebrauch gemacht, als Zuhörer an einer Prüfung teilzunehmen. Trotzdem hatte ich dann in meiner eigenen Prüfung einige Probleme, mich auf den Fragestil von Dr. Damaschke einzustellen. Da der Kurs alles andere als leicht ist, war ich allerdings auch ausgesprochen nervös. Daher führe ich meine gelegentliche Begriffsstutzigkeit bei seinen Fragen vor allem darauf zurück.

Einen Ratschlag kann ich allerdings geben: Auch eigentlich selbstverständliche Dinge sollte man unbedingt erwähnen. In meiner Prüfung passierte es zweimal, daß Dr. Damaschke zu meinen Antworten ergänzende Anmerkungen machte. Dazu meinte ich dann, daß das doch ganz selbstverständlich so sei, worauf er erwiderte "Ja sicher, aber Sie haben es nicht gesagt!"

Insgesamt ist Dr. Damaschke ein sehr fairer Prüfer. Er läßt Zeit zum Nachdenken und bringt einen bei Unklarheiten durch geschicktes Nachfragen wieder auf's richtige Gleis. Kommt man letztlich auf die richtigen Antworten, so wirken sich zwischenzeitliche Unsicherheiten minimal bis gar nicht auf die Bewertung aus.

Viel Erfolg!