Digicampus
Lecture: Flüsse in Netzwerken - Details
You are not logged into Stud.IP.
Lehrveranstaltung wird online/digital abgehalten.

General information

Subtitle 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.
Course number INF-0045
Semester SS 2020
Current number of participants 65
Home institute Theoretische Informatik
Courses type Lecture in category Teaching
First date Mon , 20.04.2020 14:00 - 15:30, Room: (1054 N)
Pre-requisites Empfehlenswert: Gutes Verständnis des Informatik III-Stoffes, insbesondere im Bereich der Graphenalgorithmen.
Modul Informatik 3 (INF-0111) - empfohlen
Learning organization 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.
Miscellanea Aktuelle Informationen zur Veranstaltungen erhalten Sie durch die Ankündigungs-Funktion von Digicampus.
ECTS points 8

Course location / Course dates

(1054 N) Monday: 14:00 - 15:30, weekly (13x)
Tuesday: 14:00 - 15:30, weekly (13x)

Module assignments

Comment/Description

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.