Digicampus
Vorlesung: Flüsse in Netzwerken - Details
Sie sind nicht in Stud.IP angemeldet.
Lehrveranstaltung wird online/digital abgehalten.

Allgemeine Informationen

Veranstaltungsname Vorlesung: Flüsse in Netzwerken
Untertitel Kenntnis und Verständnis verschiedener Flussalgorithmen und ihrer Analyse; Fähigkeit zur selbstständigen Modellierung durch Flussprobleme, zur Bewertung der Modellierung und zur Auswahl geeigneter Flussalgorithmen für jedes Modell.
Veranstaltungsnummer INF-0045
Semester SS 2020
Aktuelle Anzahl der Teilnehmenden 49
Heimat-Einrichtung Theoretische Informatik
Veranstaltungstyp Vorlesung in der Kategorie Lehre
Erster Termin Montag, 20.04.2020 14:00 - 15:30, Ort: (1054 N)
Voraussetzungen Empfehlenswert: Gutes Verständnis des Informatik III-Stoffes, insbesondere im Bereich der Graphenalgorithmen.
Modul Informatik 3 (INF-0111) - empfohlen
Lernorganisation Lern- und Arbeitstechniken; analytisches Denken; präzises Formulieren.
Online/Digitale Veranstaltung Veranstaltung wird online/digital abgehalten.
Hauptunterrichtssprache deutsch
Literaturhinweise Das Skript zur Veranstaltung wird im Digicampus hochgeladen.
Sonstiges Aktuelle Informationen zur Veranstaltungen erhalten Sie durch die Ankündigungs-Funktion von Digicampus.
ECTS-Punkte 8

Räume und Zeiten

(1054 N)
Montag: 14:00 - 15:30, wöchentlich (13x)
Dienstag: 14:00 - 15:30, wöchentlich (13x)

Kommentar/Beschreibung

Die Vorlesung behandelt Flüsse in Netzwerken, Algorithmen zu ihrer Berechnung sowie Anwendungen von Flüssen bei der Modellierung und Lösung anderer algorithmischer Probleme. Ein Netzwerk kann man sich als ein System von „Rohrleitungen“ vorstellen, die eine bestimmte „Ware“ transportieren können. Jedes Rohr hat eine Kapazität, die angibt, wieviel Ware pro Zeiteinheit durch das Rohr fließen kann; hierbei entstehen eventuell zusätzlich Kosten, die von dem Rohr abhängen. Bei einem vorliegenden Netzwerk kann man sich eine Fülle algorithmischer Fragen stellen. Zentral für uns wird das Problem sein, einen möglichst großen Fluss an Waren von einer ausgezeichneten Quelle zu einer ausgzeichneten Senke zu erreichen (Max-Flow-Problem). Wir werden einige der besten Algorithmen für dieses Problem kennenlernen, insbesondere den Ende des 20. Jahrhunderts entdecketen Binary-Blocking-Flow-Algorithmus von Goldberg und Rao. Auch das Min-Cost-Max-Flow-Problem wird zur Sprache kommen.