BannerHauptseite TUMHauptseite LehrstuhlMathematik SchriftzugHauptseite LehrstuhlHauptseite Fakultät

Lektüreseminar »Breaking the Worst Case«

Dozenten: Folkmar Bornemann, Caroline Lasser (Sommersemester 2012)

Teilnehmerzahl: 6 (min.) - 12 (max.)

Termin: donnerstags 14:00-15:30 Uhr im Seminarraum 02.08.011

Termine

Datum DiskussionsleitungSorted ascending Thema
19.7.   Smoothed Analysis [T, pp. 349-368]
24.5. Bergler Stochastische Konditionsanalyse [BC, Kapitel 2.2.6, 2.3, 2.4.1]
26.4. Bordt Normweise Kondition (Charakterisierungen) [BC, Kapitel 1]
19.4. Bornemann/Lasser Overtüre (Genauigkeit & Kondition) [BC, Kapitel 0]
31.5. Gaim Vorkonditionierung & Dreieckssysteme [BC, Kapitel 2.4.2-3.1]
03.5. Hofmann Singulärwertzerlegung und Least Squares [BC,Kapitel 1.4-1.6]
05.7. Hofmann Methode des steilsten Abstiegs [BC, Kapitel 5.1-5.2]
12.7. Keller Iterative Verfahren & Smoothed Analysis [BC, Kapitel 5.4; T, pp. 349-368]
14.6. Molina Dreieckssysteme [BC, Kapitel 3]
21.6. Troppmann Crash Kurs Stochastik (große Abweichungen, Zufallsmatrizen) [BC, Kapitel 4.1]
10.5. Zollner Stochastische Konzepte [BC,Kapitel 2.2 ohne 2.2.6]
28.6. Zollner Allgemeine Konditionsabschätzungen [BC, Kapitel 4.2.-4.4]

Inhalt

Für eine Reihe wichtiger Algorithmen (wie zum Beispiel das Gaußsche Eliminationsverfahren oder das Simplexverfahren ) weiß man, dass sie für praktisch auftretende Probleme sehr gut einsetzbar sind, kennt aber auch Worst-Case-Szenarien, in denen diese Algorithmen völlig wertlos sind. Die 2001 von Daniel Spielman und Shang-Hua Teng geschaffene Smoothed Analysis gilt als wissenschaftlicher Durchbruch für eine mögliche Erklärung dieses Phänomens. Die Grundidee der Smoothed Analysis ist die gezielte stochastische Störung von Input-Daten, so dass mit hoher Wahrscheinlichkeit der Worst Case gebrochen wird. Internationale Preise wie der Gödel-Preis 2008 und der Rolf-Nevanlinna-Preis 2010 dokumentieren, welche Bedeutung dieser neuen Theorie beigemessen wird. Das Seminar wird erklären, wie die Smoothed Analysis den Worst Case des Gaußschen Eliminationsverfahrens bricht. Benötigt werden Grundkenntnisse aus der linearen Algebra, der Stochastik und der Numerik. Das Seminar wird das faszinierende Wechselspiel, in welches die Smoothed Analysis etwas fortgeschrittenere Elemente dieser mathematischen Teildisziplinen versetzt, in langsamem und angemessenem Tempo entwickeln.

Ziele

Das Seminar ist ein gemeinsamer Lektüre- und Diskussionskurs des ersten Teils Adagio des Buchs Condition von Peter Bürgisser Pfeil und Felipe Cucker Pfeil, welches die Autoren vor seiner Veröffentlichung für diesen Kurs zur Verfügung stellen (der sehr viel schnellere und längere Hauptteil Allegro des Buchs befasst sich mit der kürzlich von den Autoren erbrachten partiellen Lösung des 17. Problems von Steve Smale Pfeil mittels Smoothed Analysis). Dieses Adagio schafft gute Voraussetzungen, um als Abschluss des Seminars die Originalarbeit von Arvind Sankar, Daniel Spielman, Shang-Hua Teng zur Smoothed Analysis der Gaußschen Elimination (2006) zu diskutieren.

Die Teilnehmer sollen im Seminar den eigenständigen Umgang mit wissenschaftlicher mathematischer Literatur erlernen und einüben. In der gemeinsamen wissenschaftlichen Diskussion der neuen Sachverhalte, Begriffe, Ideen und Argumentationslinien sollen Unklarheiten bereinigt, das mathematische Verständnis vertieft und eine professionelle Diskussionskultur eingeübt werden.

Ablauf

Pro Seminarsitzung werden die einzelnen Kapitel eingehend von allen diskutiert. Eine gewisse Selbstdisziplin, stets gut vorbereitet zu sein und durchgehend aktiv zu bleiben, ist hierzu zwingend erforderlich: Dazu gehört (a) wirklich jedes Kapitel auch eingehend studiert zu haben und (b) Fragen (jeder Art) schon vorab (hand)schriftlich zu skizzieren. Die Fragesammlungen sind unmittelbar vor jeder Sitzung an uns abzugeben und dienen dazu, eine lebendige Diskussion in Gang zu setzen. Jeder Seminarteilnehmer übernimmt für (wenigstens) eine Sitzung die Diskussionsleitung.

Literatur