| 150 220 |
Effiziente Algorithmen
4st., Mo, Do 14-16, NA 2/24 |
Simon |
Voraussetzungen:
Vordiplomskenntnisse und Vorlesung über Datenstrukturen.
Kommentar:
Es handelt sich um eine Lehrveranstaltung des Hauptstudiums
Mathematik. Sie kann sowohl in das Gebiet der Praktischen als auch
in das Gebiet der Theoretischen Informatik eingeordnet werden. Sie
richtet sich insbesondere an Studierende der Mathematik mit
Schwerpunkt oder Nebenfach Informatik.
Das Hauptanliegen der Vorlesung ist, den Studierenden einen Vorrat
grundlegender Datenstrukturen und effizienter Algorithmen zu
vermitteln und sie mit Analysetechniken vertraut zu machen
(Korrektheitsbeweis und Laufzeitanalyse). Die Vorlesung über
Effiziente Algorithmen vertieft die Kenntnisse, die in der Vorlesung
über Datenstrukturn erworben wurden. Die zentralen Themen sind
die folgenden:
- Berechnung kürzester Pfade in einem Graphen bei ganzzahligen
Kantenkosten
- Berechnung eines maximalen Flusses in einem Transportnetzwerk
- Berechnung einer optimalen Lösung bei einem Zuordnungsproblem
(auch Matching-Problem genannt)
Darüberhinaus beschäftigen wir uns mit Anwendungen dieser
grundlegenden Probleme.
Literatur:
Die Vorlesung orientiert sich in weiten Teilen an dem Buch über
Network Flows (Theory, Algorithms, and Applications) von
K. Ahuja Ravindra, Thomas L. Magnanti und James B. Orlin ,
das 1993 im Verlag Prentice Hall erschienen ist
(ISBN 0-13-617549-X) . Des weiteren wird das Buch Algorithmen-Eine Einführung von
Thomas H. Cormen, Charles E. Leiserson, Ronald Rivest und Clifford Stein
empfohlen. Materialien:
Hier stehen die jeweiligen Auszüge aus der Vorlesung zum Downloaden bereit.Das Skript ist nun ab dem Beweis von Satz 3.6.13 (d.h. ab Seite 77 inklusive) aktualisiert bzw. erweitert worden.Des weiteren steht nun das letzte Kapitel über Paarzuordnungsprobleme zum Downloaden bereit.
Kapitel 1, 2, 3
Paarzuordnungsprobleme
Das aktuelle Übungsblatt steht hier jeweils ab Mittwoch zum Downloaden bereit.
Blatt 1
Blatt 2
Blatt 3
Blatt 4
Blatt 5
Blatt 6
Blatt 7
Blatt 8
Blatt 9
Blatt 10
Blatt 11
Blatt 12
Blatt 13
Abgabe der Lösungen: Darauffolgender Dienstag, 11.00 Uhr, Kasten No.10/NA 02/Eingang Rechenzentrum
Übung:
Mi, 10.00-11.30, NA 1/64, Christian Brandl
|
