Proseminar
Randomisierte Algorithmen
Wintersemester 2005/2006
| Veranstalterin: |
Beate Bollig
beate.bollig uni-dortmund.de
|
|
| Voraussetzung: |
DAP 2, wünschenswert GTI |
| Termin: |
wöchentlich jeweils dienstags, 8:00-10:00 Uhr |
| Raum: |
GB IV 318 |
Inhalt:
Randomisierung ist ein Schlüsselkonzept der Informatik. In diesem
Proseminar wird der Entwurf und die Analyse randomisierter
Algorithmen eingeführt. Diese sind eine in den Anwendunngen
nützliche Verallgemeinerung deterministischer Algorithmen, solange
die Wahrscheinlichkeit unerwünschter Verhaltensweisen wie zu lange
Rechenzeiten oder die Berechnung falscher Ergebnisse sehr gering ist.
Wir werden sehen, wie sich randomisierte Algorithmen häufig durch ihre
Einfachheit und ihre Effizienz bei der Lösung komplexer
Aufgaben auszeichnen.
Die Vorträge werden sich u.a. mit den folgenden Entwurfsparadigmen
randomisierter Algorithmen beschäftigen:
- Überlisten des Gegners (Vermeiden von schlechten Fällen)
- Methode der Fingerabdrücke
- Wahrscheinlichkeitsverstärkung durch Wiederholungen
- Stichprobenmethode
- Methode der häufigen Zeugen
- Zufälliges Runden
Literatur:
Juraj Hromkovic (2004).
Randomisierte Algorithmen.
Teubner Verlag.
Der weitere Ablauf ist der folgende:
-
Die Vorträge sollen anhand der angegebenen Literatur vorbereitet werden.
Die Einarbeitung in die vorgeschlagene und bei Bedarf auch
weitere Literatur erfolgt
selbstständig, d.h.
nicht im Rahmen einer Vorlesung o.Ä.
Die Veranstalterin steht aber
für inhaltliche Fragen und Fragen zur Vortragsgestaltung zur Verfügung.
Nützliche Hinweise zur Vortragsgestaltung finden sich hier:
Hinweise als PS-File
Spätestens 4 Wochen vor dem Vortrag findet
eine Zwischenbesprechung statt.
Die Teilnehmer und Teilnehmerinnen sollten
jeweils ein schlüssiges Konzept vorstellen, d.h. die
wesentlichen Aussagen der zugrundeliegenden Literatur sollte verstanden sein.
Eine in Latex erstellte Zusammenfassung
des Vortragsthemas von ca 3 Seiten ist bis spätestens 3 Wochen vor dem Vortrag
bei der Veranstalterin abzugegeben.
Die Zusammenfassungen werden anschließend
an alle Seminarteilnehmerinnen und -teilnehmer verteilt.
1.10.2005 - Beate
Bollig