Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Proseminar

Randomisierte Algorithmen

Wintersemester 2018/19

Prof. (apl) Dr. Beate Bollig

[Hinweis] [Termine] [Präsentationskurs] [Inhalt] [Literatur] [Material] [Organisation]

Hinweis

Solide Kenntnisse mathematischer Notationen und wahrscheinlichkeitstheoretischer Grundlagen sind für dieses Proseminar eine Voraussetzung.

Termine

Mi 14:00-16:00 Uhr, OH 14 R 304 und
Mi 16:00-18:00 Uhr, OH 14 R 304
Die Veranstaltung beginnt am Mittwoch, 10.10.2018.

Präsentationskurs

Das Proseminar findet inklusive Präsentationskurs statt. In den ersten und letzten Wochen wird die Veranstaltung mit 4 SWS stattfinden. Insgesamt ergibt sich ein Umfang von 3 SWS für Proseminar und Präsentationskurs.

Inhalt

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. Allgemein gewinnen stochastische Methoden im Zeitalter von Big Data zunehmend an Bedeutung. In diesem Proseminar beschäftigen wir uns mit dem Entwurf und der Analyse grundlegender randomisierter Algorithmen. Wir lernen verschiedene Arten von randomisierten Algorithmen kennen und behandeln u.a. die folgenden Entwurfsmethoden:

  • Ü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 kann uns bei der gezielten Suche nach einem effizienten randomisierten Verfahren für ein zu untersuchendes Problem helfen. Darüberhinaus vertiefen wir unser Verständnis, wie und warum Randomisierung es ermöglicht, Probleme effizient algorithmisch zu lösen.

Literatur

Zum Einlesen:

Giving an academic talk [zuletzt abgerufen: 04.06.2018]

Three sins of authors in computer science and math [zuletzt abgerufen: 23.07.2018]

Die folgenden Bücher beschäftigen sich mit wissenschaftlichen Ausarbeitungen, das zweite insbesondere mit wissenschaftlichen Ausarbeitungen in der Informatik.

  • Kremer, B. P. (2014). Vom Referat bis zur Examensarbeit, 4. 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.

  • Gockel, T. (2010). Form der wissenschaftlichen Ausarbeitung, 2. Auflage. Springer
    • Das Buch ist aus dem Hochschulnetz der TU DO auch online verfügbar.

Eine umfassende Einführung in LaTeX liefert das folgende Buch.

  • Datta, D. (2017). LaTeX in 24 hours. 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. (2018). Das Buch der Beweise, 5. Auflage. Springer.
    Kapitel Gut genug gemischt? und Kapitel Die Probabilistische Methode.

    • Das Buch ist aus dem Hochschulnetz der TU DO auch online verfügbar. Die Buchauflage ist unwesentlich.

  • 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.

Ergänzend zu Kapitel 4 aus dem Buch Randomisierte Algorithmen ist das folgende Buch.

  • Schöning, U. (1995). Perlen der Theoretischen Informatik. BI-Wissenschaftsverlag.
    Kapitel 14 Äquivalenzprobleme und untere Schranken bei Branching Programmen.

    • 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.

Material

Hier werden die Veranstaltungsmaterialien, d.h. die Folien und Arbeitsblätter der Veranstalterin, hochgeladen. Die Lehrveranstaltungsunterlagen sind für den persönlichen Gebrauch der Teilnehmer und Teilnehmerinnen der Veranstaltung gedacht, insbesondere die elektronische Verbreitung ist ohne Zustimmung der Dozentin nicht erlaubt.
Inhalt Materialien Notizen
Einführungsveranstaltung PDF
Fehlerliste
Buch Randomisierte Algorithmen		 PDF
Review-Bogen PDF
Checkliste Präsentation PDF
Präsentationstechniken PDF
Bewertungskriterien Präsentationen PDF

Organisation

Im folgenden stehen einige Hinweise zum Ablauf und zu den Anforderungen des Proseminars. Details werden in der ersten Sitzung besprochen.

  • Notwendige Voraussetzung für einen Vortrag ist eine gute inhaltliche Vorbereitung.
    Diese erfolgt selbstständig mit Hilfe der angegebenen Literatur.
    Dabei sollen die mathematischen Inhalte des jeweiligen Themas im Detail verstanden werden,
    auch wenn aufgrund begrenzter Zeit nicht immer alles im Vortrag dargestellt werden kann.
    Gerne kann weitere Literatur benutzt werden.

  • 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, in der die Veranstalterin
    Fragen zum Vortragsthema stellt, um sicherzustellen, dass der Stoff verstanden worden ist.
    Vor der Zwischenbesprechung sollen alle inhaltlichen Fragen des Vortragenden bereits geklärt sein.
    Darüberhinaus sollen die Studierenden ein schlüssiges Vortragskonzept mit den wesentlichen
    Aussagen der zugrundeliegenden Literatur in der Zwischenbesprechung vorstellen.

  • Eine ausreichende Zwischenbesprechung ist Voraussetzung für die Teilnahme an der Modulprüfung.
    Diese besteht aus der Zusammenfassung und der mündlichen Präsentation,
    beide Teile müssen für einen erfolgreichen Abschluss mindestens ausreichend sein.

  • Eine sorgfältig in Latex erstellte Zusammenfassung des Vortragsthemas ist spätestens eine Woche vor dem Vortrag
    entweder elektronisch als pdf-file oder als ausgedrucktes Exemplar bei der Veranstalterin abzugeben (Endversion).
    Der wesentliche Inhalt des Vortragsthemas soll in eigenen Worten prägnant dargestellt werden.

  • Jeder Teilnehmer und jede Teilnehmerin ist Pate für die schriftliche Präsentation eines anderen Studierenden
    und gibt diesem eine Rückmeldung in Form eines Peer-Reviews. Erst wenn der Pate oder die Patin die schriftliche Präsentation
    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: 30.10.2018 von B. Bollig