Bereich:
4+2 SWS Vorlesung im
Bereich Informatik III (Theoretische Informatik)
Vertiefende Vorlesung
im Gebiet Algorithmen
Zeit und Ort:
Mittwoch, 14:15-15:45, Hörsaal MI HS 3
Freitag, 12:00-13:30, Hörsaal MI HS 2
Übung:
2 SWS Übung zur Vorlesung
Übungsleitung: N.N.
Schein:
Einen Schein erhält, wer
mindestens 40% der Punkte zu den Hausaufgaben erreicht und
erfolgreich an der mündlichen Prüfung teilnimmt.
Hörerkreis:
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
Voraussetzungen:
Stoff des Informatik Grundstudiums
Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.
Empfehlenswert für:
Erweiterte Kenntnisse im Bereich Algorithmen
Inhalt:
Algorithmen für Flüsse und Matchings
Flüsse und Schnitte
Maximaler Fluss
Max-Flow Min-Cut Theorem
Algorithmus von Ford und Fulkerson
Algorithmus von Edmonds und Karp
Algorithmus von Goldberg
Maximale Matchings
Flüsse mit minimalen Kosten
String und Pattern Matching
Naives Matching
Matching von Worten
Matching regulärer Ausdrücke
Textkompression
Shannon-Fano Codes
Huffman Codes
Arithmetische Codes
Lempel-Ziv Codes
Lineare Optimierung
Standardformulierungen
Dualitätssatz der linearen Programmierung
Simplex-Algorithmus
Polynomialzeit-Algorithmen
Approximationsalgorithmen
Randomisierte Approximationsalgorithmen
Lineare Optimierung und Approximationsalgorithmen
Weiterführende bzw. verwandte Vorlesungen:
Internet-Algorithmik
Skript:
Algorithmen für maximale Flüsse (in Postscript und pdf)
(aus dem Skript "Algorithms" von Sariel Har-Peled)
Sting- und Pattern-Matching (in Postscript und pdf)
(basierend auf dem Buch "Algorithms on Strings, Trees, and Sequences"
von Dan
Gusfield und dem Skript "Information Retrieval" von Peter Becker)
Datenkomprimierung (in Postscript und
pdf)
(teilweise basierend auf dem Skript "Data Compression" von Peter Bro Miltersen)
Lineare Optimierung (in Postscript und
pdf)
(basierend auf dem Skript "Optimierung und OR" von Michael Jünger)
Techniken für randomisierte Approximationsalgorithmen (in Postscript und pdf)
(aus dem Skript "Approximationsalgorithmen" von Rolf Wanka)
Lineare Optimierung und Approximationsalgorithmen (in Postscript und pdf)
(aus dem Skript "Approximationsalgorithmen" von Rolf Wanka)
Online Algorithmen (in pdf)
(aus dem Skript "Online Algorithmen" von Susanne Albers)
Literatur:
Die Inhalte der Vorlesung werden in wesentlichen Teilen durch folgende Bücher und Artikel abgedeckt:
Thomas H. Cormen, Charles E. Leiserson, Ron L. Rivest, Clifford Stein. Introduction to Algorithms.
2. Auflage, The MIT Press, Cambridge, MA, 2001.
Michael T. Goodrich, Roberto Tamassia. Algorithm Design: Foundations, Analysis, and Internet Examples.
John Wiley & Sons, Inc., 2002.
Christos H. Papadimitriou, Kenneth Steiglitz. Combinatorial optimization: Algorithms and complexity.
Prentice-Hall, Englewood Cliffs, NJ, 1982.