Modul Theorie effizienter Algorithmen, Informatik (Master) (SPO 7)

Ziel der Lehrveranstaltung ist die Vermittlung einiger grundlegender Algorithmen auf Graphen. Die Vorlesung soll Teilnehmer dazu befähigen, auch weiterführende Algorithmen zu erarbeiten, sicher anzuwenden sowie deren Korrektheit und Komplexität zu verstehen.

Nach einer kurzen theoretischen Einführung in die Graphentheorie werden zunächst Durchmusterungsmethoden wie die Breiten- und Tiefensuche vorgestellt. Weitere Algorithmen befassen sich mit der Erkennung von starken Zusammenhangskomponenten, topologischen Sortierungen sowie der Berechnung von kürzesten Wegen. Effiziente Tests auf die Kreisfreiheit von Graphen werden ebenfalls besprochen.

Für diese Lehrveranstaltung sind grundlegende Kenntnisse einer Programmiersprache sowie der sichere Umgang mit dem O-Kalkül notwendig. Die Kenntnis von Induktionsbeweisen ist von Vorteil. (Beide Themengebiete werden zum Selbststudium im Anhang des Skriptes angeboten.)

Der Stoff der Vorlesung wird an der Tafel besprochen und ist zusätzlich in einem vorab erhältlichen Skript verfügbar. Skript, Übungsaufgaben und Musterlösungen werden auch online angeboten.

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein: Introduction to Algorithms. MIT Press, 2001, ISBN 0-262-03293-7.

Die Lehrveranstaltung findet als Vorlesung statt. Begleitende Übungen vertiefen die vermittelten Gebiete. Musterlösungen werden zur Verfügung gestellt und bei Bedarf auch im Unterricht diskutiert.

Die Vorlesung gibt eine Einführung in Modellierungs- und Simulationsmethoden. Themen der Vorlesung und Übungen sind:

• Numerische Lösung von Nullstellenproblemen
• Numerische Lösung linearer / nichtlinearer Gleichungssysteme
• Approximationsverfahren: Taylorentwicklung, Polynominterpolation, Splines
• Ausgleichsrechnung
• Numerische Integration und Differentiation, Diskretisierungsverfahren, finite Differenzen
• Anfangswertprobleme, dynamische Systeme, numerische Lösung gewöhnlicher Differenzialgleichungen
• Raum-Zeit-Probleme, Numerische Verfahren zur Lösung partieller Differentialgleichungen; Anwendung: Stoff- und Wärmetransport
• Parallele Algorithmen und Standards zum verteilten Rechnen auf Hochleistungsrechnern

Die Inhalte der Vorlesung werden über Latex-Folien vermittelt. Die Folien werden den Studierenden vorlesungsbegleitend als PDF ins ILIAS hochgeladen. Ergänzend werden regelmäßig Beispiele und Anwendungen in vorlesungsintegrierten Rechenübungen besprochen. Die Aufgaben und Lösungen werden ebenfalls elektronisch bereitgestellt. Während der Veranstaltung werden ca. 6 Übungsblätter ausgeteilt, deren Lösung in darauffolgenden Terminen ausführlich vorgestellt wird. Zu der Veranstaltung gehört ein begleitendes Computerpraktikum, in dem numerische Algorithmen zu Interpolations- und Approximationsverfahren in kleinen Beispielprogrammen umgesetzt und am Rechner auf konkrete Probleme angewendet wird. Zum weiteren Selbststudium werden folgende Lehrbücher empfohlen:

• Scientific Computing, G. H. Golub and J.M. Ortega, B.G.Teubner Stuttgart 1996, ISBN 0-12-289255-0.
• Numerische Mathematik, M. Knorrenschild, Fachbuchverlag Leipzig, Carl Hanser Verlag, ISBN 978-3-446-42228-5.

Seminaristischer Unterricht und Übungen

In dem begleitenden Rechnerpraktikum werden die Inhalte der Vorlesung "Modellierung und Simulation" vertieft, indem numerische Algorithmen zur Interpolation diskreter Datenmengen und zur Approximation von Lösungen für kontinuierliche Probleme in der Programmiersprache C/C++ implementiert werden. Zunächst werden die Iterationsverfahren in kleinen Beispielprogrammen umgesetzt. Diese werden auf konkrete Fragestellungen angewendet und die Lösungen diskutiert bzw. graphisch dargestellt. Im Anschluss werden ausgewählte numerische Methoden hinsichtlich Laufzeit analysiert und Konzepte der Parallelisierung eingesetzt, um die Iterationen parallel auszuführen oder durch Gebietszerlegung auf mehrere Prozessoren zu verteilen. 

Themen der Rechnerübung zur Vorlesung "Modellierung und Simulation" sind:

• Umsetzung der numerischen Algorithmen zur Lösung von Nullstellenproblemen, linearen / nichtlinearen Gleichungssystemen, Interpolationsverfahren (Polynominterpolation, Splines, Taylorreihen), Ausgleichsrechnung, Numerische Integration und Differentiation, dynamische Systeme, partielle Differentialgleichungen
• Anwenden auf konkrete Fragestellungen
• Rechenzeit- bzw. Speicheroptimierung der implementierten Programme durch Konzepte der Parallelisierung und des verteilten Rechnens auf Hochleistungsclustern 

Für die praktischen Übungen am Rechner werden Aufgabenblätter erstellt und als PDF im ILIAS System bereitgestellt. Die Aufgaben werden zu Beginn der Veranstaltung besprochen, die Ziele erklärt und Lösungswege skizziert. Als Unterstützung werden den Studierenden Programmrümpfe zur Verfügung gestellt, in die die jeweiligen Algorithmen in C/C++ umgesetzt werden sollten. Nach Fertigstellung und Anwenden der Programme erfolgt eine Abnahme und eine ausführliche Besprechung der implementierten Lösung. Zum Vertiefen der in der Vorlesung erarbeiteten numerischen Verfahren wird auf das Lehrbuch:

• Numerische Mathematik, M. Knorrenschild, Fachbuchverlag Leipzig, Carl Hanser Verlag, ISBN 978-3-446-42228-5.

verwiesen. Als Unterstützung bei der Implementierung der Verfahren in C/C++ wird der Klassiker für Beispielprogramme in C empfohlen:

• Numerical Recipes in C book set: Numerical recipes . The art of scientific computing. Cambridge University Press; ISBN-10: 0521431085, ISSN-13: 978-0521431088

Praktische Übungen am Rechner