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, Donnerstag, 23.7., 13:15 im HS2
- Die Wiederholungsprüfung ist eine mündliche Prüfung am Donnerstag, den 15.10.
- 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)
Hierarchische Verfahren
- 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 exakten 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 (Update 25.8.: Folie 3 (PDF-Numerierung), oberste Formel: 2^{-\underline{l}} statt 2^{\underline{l}})
- Einschub: Finite Elemente - eine Einführung in die gängigsten Vorurteile
- Algorithmen und Datenstrukturen für dünne Gitter
- Mehrgitterverfahren
- Hierarchische Teilraumzerlegung und Wavelets (Update 18.6.: Absatz "Achtung..." auf Folie 8 entfernt, weil durch neue Numerierung kein Anlass mehr besteht :-)
- Gesammelte Werke: Alle hierarchischen Folien (8 pro Seite)
Schnelle Fouriertransformation
- Diskrete Fouriertransformation - 03.6.09
- Schnelle Fouriertransformation - 03.6.09 & 04.6.09
- Schnelle Fouriertransformation für reelle Daten - 11.06.09
- zur Info: Paul N. Swarztrauber - Symmetric FFTs (ggf. Zugriff über LRZ-Proxy nötig)
- Quarter-Wave-Fouriertransformation und Diskrete Cosinus-Transformation - 17.06.09
- Diskrete Sinus-Transformation - 24.06.09
Raumfüllende Kurven
- Oktalbäume - 01.07.09
- Hilbertkurve - 02.07.09
- Hilberttraversierung und Hilbertabbildung - 08.07. & 09.07.09
- Maple-Worksheets: turtle.mws (Turtle-Grafik) und hilbert_adap.mws (Hilberttraversierung auf Quadtrees)
- Maple-Worksheets: hilbert.mws (Hilbert-Arithmetisierung) und hilbert_part.mws (Umkehrung der Hilbertkurve, Partitionierung)
- Approximierende Polygone, Raumfüllende Kurven & Fraktale - 15.07.09
- Maple-Worksheets: hilbert.mws (Hilbert-Arithmetisierung) und peano.mws (Peano-Arithmetisierung)
- Raumfüllende Kurven in 3D - 16.07.09
- Maple-Worksheets: hilbert_3D_a.mws, hilbert_3D_b.mws, hilbert_3D_c.mws, hilbert_3D_d.mws (Hilbert-Arithmetisierung in 3D, 4 Varianten)
Lehrstuhlausflug
- Am Donnerstag, 16.7., näheres hier.
Ü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
- Die ausgefüllte OpenOffice-Tabelle, auch als pdf
- Blatt 4 (Kombinationstechnik, 28.5.09)
- Ein Lösungsvorschlag
- Das Maple-Worksheet (auch in HTML)
- Blatt 5 (Erzeugendensysteme, 4.6.09)
- Ein Lösungsvorschlag
- Blatt 6 (Trigonometrische Interpolation und DFT, 4.+11.6.09 in der Vorlesung)
- Lösungsvorschlag
- zugehörige Maple-Worksheets: pallas1.mws (auch als PDF) und pallas2.mws (auch als PDF)
- Blatt 7 (Gedanken zum Thema "senkrecht", 18.6.09)
- Ein Lösungsvorschlag
- Blatt 8 (Cosinustransformation, 25.6.09)
- Ein Lösungsvorschlag
- Blatt 8a (Schneller Poisson-Löser, 25.6.09 in der Vorlesung)
- Ein Lösungsvorschlag
- Blatt 9 (Raumfüllende Probleme, 2.7.09)
- da man bei diesem Blatt nur probieren, aber nichts falsch machen kann, gibt es keinen Lösungsvorschlag
- Blatt 10 (Grammatiken für raumfüllende Kurven, 9.7.09)
- Ein Lösungsvorschlag
- Maple-Worksheets: realturtle_hilbert.mw, realturtle_hilbert1.mw, realturtle_hilbert2.mw
- Blatt 11 (Arithmetisierung raumfüllender Kurven, 16.7.09)
- Ein Lösungsvorschlag
- Maple-Worksheets zu Aufg. 2: peano_switch.mws, meander2.mws
- Maple-Worksheets zu Aufg. 3: kochturtle.mw
Klausur
- Donnerstag, 23.7., 13:15 im HS 2
- Anmeldeverfahren: über TUMonline
- erlaubte Hilfsmittel: ein beidseitig beschriebenes DinA4-Blatt mit handschriftlichen(!) Notizen
- Die Klausur ist korrigiert, Noten sind im TUMonline eingetragen. Informatiker, die noch nicht im TUMonline angemeldet waren, bitte schnellstmöglich nachholen und uns Bescheid sagen, damit wir die Note nachtragen können.
- Klausureinsicht: nach Vereinbarung (Mail an zimmer@in.tum.de)
- Die Wiederholungsprüfung ist eine mündliche Prüfung am Donnerstag, den 15.10.
Alte Klausuren zum Üben:
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)