Algorithmen des Wissenschaftlichen Rechnens - Summer 09

Term

Summer 09

Lecturer

Michael Bader, Stefan Zimmer

Time and Place

Mittwochs 12:15-13:45, und Donnerstags, 13:15-14:45, Raum MI HS2, Beginn: 22.04.2009

Übung: Donnerstags, 8:30-10:00, Raum MI 02.07.023, Beginn: 30.04.2009

Audience

Modul IN2001

Informatik Diplom: Wahlpflichtfach im Bereich theoretische Informatik

Informatik Master: Wahlfach im Fachgebiet "Algorithmen und Wissenschaftliches Rechnen"

Informatik/Wirtschaftsinformatik Bachelor: Wahlfach

Studierende der Mathematik/Technomathematik, Natur- und Ingenieurwissenschaften

Tutorials

Michael Bader, Stefan Zimmer

Exam

Schriftliche Prüfung am Semesterende, voraussichtlich Donnerstag, 23.7. , 13:15 im HS2

Semesterwochenstunden / ECTS Credits

6 SWS (4V + 2Ü) / 8 Credits

TUMonline

{{{tumonline}}}

---

Worum geht's in AWR?

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:

• Varianten der schnellen Fouriertranformation (FFT):
  FCT (Fast Cosine Transform), reelle FFT, Einsatz zur Kompression von Video- und Audiodaten
• Raumfüllende Kurven:
  Konstruktion und Eigenschaften raumfüllender Kurven, Einsatz in der Parallelisierung und zur Linearisierung mehrdimensionaler Datenräume in Datenbanken
• Hierarchische und rekursive Verfahren im Wissenschaftlichen Rechnen:
  von der Archimedes-Quadratur zur hierarchischen Basis, Aufwand vs. Genauigkeit - Dünne Gitter, Wavelets, Mehrgitterverfahren

Materialien zur Vorlesung

Vortragsfolien etc. werden hier bereit gestellt; um einen Eindruck vom weiteren Ablauf der Veranstaltung zu bekommen, kann man vorerst einfach mal auf der Seite vom Vorjahr vorbeischauen.

Einführung

(Vorlesung am 22.4.09)

• Merkblatt zur Vorlesung

Hierarchische Verfahren

Stand der Vorlesung: am 7.5. sind wir in "Hierarchische Zerlegung, mehrdimensional" bis zu Folie 6 (PDF-Numerierung, Seitenzahl 4) gekommen

• Quadratur nach Archimedes (eindimensional) - 23.4.09
  • Das Maple-Worksheet dazu (auch in HTML)
• Exkurs über Aufwand und Genauigkeit
• Hierarchische Zerlegung, eindimensional
• Quadratur nach Archimedes (mehrdimensional)
  • Das Maple-Worksheet dazu (auch in HTML)
  • "Archimedes in Python" arch.py: für alle, die die d-dimensionale Quadratur auch mal in Aktion sehen wollen; die Implementierung hält sich eng an die Folien, nur die Reihenfolge, in der die x_i behandelt werden, ist umgekehrt (im Programm war es einfacher, in der ersten Komponente zu hierarchisieren, auf der Folie beginnen wir mit x_2). Aufgerufen wird das mit F(f, eps, a, b):
    • f ist der Integrand (als Parameter bekommt er einen Vektor mit den Koordinaten der Auswertestelle)
    • eps das Abbruchkriterium (dessen Behandlung ist noch nicht ganz korrekt, da müsste man noch mal drüber nachdenken)
    • a ist ein Vektor mit den Koordinaten der "linken unteren" Ecke des Integrationsgebietes, b die der diagonal gegenüberliegende Ecke
    • test(eps, a, b) verwendet für f unser Standard-Testbeispiel [4*x_1*(1-x_1)]* [4*x_2*(1-x_2)]*...* [4*x_d*(1-x_d)] und berechnet außer der Approximation auch den exaten Integralwert
    • test_ed(eps, d) setzt a auf den Nullpunkt, b auf den Mittelpunkt des d-dimensionalen Einheitswürfels und druckt den Quadraturfehler aus.
    • Das Programm arch_dict.py berechnet genau dasselbe, aber die Funktionen T und D speichern nun die einmal berechneten Werte, das ist im Höherdimensionalen, wo 3^d ziemlich groß ist, schneller.
    • Das ist mein erstes Python-Programm und vermutlich habe ich einiges unsachgemäß aufgeschrieben, Verbesserungsvorschläge sind willkommen!
  • Der Aufrufbaum als Mindmap für Freemind und der HTML-Export
• Hierarchische Zerlegung, mehrdimensional
• Einschub: Finite Elemente - eine Einführung in die gängigsten Vorurteile
• Algorithmen und Datenstrukturen für dünne Gitter

Übungsblätter und Lösungen

• Blatt 1 (Hierarchischer Überschuss, 30.4.09)
  • Das Maple-Worksheet (auch in HTML)
  • Die Berechnung mittels der Intregralformel
• Blatt 2 (Normen von Funktionen, 7.5.09)
  • Ein Lösungsvorschlag
  • Das Maple-Worksheet (auch in HTML)
• Blatt 3 (Mehrdimensionale Quadratur, 14.5.09)
  • Eine OpenOffice-Tabelle als Vorlage
• Blatt 4 (Kombinationstechnik, 28.5.09)

Klausur

• Voraussichtlich am Donnerstag, 23.7., 13:15 im HS 2
• Anmeldeverfahren: wird noch bekannt gegeben.

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, hängt hauptsächlich vom persönlichen Geschmack ab, daher erfolgt hier keine spezielle Empfehlung.

Raumfüllende Kurven:

• Skriptum zur Vorlesung
• Hans Sagan, Space-Filling Curves, Springer-Verlag, 1994

Hierarchische Verfahren

• Skript zur Vorlesung "Rekursive Verfahren und hierarchische Datenstrukturen in der numerischen Analysis" des WS 1999/2000, (Autor: H.-J. Bungartz, gezipte PostScript-Datei)