Algorithmen des Wissenschaftlichen Rechnens - SS 2004

Material zu Vorlesungen und Übungen

Vorlesungsfolien:

Fouriertransformation:

• Diskrete Fouriertransformation
• Schnelle Fouriertransformation/FFT
• (Schnelle) Fouriertransformation reeller Daten (begleitend zu den Übungen)
• (Schnelle) Cosinustransformation (inkl. Quarter-Wave-DFT)
• (Schnelle) Sinustransformation

Raumfüllende Kurven:

• Einführung (Raumfüllende Kurven, Hilbert-Kurve, Darstellung durch Grammatiken)
• Arithmetisierung der Hilbertkurve (Berechnung der Hilbert-Abbildung und deren Umkehrung)
• Aproximierende Polygone, Peanokurve, korrigierte Fassung vom 14.7.2004!
• 3D-Kurven, Parallelisierung
• Maple-Worksheets:
  • Arithmetisierung der Hilbertkurve: hilbert.mws (auch als Webseite und PDF)
  • Arithmetisierung der Peanokurve: peano.mws (auch als Webseite und PDF)
  • Parallelisierung und Partitionierung: hilbert_part.mws (auch als Webseite und PDF)
  • 3-dimensionale Hilbertkurve: hilbert_3D.mws (auch als Webseite und PDF)

Adaptive Integration nach Archimedes:

• Maple-Worksheets:
  • eindimensionale Integration nach Archimedes:
    arch1D.mws (auch als Webseite und PDF)
  • eindimensionale Integration nach Archimedes (Version 2):
    arch1D_vers2.mws (auch als Webseite und PDF)
  • Quadratur nach Archimedes - d-dimensionaler Fall:
    arch_dDim.mws (auch als Webseite und PDF)
  • Quadratur nach Kombinationstechnik:
    kombi.mws (auch als Webseite und PDF)
  • Hierarchisierung und Dehierarchisierung:
    dehierarch.mws (auch als Webseite und PDF)
  • Poisson-Gleichung und Hierarchisierung:
    hierbas1d.mws (auch als Webseite und PDF)
  • Poisson-Gleichung und Hierarchisierung (2D):
    hierbas2d.mws (auch als Webseite und PDF)
  • Mehrgittermethode mit hierarchischen Basen:
    mg1dhierbas.mws (auch als Webseite und PDF)
  • Mehrgittermethode mit hierarchischen Basen (2D):
    mg2dhierbas.mws (auch als Webseite und PDF)

  Bei der HTML-Darstellung muss bei den neueren Worksheets der verwendete Browser evtl. manuell auf UTF-8-Codierung umgeschaltet werden, damit die Umlaute korrekt dargestellt werden. Maple 9 erzeugt hier leider unzureichenden HTML-Code.

• Overhead-Folien:
  • Foliensatz 1 (PDF)

Übungsblätter:

• Blatt 1: Eigenschaften der DFT (Fr, 23.04.2004)
• Angabe (korrigiert!)
• Lösungsvorschlag
• Blatt 2: Projekt "Interpolation der Bahn des Asteroiden Pallas"
  • Angabe
  • Lösungsvorschlag
  • Maple-Worksheet (auch als Webseite und PDF)
• Blatt 3: Schnelle reelle Fouriertransformation (Fr, 03.05.2004)
• Angabe (neue Aufgabenstellung!)
• Lösungsvorschlag
• Blatt 4: Schnelle Poisson-Löser
  • Angabe
  • Lösungsvorschlag
  • Maple-Worksheets:
    1D-Poisson-Löser (auch als Webseite und PDF),
    2D-Poisson-Löser (auch als Webseite und PDF)
• Blatt 5: Grammatiken für Raumfüllende Kurven
  • Angabe
  • Lösungsvorschlag (Korrigierte Fassung!)
  • Maple-Worksheet: turtle.mws (auch als Webseite und PDF)
• Blatt 6: Arithmetisierung raumfüllender Kurven
  • Angabe
  • Lösungsvorschlag
  • Maple-Worksheets:
    hilbert.mws (auch als Webseite und PDF),
    peano.mws (auch als Webseite und PDF),
    
• Blatt 7: Adaptive Integration mit Parabelbögen
  • Angabe
  • Lösungsvorschlag (korrigiert!)
  • Maple-Worksheets:
    archipar.mws (auch als Webseite und PDF)

Sonstiges/Links:

• zur Schnellen Fouriertransformation:
  • Paul N. Swarztrauber: Symmetric FFTs, Math. Comp. 47 (1986), pp. 323-346
  • JPEG-Tutorial (by Ray Wolfgang, Purdue University)
  • Photo Database (University of Cambridge, enthält eine Sammlung von Bildern, die im Image Processing gerne verwendet werden)
  • Quellcode des Java-Programms aus der Vorlesung:
    BildFrame.java, BildApplet.java, FctDialog.java, Fourier.java, GraustufenBild.java, KompGrauBild.java, Complex.java
    Wer Verbesserungen und/oder Erweiterung des Codes vornehmen will, ist dazu herzlich eingeladen. Ich würde mich freuen, eine Kopie des modifizierten Codes zu erhalten (und zu veröffentlichen).
• zu raumfüllenden Kurven:
  • Skriptum zur Vorlesung (PDF-Dokument)
  • Maple-Worksheet zur Hilbert-Kurve nach Moore:
    Implementierung in Maple (auch als Webseite und als PDF)
  • Greg Breinholt and Christoph Schierz: Algorithm 781: generating Hilbert's space-filling curve by recursion ,
    ACM Transactions on Mathematical Software (TOMS), Volume 24 , Issue 2 (June 1998)
  • Maple-Worksheet zum Algorithm 781:
    Implementierung in Maple (auch als Webseite)
• zu hierarchischen Basen:
  • Skript zur Vorlesung "Rekursive Verfahren und hierarchische Datenstrukturen in der numerischen Analysis" des WS 1999/2000, (Autor: H.-J. Bungartz, als gezipte PostScript-Datei), insbes. Kapitel 2 und 3