Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Proseminar

Randomisierte Algorithmen

Wintersemester 2017/18

Prof. (apl) Dr. Beate Bollig

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

Hinweis

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.

Termine

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.

Präsentationskurs

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.

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

Literatur

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.

Material

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

Organisation

  • 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