Forschungsinstitut für Diskrete Mathematik

Vorlesung "Algorithmische Mathematik I"

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

Skript zur Vorlesung

Die Algorithmische Mathematik I benötigt als Erstsemestervorlesung keine Vorkenntnisse.

Klausurtermine: 19.2.2009, 9 Uhr, und 31.3.2009, 9 Uhr.

Termin zur Klausureinsicht der Nachklausur: Freitag, 24.4. von 13:00-15:00 Uhr im Konferenzraum, Forschungsinstitut für Diskrete Mathematik, Lennéstr. 2, 53113 Bonn.

Zeit: Montags und mittwochs 10-12 Uhr (c.t.)
Ort: Großer Hörsaal der Mathematik, Wegelerstr. 10
Übungen: 4st, nach Vereinbarung. Die Übungen beginnen am 15.10.2008. Nähere Informationen zu den Übungen finden sich hier.
Neben theoretischen Übungsaufgaben sind auch Programmieraufgaben zu bearbeiten. Diese müssen in der Programmiersprache C++ abgegeben werden. Grundlegendes Wissen der Programmiersprache C++ muss eigenständig erlernt werden. Dieses wird z.B im Programmierkurs der Fachschaft Mathematik (http://www.fsmath.uni-bonn.de/index.php?q=node/51) oder durch eines der vielen Online-C++-Tutorials (z.B. http://www.c-plusplus.de ) vermittelt.

Prof. Dr. S. Hougardy

Zeit:	Montags und mittwochs 10-12 Uhr (c.t.)
Ort:	Großer Hörsaal der Mathematik, Wegelerstr. 10
Übungen:	4st, nach Vereinbarung. Die Übungen beginnen am 15.10.2008. Nähere Informationen zu den Übungen finden sich hier. Neben theoretischen Übungsaufgaben sind auch Programmieraufgaben zu bearbeiten. Diese müssen in der Programmiersprache C++ abgegeben werden. Grundlegendes Wissen der Programmiersprache C++ muss eigenständig erlernt werden. Dieses wird z.B im Programmierkurs der Fachschaft Mathematik (http://www.fsmath.uni-bonn.de/index.php?q=node/51) oder durch eines der vielen Online-C++-Tutorials (z.B. http://www.c-plusplus.de ) vermittelt.