Upload
others
View
1
Download
0
Embed Size (px)
Citation preview
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 1
Algorithmik IIIAlgorithmik III
Algorithmen und Datenstrukturen Algorithmen und Datenstrukturen für kontinuierliche Modellefür kontinuierliche Modelle
Ulrich Rüde
Lehrstuhl für Systemsimulation
Sommersemester 2007
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 2
Vorlesung Vorlesung 1a 1a
Vorbemerkungen, Organisatorisches, Vorbemerkungen, Organisatorisches, Ziele, Motivation, InhaltsübersichtZiele, Motivation, Inhaltsübersicht
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 3
Organisatorisches (1)Organisatorisches (1)Format der VorlesungFormat der Vorlesung
4 SWS Vorlesung 4 SWS Vorlesung
2 SWS Übungen: Programmier- und Übungsaufgaben sind 2 SWS Übungen: Programmier- und Übungsaufgaben sind entscheidend für den Studienerfolgentscheidend für den Studienerfolg
Theoretische HausaufgabenTheoretische Hausaufgaben
werden korrigiertwerden korrigiert
ProgrammieraufgabenProgrammieraufgaben
werden korrigiertwerden korrigiert
Kurzprüfungen (KP1, KP2, KP3, KP4) in den ÜbungenKurzprüfungen (KP1, KP2, KP3, KP4) in den Übungen
jeweils 5 Punktejeweils 5 Punkte
Klausur, 120 min, 120 Punkte, am 20.9. 2007Klausur, 120 min, 120 Punkte, am 20.9. 2007
wer die Klausur bestanden hat, kann die Punkte aus den KP zur wer die Klausur bestanden hat, kann die Punkte aus den KP zur Notenverbesserung anrechnenNotenverbesserung anrechnen
nur jeweils die erste KP zähltnur jeweils die erste KP zählt
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 4
Organisatorisches (2)Organisatorisches (2)
Das TeamUlrich Rüde
Christoph [email protected]
Harald Kö[email protected]
Markus Stü[email protected]
Frank [email protected]
Dominik Bratuschat
Dominik Haspel
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 5
Organisatorisches (3)Organisatorisches (3)
Vorlesung: Mi 12-14 Uhr, H8 Fr 12-14 Uhr, H8
Freitag, der 4.5.2006 : Tag der Informatik
alle Informatik-LV entfallen
Vorträge und Live-Demos ausgewählter Arbeiten
Übungen:Mo 8:00 - 12:00 (0.141), Mo 10:00 - 12:00 (KS I), Mo 12:00 - 14:00 (00.156), Mo 14:00 - 16:00 (0.141),
Di 14:00 - 16:00 (0.111), Mi 10:00 - 12:00 (0.111), Do 10:00 - 12:00 (KS I)
Anmeldung mit WAS – bis 20.4.2007 (23:59)Info auf der web-Seite: www10.informatik.uni-erlangen.de -> Lehre ->
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 6
Organisatorisches (4)Organisatorisches (4)
Übungen:
wöchentliche Aufgaben: Ausgabe am Donnerstag (nur im web)
Empfehlung: Bearbeitung im Team,
Abgabe schriftlicher Ausarbeitung 8 Tage später
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 7
Motivation (1)Motivation (1) Warum „kontinuierliche“ Datenstrukturen und Algorithmen?Warum „kontinuierliche“ Datenstrukturen und Algorithmen? Gegensatz von diskret/digital zu kontinuierlich/analogGegensatz von diskret/digital zu kontinuierlich/analog Bisher sind kontinuierliche Probleme im Grundstudium der Bisher sind kontinuierliche Probleme im Grundstudium der
Informatik (fast) nicht vorgekommenInformatik (fast) nicht vorgekommen Computer sind doch digital, nicht analogComputer sind doch digital, nicht analog Mit zunehmender Speicherkapazität und Mit zunehmender Speicherkapazität und
Verarbeitungsleistung werden (digitale) Computer Verarbeitungsleistung werden (digitale) Computer zunehmend eingesetzt um analoge Verarbeitung zu ersetzenzunehmend eingesetzt um analoge Verarbeitung zu ersetzen
„„Siegeszug der Digitaltechnik“: Verarbeitung kontinuierlicher Siegeszug der Digitaltechnik“: Verarbeitung kontinuierlicher DatenDaten
Verarbeitung kontinuierlicher (analoger) Daten wird Verarbeitung kontinuierlicher (analoger) Daten wird (eigentlich: ist schon) für die Informatik zunehmend wichtig(eigentlich: ist schon) für die Informatik zunehmend wichtig
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 8
Motivation (2)Motivation (2)
Beispiel-Anwendungen
Mustererkennung: Analyse von (eigentlich kontinuierlichen) Audio-, Bild- und Videodaten,
Graphische Datenverarbeitung: Synthese von (kontinuierlichen) Bild- (oder Video-) Daten
Simulation: Berechnung bzw. Approximation kontinuierlicher Prozesse der (physikalischen) Realität mit Digitalrechnern
Embedded Systems Analyse (kontinuierlicher) Sensorsignale Digitale Verarbeitung Generierung (kontinuierlicher) Stellgrößen für die Aktoren
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 9
Beispiel MustererkennungBeispiel Mustererkennung
Automatisches Tracking
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 10
Simulation und Experiment
Simulation and Experiment: Diplomarbeit N. Thürey
Zur Anzeige wird der QuickTimeª Dekompressor ãYUV420 codecÒ
bentigt.
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 11
Pulsating Blood Flow at Pulsating Blood Flow at AneurysmAneurysm
Data Set
Zur Anzeige wird der QuickTimeª Dekompressor ãYUV420 codecÒ
bentigt.
• Master ThesisJan Götz
In Zusammenarbeit mit Neuroradiologie (Prof. Dörfler)BildverarbeitungSimulationStrömungsmechanik
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 12
Beispiel ComputergraphikBeispiel Computergraphik
Photorealistische Darstellung
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 13
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 14
Simulation und VisualisierungSimulation und Visualisierung
Zur Anzeige wird der QuickTimeª Dekompressor ãÒ
bentigt.
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 15
Aktuelle und zukünftige ThemenAktuelle und zukünftige Themen für Forschung und Entwicklung (1) für Forschung und Entwicklung (1)
Digitale SignalverarbeitungDigitale Signalverarbeitung• Beginn mit Einführung der CD: Anfangs war es eine große Beginn mit Einführung der CD: Anfangs war es eine große
Herausforderung, genügend Speicherkapazität und Herausforderung, genügend Speicherkapazität und Verarbeitungsgeschwindigkeit für eine ansprechende Klangqualität bereit Verarbeitungsgeschwindigkeit für eine ansprechende Klangqualität bereit zu stellenzu stellen
• Audio-Kompressionsverfahren (MP3)Audio-Kompressionsverfahren (MP3)• Digitales Radio ?Digitales Radio ?• Digitale (netzgebundene) TelefonieDigitale (netzgebundene) Telefonie• Voice over IPVoice over IP• MobilfunkMobilfunk• Kompressionsverfahren für Bilddaten (jpeg, etc)Kompressionsverfahren für Bilddaten (jpeg, etc)• Digitales VideoDigitales Video• VideokompressionsverfahrenVideokompressionsverfahren• MultimediaMultimedia• Suchen und Vergleichen in Mediadaten Suchen und Vergleichen in Mediadaten
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 16
Aktuelle und zukünftige ThemenAktuelle und zukünftige Themen für Forschung und Entwicklung (2) für Forschung und Entwicklung (2)
• SimulationSimulation• Vorhersage und Optimierung Vorhersage und Optimierung
komplexer (physikalischer) Systeme komplexer (physikalischer) Systeme in Wissenschaft und Technikin Wissenschaft und Technik
• MustererkennungMustererkennung• Echtzeitanalyse von VideodatenEchtzeitanalyse von Videodaten• Medizinische Bildverarbeitung: Medizinische Bildverarbeitung:
Registrierung, ….Registrierung, ….• Embedded SystemsEmbedded Systems
• (optimale) Steuerung und Regelung (optimale) Steuerung und Regelung technischer Systeme in Realzeit technischer Systeme in Realzeit
• Computergraphik und Visualisierung Computergraphik und Visualisierung • Synthese photorealistischer Bilder und VideosSynthese photorealistischer Bilder und Videos• Visualisierung grosser Datensätze (aus Simulation oder Experiment)Visualisierung grosser Datensätze (aus Simulation oder Experiment)• Augmented Reality, z.B. in der MedizintechnikAugmented Reality, z.B. in der Medizintechnik
Diplomarbeit N. ThüreyDiplomarbeit N. Thürey
Zur Anzeige wird der QuickTimeª Dekompressor ãÒ
bentigt.
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 17
Aktueller StandAktueller Stand
• Informatik ist über die „Verarbeitung von Symbolen“ (=Zeichenketten, Informatik ist über die „Verarbeitung von Symbolen“ (=Zeichenketten, diskreten Strukturen) hinausgewachsendiskreten Strukturen) hinausgewachsen
• Neben der Verarbeitung von diskreten Daten gewinnt die digitale Neben der Verarbeitung von diskreten Daten gewinnt die digitale Verarbeitung kontinuierlicher Information zunehmend an BedeutungVerarbeitung kontinuierlicher Information zunehmend an Bedeutung
• Diese Themen sind dabei, der konventionellen Informatik Diese Themen sind dabei, der konventionellen Informatik „davonzulaufen“:„davonzulaufen“:• Signalverarbeitung zur Elektrotechnik/NachrichtentechnikSignalverarbeitung zur Elektrotechnik/Nachrichtentechnik• Embedded Systems zur Elektrotechnik/RegelungstechnikEmbedded Systems zur Elektrotechnik/Regelungstechnik• Simulation zur Physik, Chemie und Ingenieuren aus allen Simulation zur Physik, Chemie und Ingenieuren aus allen
DisziplinenDisziplinen• Visualisierung und Computergraphik zur Mathematik (Geometrie)Visualisierung und Computergraphik zur Mathematik (Geometrie)• ......
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 18
Ziele der VorlesungZiele der Vorlesung
Algorithmen und DatenstrukturenAlgorithmen und Datenstrukturen für kontinuierliche Modelle (Algorithmik III) für kontinuierliche Modelle (Algorithmik III)
• Digitale Verarbeitung kontinuierliche Daten als wichtiges (Zukunfts-) Digitale Verarbeitung kontinuierliche Daten als wichtiges (Zukunfts-) Thema der InformatikThema der Informatik
• Vermittlung der Grundlagen der Verarbeitung kontinuierlicher Daten Vermittlung der Grundlagen der Verarbeitung kontinuierlicher Daten (bereits im Grundstudium)(bereits im Grundstudium)
• Vorbereitung auf die Inhalte der Lehrveranstaltungen inVorbereitung auf die Inhalte der Lehrveranstaltungen in• MustererkennungMustererkennung• ComputergraphikComputergraphik• SimulationSimulation
• Diese Fächer benötigen die gleichen Grundlagen, wenn auch jeweils Diese Fächer benötigen die gleichen Grundlagen, wenn auch jeweils mit unterschiedlichen Schwerpunkten und aus jeweils einem anderen mit unterschiedlichen Schwerpunkten und aus jeweils einem anderen BlickwinkelBlickwinkel
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 19
ThemenübersichtThemenübersicht
• Was sind kontinuierliche DatenWas sind kontinuierliche Daten
• Datenstrukturen zur Behandlung kontinuierlicher DatenDatenstrukturen zur Behandlung kontinuierlicher Daten• Zahlwerte, Rundung, GleitpunktzahlenZahlwerte, Rundung, Gleitpunktzahlen• Datenstrukturen zur Approximation von kontinuierlichen Datenstrukturen zur Approximation von kontinuierlichen
ObjektenObjekten
• Vektoren und MatrizenVektoren und Matrizen• Koordinatensysteme und -transformationenKoordinatensysteme und -transformationen• OptimierungsverfahrenOptimierungsverfahren• ParameterschätzungParameterschätzung
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 20
Geplanter Inhalt: allgemeinGeplanter Inhalt: allgemein
• Mathematisch orientiertMathematisch orientiert
• Kombination vonKombination von• Abstraktion und PraxisrelevanzAbstraktion und Praxisrelevanz
• Mathematischer Präzision und AnschauungMathematischer Präzision und Anschauung
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 21
Geplanter Inhalt (1)Geplanter Inhalt (1)• Einfache Datenstrukturen zur Approximation kontinuierlicher DatenEinfache Datenstrukturen zur Approximation kontinuierlicher Daten
• Was sind kontinuierliche DatenWas sind kontinuierliche Daten• Zahlwerte im Zahlwerte im R• Reelle Zahlen und GleitpunktzahlenReelle Zahlen und Gleitpunktzahlen
• RundungRundung• Algorithmen mit Gleitpunktzahlen: FehlerfortpflanzungAlgorithmen mit Gleitpunktzahlen: Fehlerfortpflanzung• Kondition und StabilitätKondition und Stabilität• FehlerbegriffeFehlerbegriffe• IntervallarithmetikIntervallarithmetik
• Approximation von Relationen und Funktionen im Approximation von Relationen und Funktionen im Rd
• Pixel- und VoxelmodellePixel- und Voxelmodelle• Fluch der DimensionFluch der Dimension• Quad- und OctreesQuad- und Octrees
• Funktionen Funktionen R R R R • AbtasttheoremAbtasttheorem• DiskretisierungDiskretisierung• QuantisierungQuantisierung
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 22
Geplanter Inhalt (2)Geplanter Inhalt (2)
• Vektoren und MatrizenVektoren und Matrizen• Schreibweise und BezeichnungenSchreibweise und Bezeichnungen• Normen, Skalarprodukt, OrthogonalitätNormen, Skalarprodukt, Orthogonalität• Elementare TransformationsmatrizenElementare Transformationsmatrizen
• RotationRotation• Projektion (orthogonal, perspektivisch)Projektion (orthogonal, perspektivisch)• ......
• Datenstrukturen für Vektoren und MatrizenDatenstrukturen für Vektoren und Matrizen• Lineare GleichungssystemeLineare Gleichungssysteme
• RegulärRegulär• Überbestimmt (Methode der kleinsten Quadrate)Überbestimmt (Methode der kleinsten Quadrate)
• Koordinatensysteme und -transformationenKoordinatensysteme und -transformationen• OrthogonalisierungOrthogonalisierung
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 23
Geplanter Inhalt (4)Geplanter Inhalt (4)
• Approximation von Funktionen• Polynominterpolation• Approximation, Methode der kleinsten Quadrate• Faltung und Fourier• Fast Fourier Transformation (FFT)
• Geometrische Objekte• Kurven (Bezier, Splines)• Fläche
• Tensorprodukte• Dreiecks- und Polygonnetze• Finite Elemente
• Volumendatenstrukturen
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 24
Geplanter Inhalt (5)Geplanter Inhalt (5)
• OptimierungOptimierung• Quadratische OptimierungQuadratische Optimierung• Nichtlineare OptimierungNichtlineare Optimierung• GradientenverfahrenGradientenverfahren• NebenbedingungenNebenbedingungen• Diskrete OptimierungDiskrete Optimierung• Simuliertes Ausglühen (Simulated Annealing)Simuliertes Ausglühen (Simulated Annealing)
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 25
Vorläufiger Zeitplan (bis 11.5.07)Vorläufiger Zeitplan (bis 11.5.07)siehe auch im Internet:siehe auch im Internet:
www10.informatik.uni-erlangen.de für jeweils aktuelle Version für jeweils aktuelle Version
18.04. Einführung
20.04. Rundungsfehler
25.04. Kondition und Stabilität
27.04. Quantisierung und Diskretisierung, Filter
02.05. Datenstrukturen für Matrizen und Vektoren
04.05. Tag der Informatik (keine Vorlesung)
09.05. Matrix-Operationen: Grundlagen der linearen Algebra
11.05. Gauß-Seidel und SOR-Verfahren
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 26
Vorläufiger Zeitplan (ab 15.6.07)Vorläufiger Zeitplan (ab 15.6.07)
16.05. Elementare Matrixtransformationen: Rotation, Spiegelung, Projektion
18.05. Matrixalgorithmen I: Wiederholung Lineare Gleichungssysteme - Gauß-Algorithmus
23.05. Matrixalgorithmen 2: Faktorisierung, Inverse, spezielle Systeme
25.05. Matrixalgorithmen 3: Parameterschätzung, Mustererkennung mit Least Squares-Methoden
30.05. Matrixalgorithmen 4: Üb� er- und unterbestimmte Systeme: Computertomographie
01.06. Approximation und Interpolation 1: Einführung
06.06. Approximation und Interpolation 2: Polynominterpolation
08.06. Approximation und Interpolation 3: Bezierkurven
13.06. Approximation und Interpolation 4: Flächen
15.06. Approximation und Interpolation 5: Splines
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 27
Vorläufiger Zeitplan (ab 20.6.07)Vorläufiger Zeitplan (ab 20.6.07)
20.06. Volumenmodelle, Quadtrees, Flächen- und Volumenberechnung, Quadratur
22.06. Nichtlineare Systeme und Optmierung27.06. Heuristiken, Branch and Bound29.06. Simulated Annealing und Genetische Algorithmen04.07. Finite Differenzen06.07. Finite Elemente11.07. Fast Fourier Transformation (FFT) I13.07. Probeklausur18.07. Fast Fourier Transformation (FFT) II20.07. Data Mining und Suchmaschinen
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 28
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 29
Ferienakademie = Ferien + Akademie
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 30
Ferienakademie = Ferien + Akademie
● Aktuelle Themen wissenschaftlich erarbeitenAktuelle Themen wissenschaftlich erarbeiten
● Erlernen von Vortragstechniken ohne Erlernen von Vortragstechniken ohne
NotendruckNotendruck
● Zutrauen in eigene Fähigkeiten gewinnenZutrauen in eigene Fähigkeiten gewinnen
● Freizeitgestaltung: Bergwandern, Schach, TT, ...Freizeitgestaltung: Bergwandern, Schach, TT, ...
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 31
Ferienakademie = Ferien + Akademie
● Meinungsaustausch mit Professoren, Meinungsaustausch mit Professoren, Gastdozenten, und KommilitonenGastdozenten, und Kommilitonen
● Kontakte zur IndustrieKontakte zur Industrie
● Kaminabende mit Persönlichkeiten aus Kaminabende mit Persönlichkeiten aus
Industrie und WissenschaftIndustrie und Wissenschaft
● Anreise und Aufenthalt kostenlos!Anreise und Aufenthalt kostenlos!
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 32
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 33
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 34
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 35
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 36
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 37
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 38
Kurs 9: Numerical Simulation: From Models to Software
Thema:
Dozenten: Prof. H. Bungartz, TUMProf. U. Rüde, ErlangenProf. P. Bastian, Stuttgart
Teilnehmer: Ca. 15 Studierende, 2 wiss. Mitarbeiter, 3 Professoren
Institut für InformatikU. Rüde, G. Greiner: Algorithmik III - SS 2007 - VL 1a - Folie 39
Zeitraum: So., 23. September bis Fr., 5. Oktober 2007
Bewerbungsschluss: 18. Mai 2007
Ansprechpartner: U. Rü[email protected]
Weitere Infos: http://www5.in.tum.de/FA
Web-seite 2006: http://www5.in.tum.de/FA/2006/K6/K6_internal.html