Die Vorlesung behandelt verschiedene Probleme aus der theoretischen Informatik und Algorithmen zur Lösung dieser. Dabei wird versucht, schrittweise effizientere Algorithmen zu nutzen, indem Probleme in erweitert, umgeformt oder in bereits behandelte Probleme umgewandelt werden. Themen:

• Flussnetzwerke und Flussalgorithmen
• Matchings in bipartiten Graphen
• TODO

Zu den Vorlesungen wird ein altes Skript von Prof. Dietzfelbinger sowie der Foliensatz als Handout angeboten. In letzterem sind keine Beweise enthalten. Diese werden als Tafelanschrieb in der Vorlesung präsentiert.

Inhaltlich gibt es Überschneidungen zur Vorlesung Graphen und Algorithmen. Daher bietet sich diese als Ergänzungsvorlesung an, um Probleme noch einmal aus einem anderen Blickwinkel und mit anderen Erklärungen hören zu können.

Zur Übung werden hauptsächlich Beweise und Algorithmen zu Problemen mit Bezug zur Vorlesung gesucht. Die Übungsaufgaben sollen vor dem Übungstermin vorbereitet und dann in der Übung vorgestellt werden. Die Aufgaben werden im Laufe der Vorwoche veröffentlicht.

• WS23/24