LEA

Randomisierte Algorithmen

  • Dozent:
    Prof. Dr. Ernst W. Mayr
  • Modul:
    IN2160, TUMonline
  • Bereich:
    4+2 SWS Vorlesung im Bereich Informatik III (Theoretische Informatik)
    Wahlpflichtvorlesung im Gebiet Algorithmen
  • Zeit und Ort:
    Dienstag, 08:30–10:00, 00.13.009A
    Donnerstag, 08:30–10:00, 00.13.009A
    Achtung: Die Vorlesung am 2. Februar 2012 findet ausnahmsweise im Raum E.126, IMETUM, ZIMT statt!
    Achtung: Die Vorlesung am 8. Dezember fällt wegen Dies Academicus aus!
    Achtung: Die Vorlesung am 18. Oktober 2011 findet ausnahmsweise im Raum MI 00.08.038 statt!
  • Übung:
    2 SWS Übung zur Vorlesung
    Übungsleitung: Jeremias Weihmann
  • Klausur:
    Termin: Mo. 06.02.2012, 16:15 bis 19:15 Uhr, im Hörsaal 5510.01.050 (MW 1050, Johann-Bauschinger-Zeichensaal).
    Die angegebenen Zeiten sind die reinen Bearbeitungszeiten. Anwesenheit mindestens 15min vorher.
    Als Hilfsmittel ist nur ein beidseitig eigenhändig beschriebenes A4-Blatt mit Notizen zugelassen.
  • Klausureinsicht
    Die Klausureinsicht ist am Dienstag, 14. Februar 2012, von 16:15 bis 16:45 Uhr im Seminarraum 03.11.018.
  • Wiederholungsklausur:
    Termin: Mo. 02.04.2012, 14:15 bis 17:15 Uhr, im Seminarraum 03.11.018.
    Die angegebenen Zeiten sind die reinen Bearbeitungszeiten. Anwesenheit mindestens 15min vorher.
    Als Hilfsmittel ist nur ein beidseitig eigenhändig beschriebenes A4-Blatt mit Notizen zugelassen.
  • Hörerkreis:
    Studierende im Hauptstudium der Informatik
    Studierende mit Nebenfach Informatik
  • ECTS: 8 Punkte
  • Voraussetzungen:
    Stoff des Informatik Grundstudiums
    Vorlesung Effiziente Algorithmen und Datenstrukturen I vorteilhaft, aber nicht notwendig.
  • Empfehlenswert für:
    Grundkenntnisse im Bereich Algorithmen
  • Folien:
    Oktober:18. Oktober 2011
    Und hier gibt es alles in einer Datei! 
    (Hinweise zum Zugriff auf obige Folien)
  • Bisheriger Vorlesungsinhalt (der Inhalt orientiert sich grob am Motwani-Raghavan-Buch, siehe Literatur)
    DateCh.Sec.Subs.Topic
    18.10.2011:0Organization of the course
    1Planned topics of the course
    2Literature
    I1Paradigms of Randomized Algorithms
    20.10.2011(Continued)
    2What’s not in the course
    3Simple Examples
    1Randomized Quicksort
    25.10.2011(Continued)
    2Min-Cut
    3Binary Planar Partition
    27.10.2011(Continued)
    4Secretary Problem
    5Matrix Multiplication (Fingerprinting)
    03.11.20116Game Tree Evaluation
    4Las Vegas vs. Monte Carlo
    5A Probabilistic Recurrence
    08.11.20116Machine Models and Complexity Classes
    1Turing Machines and RAMs
    2Languages and (Decision) Problems
    3Complexity Classes
    10.11.20114Reductions
    15.11.20115Probabilistic Complexity Classes
    17.11.20116(Randomized) Boolean Circuits and Uniformity
    19.11.2011(Continued)
    7A simple derandomization
    IIMoments and Deviations
    1Occupancy problems
    1Balls into bins
    24.11.2011(Continued)
    2Birthdays
    2Markov and Chebyschev Inequalities
    3Two-Point Sampling and Probability Amplification
    (Continued)
    29.11.20114Principle of Deferred Decisions
    1Clock Solitaire
    2Stable Marriage Problem
    01.12.2011(Continued)
    3Coupon Collector’s Problem
    03.12.2011(Lecture cancelled)
    13.12.2011(Continued)
    IIITail Inequalities
    1Chernoff Bounds
    15.12.2011(Continued)
    20.12.2011(Continued)
    2Routing in a Parallel Computer
    22.12.2011(Continued)
    10.01.2012(Continued)
    3A Wiring Problem
    12.01.2012(Continued)
    4Martingales
    17.01.2012(Continued)
    19.01.2012IVThe Probabilistic Method
    1Game tree and set balancing revisited
    2Max-Cut
    3k-Max-SAT
    24.01.2012(Continued)
    4Probabilistic construction and existence
    1Expanding graphs
    2Probability Amplification
  • Literatur:
    Literatur zum Runterladen
    R. Motwani, P. Raghavan:
    Randomized Algorithms
    Cambridge University Press, 1995.
    C. Scheideler:
    Probabilistic Methods for Coordination Problems
    HNI-Verlagsschriftenreihe, Band 78, 2000.
  • Sprechstunde:
    siehe hier