Algorithmen des Wissenschaftlichen Rechnens - SS 2003

Dozenten:

• Prof. Dr. Chr. Zenger
• Dr. M. Bader

Hörerkreis + Einordnung:

• Studierende der Informatik (Hauptstudium, Wahlpflichtfach im Bereich theoretische Informatik)
• Studierende der Mathematik/Technomathematik, Natur- und Ingenieurwissenschaften

Semestralklausur:

Klausurtermin ist Donnerstag, 10. Juli 2003, 12-14 Uhr, MI HS 3, also in der letzten Vorlesung.

Klausurergebnisse:

Die endgültigen Ergebnisse der Klausur hängen ab sofort im Schaukasten des Lehrstuhl Zenger aus (neben dem Eingang zum Bauteil MI 02.05). Gelegenheit zur Klausureinsicht besteht nach Absprache bis zum 31.10.2003 (bitte Termin vereinbaren mit Michael Bader).

Scheine können direkt im Büro von Michael Bader abgeholt werden - kurze Terminabsprache wird empfohlen, es sind Ferien! Die Notenmeldungen für DHP-Physik gehen direkt an Herrn Dressler (Scheine werden dafür nicht ausgestellt).

Vorlesungs- und Übungstermine:

3 SWS Vorlesung plus 1 SWS Übung; Vorlesungsbeginn: 8. April 2003

• Vorlesung/Übung: Dienstags, 10-12 Uhr, MI 00.06.011 (HS 3)
• Vorlesung: Donnerstags, 12-14 Uhr, MI 00.06.011 (HS 3)

Voraussetzungen:

Vordiplom, Vorlesung "Konkrete Mathematik"

Inhaltsangabe:

Viele Anwendungen der Informatik erfordern Methoden aus der (vorwiegend numerischen) Mathematik - dies gilt natürlich vor allem für Anwendungen aus dem Bereich der Natur- und Ingenierwissenschaften, aber auch für überraschend viele Gebiete, die man als ureigenste Gebiete der Informatik ansehen würde:

Zum Beispiel sind die Fourier- und auch die Wavelet-Transformation in der Bildverarbeitung und -kompression unverzichtbare Werkzeuge. Raumfüllende Kurven - Ende des 19. Jahrhundert's als "topologische Monster" noch reine Gedankengebilde - haben wichtige Anwendungsfelder in der Parallelisierung und in der Implementierung von Datenbanken gefunden. Numerische Verfahren zur Minimierung und Nullstellensuche bilden die wesentliche Grundlage des maschinellen Lernens mittels Neuronaler Netze.

Die Vorlesung "Algorithmen des Wissenschaftlichen Rechnens" bietet eine allgemein verständliche, algorithmisch orientierte Einführung in die Grundlagen solcher mathematischer Verfahren. Themengebiete sind z.B.:

• Varianten der schnellen Fouriertranformation (FFT):
  FCT (Fast Cosine Transform), reelle FFT, Einsatz zur Kompression von Video- und Audiodaten
• Wavelets:
  Konstruktion von Wavelets, schnelle Algorithmen zur Wavelet-Transformation, Anwendung in der Bildverarbeitung und -kompression
• Raumfüllende Kurven:
  Konstruktion und Eigenschaften raumfüllender Kurven, Einsatz in der Parallelisierung und zur Linearisierung mehrdimensionaler Datenräume in Datenbanken
• Minimierung und Nullstellensuche im Mehrdimensionalen:
  Newton-Verfahren, Steepest Descent und Conjugate Gradient, das Problem lokaler und globaler Minima,
  Anwendungsbeispiel: Neuronale Netze,
  Exkurs: Nichtlinearität und Chaos - Fraktale Welten
• Iterative Verfahren zum Lösen von Gleichungssystemen:
  Gauss-Seidel- und Jacobi-Verfahren, Mehrgitter-Verfahren
• Hierarchische und Rekursive Verfahren im Wissenschaftlichen Rechnen:
  von der Archimedes-Quadratur zur hierarchischen Basis, Der Fluch der Dimension: Integration in hochdimensionalen Räumen (z.B. in der Finanzmathematik)

Literatur:

Schnelle Fouriertransformation:

Die Vorlesung orientiert sich an ausgewählten Kapiteln der beiden folgenden Bücher:

• W.L. Briggs, Van Emden Henson, The DFT - An Owner's Manual for the Discrete Fourier Transform, SIAM, 1995
• Charles van Loan, Computational Frameworks for the Fast Fourier Transform, SIAM, 1992

Darüber hinaus dürften im Fachbuchhandel ein stattliche Anzahl von weiteren Lehrbüchern zum Thema erhältlich sein. Welches davon zu empfehlen ist, dürfte hauptsächlich vom Geschmack des Einzelnen abhängen, daher erfolgt hier keine spezielle Empfehlung.

Raumfüllende Kurven:

• Hans Sagan, Space-Filling Curves, Springer-Verlag, 1994