|
Dozent:
Prof. Dr. Angelika Steger
|
|
|
Bereich:
3 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
Vertiefungsvorlesung im Gebiet Algorithmen
|
|
|
Zeit und Ort:
Mi 08:30 - 10:00, Hörsaal 65/Luisenstr.
Do 08:30 - 09:00, Hörsaal S1128
Beginn: 2. Mai
|
|
|
Übung:
1 SWS Übung zur Vorlesung
Mi 13:00 - 13:45, Raum S2229
Übungsleitung:
Volker Heun
Übungsschein: Klausur
|
|
|
Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
|
|
|
Voraussetzungen:
Stoff des Informatik-Grundstudiums,
Kenntnisse der Veranstaltungen Algorithmen und Datenstrukturen
I/II sind vorteilhaft, werden aber nicht vorausgesetzt.
|
|
|
Empfehlenswert für:
Vertiefung im Bereich Algorithmen
|
|
|
Inhalt:
In dieser Vorlesung werden Optimierungsprobleme über endlichen
diskreten Strukturen betrachtet.
Ziel der Vorlesung ist es insbesondere verschiedene grundlegende
kombinatorische Ansätze und Methoden wie
Greedy-Verfahren,
Enumerations- und Branch & Bound-Verfahren,
Dynamische Programmierung, Scaling-Methoden,
Divide and Conquer Verfahren
vorzustellen und sie an konkreten Problemen zu illustrieren.
Einen "roten Faden" der Vorlesung werden
Färbungsproblem in Graphen bilden:
- Färbungsprobleme in Graphen
u.a Greedy-Algorithmus, exponentielle Algorithmen,
Kantenfärbungen
- Polynomielle Algorithmen für spezielle Graphenklassen
u.a. planare Graphen, perfekte Graphen
- Approximationsalgorithmen
u.a. Knapsack, Setcover, chromatische Zahl
|
|
|
Skript:
Kein Skript
|
|
|
Literatur:
-
M. Aigner:
-
Graphentheorie. Eine Entwicklung aus dem 4-Farben-Problem
-
R. Motwani:
-
Lecture Notes on Approximation Algorithms
Technical Report No. STAN-CS-92-1435,
Department of Computer Science, Stanford University
(elektronisch erhältlich,
hier liegt eine
lokale Kopie als gzipped PS-File (213kB))
-
Ch. Papadimitriou, K. Steiglitz:
-
Combinatorial Optimization: Algorithms and Complexity
|
|
|
Sprechstunde:
siehe hier
|
