Allgemeine Informationen

Veranstaltungsname	Vorlesung: Network Flow (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.
Semester	WS 2017/18
Aktuelle Anzahl der Teilnehmenden	0
Heimat-Einrichtung	Theoretische Informatik
Veranstaltungstyp	Vorlesung in der Kategorie Lehre
Erster Termin	Dienstag, 17.10.2017 15:45 - 17:15
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 ist auf der folgenden Webseite im entsprechenden Semester zu finden: https://thiserver.informatik.uni-augsburg.de/index_semester.html
Sonstiges	Aktuelle Informationen zur Veranstaltungen erhalten Sie auf der Internetseite des Lehrstuhls (https://thiserver.informatik.uni-augsburg.de/index_semester.html ) sowie in der Vorlesung.
ECTS-Punkte	8

Lehrende

Prof.Dr. Torben Hagerup

Räume und Zeiten

Keine Raumangabe: Dienstag: 15:45 - 17:15, wöchentlich; Donnerstag: 12:15 - 13:45, wöchentlich

Studienbereiche

Fakultät für Angewandte Informatik > Informatik

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.

Anmelderegeln

Diese Veranstaltung gehört zum Anmeldeset "Anmeldung gesperrt (global)".

Folgende Regeln gelten für die Anmeldung:

Die Anmeldung ist gesperrt.