Vorlesungen Diskrete Strukturen Effiziente Algorithmen und Datenstrukturen I Randomisierte Algorithmen Proseminar Proofs from The Book Praktikum Algorithmen-Entwurf Lehrveranstaltungen für Doktoranden Oberseminar

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)
  

  Date	Ch.	Sec.	Subs.	Topic
  18.10.2011:		0		Organization of the course
  		1		Planned topics of the course
  		2		Literature
  	I	1		Paradigms of Randomized Algorithms
  20.10.2011				(Continued)
  		2		What’s not in the course
  		3		Simple Examples
  			1	Randomized Quicksort
  25.10.2011				(Continued)
  			2	Min-Cut
  			3	Binary Planar Partition
  27.10.2011				(Continued)
  			4	Secretary Problem
  			5	Matrix Multiplication (Fingerprinting)
  03.11.2011			6	Game Tree Evaluation
  		4		Las Vegas vs. Monte Carlo
  		5		A Probabilistic Recurrence
  08.11.2011		6		Machine Models and Complexity Classes
  			1	Turing Machines and RAMs
  			2	Languages and (Decision) Problems
  			3	Complexity Classes
  10.11.2011			4	Reductions
  15.11.2011			5	Probabilistic Complexity Classes
  17.11.2011			6	(Randomized) Boolean Circuits and Uniformity
  19.11.2011				(Continued)
  			7	A simple derandomization
  	II			Moments and Deviations
  		1		Occupancy problems
  			1	Balls into bins
  24.11.2011				(Continued)
  			2	Birthdays
  		2		Markov and Chebyschev Inequalities
  		3		Two-Point Sampling and Probability Amplification
  				(Continued)
  29.11.2011		4		Principle of Deferred Decisions
  			1	Clock Solitaire
  			2	Stable Marriage Problem
  01.12.2011				(Continued)
  			3	Coupon Collector’s Problem
  03.12.2011				(Lecture cancelled)
  13.12.2011				(Continued)
  	III			Tail Inequalities
  		1		Chernoff Bounds
  15.12.2011				(Continued)
  20.12.2011				(Continued)
  		2		Routing in a Parallel Computer
  22.12.2011				(Continued)
  10.01.2012				(Continued)
  		3		A Wiring Problem
  12.01.2012				(Continued)
  		4		Martingales
  17.01.2012				(Continued)
  19.01.2012	IV			The Probabilistic Method
  		1		Game tree and set balancing revisited
  		2		Max-Cut
  		3		k-Max-SAT
  24.01.2012				(Continued)
  		4		Probabilistic construction and existence
  			1	Expanding graphs
  			2	Probability 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