Veranstalter
Allgemeines
Das Verhalten von randomisierten Algorithmen hängt von dem Ausgang von Zufallsexperimenten ab. Da sich randomisierte Algorithmen nicht deterministisch verhalten, können die Laufzeit und/oder die Korrektheit nur noch mit gewissen Wahrscheinlichkeiten garantiert werden. Jedoch sind randomisierte Algorithmen in den meisten Fällen effizienter und einfacher zu implementieren als deterministische Algorithmen. In diesem Seminar sollen ausgewählte Themen aus dem Bereich der randomisierten Algorithmen bearbeitet und vorgestellt werden.
Jedes Thema wird von zwei Personen bearbeitet. In Gruppenarbeit werden Sie einen Vortrag von 90 Minuten Dauer (ca. 45 Minuten je Teilnehmer) zu ihrem Thema ausarbeiten. Der Inhalt sollte möglichst verständlich präsentiert werden. Der Vortrag sollte dabei nicht vornehmlich die Seminarleiter ansprechen, sondern insbesondere Ihre Komilitonen.
Termine
- Mittwoch 19. Oktober, 15:15 Uhr, Raum 4017: Kurzpräsentationen (maximal 4 Minuten pro Teilnehmer)
- Mittwoch 2. November: Abgabe der Ausarbeitungen (maximal 4 Seiten pro Teilnehmer)
- Ab Mittwoch 9. November, jeweils 15:15 Uhr, Raum 4017: Vorträge (45 Minuten pro Teilnehmer, inklusive Diskussion) in unten aufgeführter Reihenfolge
- Mittwoch 18. Januar und 25. Januar: Seminar fällt aus
Vorlage für die Ausarbeitung
Themen
- Probabilistische Methode: Kapitel 5 aus [MR95]
Min Su und Zhonghua Long, Betreuer: Matthias Englert
- Markov Chains und Random Walks: Kapitel 6 aus [MR95]
Volker Nießen und Rami Salsaa, Betreuer: Matthias Englert
- Random Treaps und Skip Listen: Kapitel 8 aus [MR95]
Oliver Preuschel und Peter Schmitz, Betreuer: Matthias Westermann
- Hashing: Kapitel 8 aus [MR95] und [V04]
Hasem Soliman und Liang Huang, Betreuer: Matthias Westermann
- Random Sampling und Linear Programming: Kapitel 9 aus [MR95]
Tobias Walter und Christoph Rasim, Betreuer: Matthias Westermann
- Parallele Algorithmen auf einer PRAM: Kapitel 12 aus [MR95]
Sebastian Patzak und Eva Berckmann, Betreuer: Matthias Westermann
- Primzahltest: Kapitel 14 aus [MR95]
Benedikt Westermann und Josip Vlahovic, Betreuer: Matthias Englert
- Random Knapsack in Expected Polynomial Time: [BV04]
Matthias Botzen und Volker Böhme, Betreuer: Matthias Englert
- Bartals Baum-Metrik: [B96] und [FRT03]
Michael Arens und Andreas Feldmann, Betreuer: Matthias Englert
- Datenmanagement in Netzwerken: [MMVW97] und [MVW99]
Gert Menke, Betreuer: Matthias Westermann
- Hashing: Kapitel 8 aus [MR95] und [V04]
Hasem Soliman, Betreuer: Matthias Westermann
Literatur
- [B96]: Yair Bartal. Probabilistic Approximation of Metric Spaces and its Algorithmic Applications . In Proc. of the 37th Ann. IEEE Symp. on Foundations of Computer Science (1996), 184-193.
- [BV04]: Rene Beier und Berthold Vöcking. Random Knapsack in Expected Polynomial Time . Journal of Computer and System Sciences 69 (2004), 306-329.
- [FRT03]: Jittat Fakcharoenphol, Satish Rao und Kunal Talwar. A tight bound on approximating arbitrary metrics by tree metrics . In Proc. of the 35th Ann. ACM Symp. on Theory of Computing (2003), 448-455.
- [MMVW97]: Bruce Maggs, Friedhelm Meyer auf der Heide, Berthold Vöcking und Matthias Westermann. Exploiting Locality for Data Management in Systems of Limited Bandwidth ( full version ). In Proc. of the 38th Ann. IEEE Symp. on Foundations of Computer Science (1997), 284-293.
- [MR95]: Rajeev Motwani und Prabhakar Raghavan. Randomized Algorithms. Cambridge University Press, 1995.
- [MVW99]: Friedhelm Meyer auf der Heide, Berthold Vöcking und Matthias Westermann. Provably Good and Practical Strategies for Non-Uniform Data Management in Networks . In Proc. of the 7th Ann. European Symp. on Algorithms (1999), 89-100.
- [V04]: Berthold Vöcking. Zufälliges Hashing mit Anwendungen für Datenmanagement und P2P-Netzwerke . Manuskript (2004).