Vorlesung "Algorithmische Mathematik I"

← Semesterübersicht

Wintersemester 2008/09

Diese Vorlesung vermittelt grundlegende mathematische Fähigkeiten zu Entwurf und Analyse von Algorithmen. Neben elementaren algorithmischen Konzepten werden Fragen zur numerischen Stabilität und Effizienz von Algorithmen behandelt.

Themen:

• Elementare Algorithmen: Was sind Algorithmen? Berechenbarkeit, Umsetzung von Algorithmen; elementare Programmierkonzepte; Einführung in Programmierung; Zahlendarstellungen auf dem Rechner: Integer, Gleitkommazahlen; Auslöschung, Rundungsfehler; Rekursive Algorithmen am Beispiel der Dreitermrekursion: elementare Betrachtungen zur Stabilität; Komplexität beispielorientiert: Sortieralgorithmen
• Diskrete Algorithmen: Graphen, Bäume, Arboreszenzen, Zusammenhang, BFS und DFS, bipartite, azyklische, stark zusammenhängende Graphen; verkettete Listen, Baumdatenstrukturen, Heaps; Finden kürzester Wege; Flüsse in Netzwerken, Max-Flow-Min-Cut-Theorem, Algorithmen von Ford-Fulkerson und Edmonds-Karp; bipartites Matching; Turing-Maschinen, NP-vollständigkeit
• Stabilität, Kondition und numerische lineare Algebra: absolute und relative Kondition; Stabilität, Stabilitätsindikator; Einführung in die linearisierte Fehlertheorie, Vorwärts- und Rückwärtsanalyse, Design von numerischen Methoden; Direkte Verfahren: Gaußelimination, Cholesky-Zerlegung

Literatur:

• P. Deuflhard, A. Hohmann: Numerische Mathematik. De Gruyter, 2002
• T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein: Introduction to Algorithms, MIT Press, 2. Auflage, 2001
• B. Korte, J. Vygen: Combinatorial Optimization: Theory and Algorithms. Springer, 2008 (Abschnitte 1.1-1.4, 2.1-2.4, 4.1-4.3, 6.1, 7.1, 8.1-8.3 und 15.1-15.4)
• J. Kleinberg, E. Tardos: Algorithm Design. Pearson, 2006 (Kapitel 2, 3, 4, 7)
• J. Stoer: Einführung in die Numerische Mathematik 1, Springer