Schriftzug: Fachbereich Mathematik 
  UHH > Fakultäten > MIN-Fakultät > Mathematik > Personen   Sitemap Suchen Hilfe there is no english version of this page  
 

Vorlesung: Probabilistische Methoden

Dozent: Dr. Mathias Schacht

Termine

  • 01.04.2010 (erste VL)
  • 08.04.2010 (erste UE), 27.04.2010 (zweite UE)
VL Donnerstag 12:00 - 14:00 Geomatikum, H3
VL/UE Dienstag 12:00 - 14:00 Geomatikum, H3

Leistungsnachweis

  • Bestehen der mündlichen Prüfung
  • Termin nach Absprache

Zuordnung

  • Vertiefungsvorlesung, Master
  • 3+1 SWS
  • Graphentheorie und Diskrete Mathematik

Voraussetzungen

  • Keine. Grundkentnisse aus den Gebieten Graphentheorie, Diskrete Mathematik und Stochastik sind hilfreich, aber nicht notwendig.

Überblick

Die Vorlesung folgt dem Buch The probabilistic method von Alon und Spencer. Anhand vieler Beispiele aus der Diskreten Mathematik werden folgende Methoden vorgestellt
  • Momentmethode,
  • Local Lemma,
  • Martingale und Randungleichungen.

Inhalte

  1. Grundlagen (01.04.-06.04.)
    • Kapitel 1 und 2.1 aus [MV]
  2. Einführede Beispiele (06.04.-15.04.)
    • Sätze 2.2.4, 2.3.2 und 2.4.1 aus [MV]
    • Sätze 1.3.2 und 1.4.1 aus [AS]
  3. Erwartungswert und 1. Momentmethode (15.04.-22.04.)
    • Kapitel 3 aus [MV]
    • Sätze 2.4.1, 2.4.2 und Satz von Brègman aus [AS]
    • Markow'sche Ungleichung (z.B. Lemma 4.0.2 in [MV])
  4. Anpassungen und Modifikationen (29.04.-04.05.)
    • Kapitel 4 aus [MV]
    • Kapitel 3.5 aus [AS]
  5. Varianz und 2. Momentmethode (06.05.-01.06.)
    • Kapitel 5 aus [MV]
  6. Local Lemma (01.06.-10.06.)
    • Kapitel 6 aus [MV]
  7. Randungleichungen, Martingale und Konzentration von Zufallsvariablen (15.06.-06.07.)
    • Kapitel 7.1-7.3 aus [MV]
    • Kapitel 8.1 und 8.3 aus [MV]
    • Kapitel 7.3 aus [AS]
    • Kapitel 2.4 aus [JŁR] (Beweis der Azuma-Hoeffding-Ungleichung)
    • Kapitel 10.1 und 10.2 aus [MR] (Talagrand-Ungleichung und Anwendungen)

Übungen

Übungen finden zweiwöchentlich (im Wechsel mit der Vorlesung) am Donnerstag Dienstag statt. In den Übungen wird der Stoff der Vorlesung vertieft und es werden die Übungaufgaben besprochen.

Literatur

  • N. Alon & J. H. Spencer: The probabilistic method, Wiley, 3rd ed., 2008
  • B. Bollobás: Random graphs, Cambridge University Press, 2nd ed., 2001
  • S. Janson, T. Łuczak & A. Ruciński: Random graphs, Wiley, 2000
  • J. Matoušek & J. Vondrák: The probabilistic method, Vorlesungsskript, 2008
  • M. Molloy & B. Reed: Graph colouring and the probabilistic method, Springer, 2002

 
  Seitenanfang  Impressum 2010-07-06, Mathias Schacht