Proseminar
Randomisierte Algorithmen
Wintersemester 2017/18
[Hinweis]
[Termine]
[Präsentationskurs]
[Inhalt]
[Literatur]
[Material]
[Organisation]
Mo, 16.10.2017, findet um 10-12 Uhr in OH 14 R 304 Ein Streifzug durch die diskrete Stochastik (Vortrag)
statt.
Mo, 30.10.2017 und 06.11.2017, sowie Mi, 08.11.2017, findet um 12-14 Uhr bzw. 16-18 Uhr in OH 14 R 304
Offenes Arbeiten statt.
Mo 12:15-14:00 Uhr, OH 14 R 304 und
Mi 16:00-18:00 Uhr, OH 14 R 304
Die Veranstaltung beginnt am Montag, 09.10.2017.
Das Proseminar findet inklusive Präsentationskurs statt.
In den ersten Wochen wird die Veranstaltung mit 4 SWS stattfinden, später auf 2 SWS reduziert,
so dass sich insgesamt ein Umfang von 3 SWS für Proseminar und Präsentationskurs ergibt.
Randomisierte Algorithmen sind eine in den Anwendungen
nützliche Verallgemeinerung deterministischer Algorithmen, solange
die Wahrscheinlichkeit unerwünschter Verhaltensweisen wie zu lange
Rechenzeiten oder die Berechnung falscher Ergebnisse sehr gering ist.
Sie zeichnen sich häufig durch ihre Einfachheit und ihre Effizienz bei
der Lösung komplexer Aufgaben aus.
In diesem Proseminar wird der Entwurf und die Analyse grundlegender randomisierter Algorithmen behandelt.
Wir wollen u.a.
die folgenden Entwurfsmethoden kennenlernen:
- Ü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
Die Kenntnis dieser Entwurfsmethoden hilft uns bei der gezielten
Suche nach einem effizienten randomisierten Verfahren
für ein zu untersuchendes Problem.
Zum Einlesen:
Giving an academic talk
[zuletzt abgerufen: 30.08.2017]
Die folgenden Bücher beschäftigen sich mit wissenschaftlichen Ausarbeitungen.
-
Kremer, B. P. (2009)
Vom Referat bis zur Examensarbeit, 3. Auflage
Springer
Insbesondere in Kapitel 5 finden sich viele Beispiel zum Thema "Verständlich schreiben".
Das Buch ist aus dem Hochschulnetz der TU DO auch online verfügbar.
Das folgende Buch beschäftigt sich insbesondere mit wissenschaftlichen Ausarbeitungen in der Informatik.
-
Gockel, T. (2010)
Form der wissenschaftlichen Ausarbeitung, 2. Auflage
Springer
Das Buch ist aus dem Hochschulnetz der TU DO auch online verfügbar.
Fachliche Grundlage für das Proseminar ist die folgende Literatur.
-
Aigner, M., Ziegler, G.M.: Das Buch der Beweise. Vierte Auflage, Springer 2015.
Alternativ: Aigner, M., Ziegler, G.M.: Proofs from The Book. Fünfte Auflage,
Springer 2014.
Kapitel Gut genug gemischt? und Kapitel Die Probabilistische Methode.
Das Buch ist aus dem Hochschulnetz der TU DO auch online verfügbar.
- Hromkovic, J. (2004).
Randomisierte Algorithmen.
Teubner Verlag.
Das Buch soll vollständig im Proseminar behandelt werden.
Es ist in der Universitätsbibliothek der TU DO verfügbar.
- Motwani, R., Raghavan, P. (1995).
Randomized Algorithms.
Cambridge University Press.
Kapitel 10.1 All-pairs Shortest Paths und Kapitel 10.3 Minimum Spanning Trees.
Das Buch ist in der Universitätsbibliothek der TU DO verfügbar.
- Schöning, U. (1995).
Perlen der Theoretischen Informatik.
BI-Wissenschaftsverlag.
Kapitel 5 LOGSPACE, Zufallsirrfahrten auf Graphen und universelle Durchlaufsequenzen,
Kapitel 14 Äquivalenzprobleme und untere Schranken bei Branching Programmen
(Ergänzung zu Kapitel 4 aus dem Buch Randomisierte Algorithmen) und
Kapitel 17 Probabilistische Algorithmen,
Wahrscheinlichkeitsverstärkung und Recycling von Zufallszahlen.
Das Buch ist in der Universitätsbibliothek der TU DO verfügbar.
Ergänzend zu Kapitel 6 aus dem Buch Randomisierte Algorithmen ist das folgende Buch.
-
Dietzfelbinger, M. (2004).
Primality Testing in Polynomial Time.
Springer.
Kapitel 5 und 6.
Das Buch ist aus dem Hochschulnetz der TU DO auch online verfügbar.
Eine gute Einführung in die Grundlagen der diskreten Wahrscheinlichkeitstheorie bietet das folgende Buch.
- Schickinger, T., Steger, A. (2001).
Diskrete Strukturen, Band 2.
Springer.
Kapitel 1.1-1.6.
Das Buch ist in der Universitätsbibliothek der TU Dortmund vorhanden.
Hier werden die Veranstaltungsmaterialien, d.h. die
Folien und Arbeitsblätter der Veranstalterin, hochgeladen.
Inhalt |
Materialien |
Notizen |
Einführungsveranstaltung |
PDF |
|
Fehlerliste Buch Randomisierte Algorithmen |
PDF |
|
Nützliche Formeln |
PDF |
|
Bewertungskriterien
Präsentationen
(Anhaltspunkte) |
PDF |
Version 29.11.2017
Tippfehler korrigiert |
Checkliste Schreiben |
PDF |
|
Checkliste Vortrag |
PDF |
|
Feedback |
PDF |
Noch nicht freigegeben |
Review |
PDF |
Version 20.11.2017
Tippfehler korrigiert |
Streifzug durch die diskrete Stochastik |
PDF |
|
Präsentationstechniken Teil 1 |
PDF |
Version 20.10.2017 |
Präsentationstechniken Teil 2 |
PDF |
Version 30.10.2017 |
-
Notwendige Voraussetzung für einen Vortrag ist eine gute inhaltliche Vorbereitung.
-
Die Vorträge sollen anhand der angegebenen Literatur selbstständig vorbereitet werden.
Gerne kann weitere Literatur benutzt werden.
-
Die mathematischen Inhalte des jeweiligen Themas sollen im Detail verstanden werden,
auch wenn aufgrund begrenzter Zeit nicht alles im Vortrag dargestellt werden kann.
Bei Problemen, die nach hinreichender Auseinandersetzung mit den jeweiligen Quellen
nicht eigenständig gelöst werden können,
steht die Veranstalterin für konkrete Fragen
in ihrer Sprechstunde zur Verfügung.
-
Zwei Wochen vor dem Vortrag findet eine Zwischenbesprechung statt.
Spätestens bis zu diesem Termin sollen alle
inhaltlichen Fragen des Vortragenden geklärt sein.
Es soll ein schlüssiges Vortragskonzept mit den
wesentlichen Aussagen der zugrundeliegenden Literatur
vorgestellt werden.
Die Veranstalterin stellt in der Zwischenbesprechung Fragen zum Vortragsthema,
um sicherzustellen, dass der Stoff verstanden worden ist.
-
Eine ausreichende Zwischenbesprechung ist
Voraussetzung für einen Proseminarvortrag!
-
Eine in Latex erstellte schriftliche Präsentation des Vortragsthemas von maximal sieben Seiten
ist bis spätestens eine Woche vor dem Vortrag elektronisch
als pdf-file bzw bei der Veranstalterin abzugeben (Endversion!).
Diese sollte sorgfältig erstellt werden und
den wesentlichen Inhalt des Vortragsthemas in eigenen Worten prägnant darstellen.
-
Jeder Teilnehmer und jede
Teilnehmerin ist Pate für die schriftliche Präsentation eines anderen Studierenden.
Erst wenn der Pate oder die Patin
diese korrekturgelesen und inhaltlich verstanden hat, wird sie bei der Veranstalterin
abgegeben.
-
Der Abgabe ist eine unterschriebene Erklärung mit folgendem Wortlaut beizufügen:
Hiermit erkläre ich, dass ich meine Abgabe eigenständig und nur mit den angegebenen Hilfsmitteln
und der angegebenen Literatur verfasst habe.
Seitenanfang
Letzte Änderung: 20.11.2017 von B. Bollig