Sprungmarken

Servicenavigation

       

Hauptnavigation

Bereichsnavigation

Proseminar

Randomisierte Algorithmen

Wintersemester 2017/18

Prof. (apl) Dr. Beate Bollig


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


Hinweis

Aufgrund der hohen Anzahl der Teilnehmenden wird sich der zeitliche Ablauf des Proseminars möglicherweise verändern.


Termine

Mo 12-14 Uhr, OH 14 R 304 und
Mi 16-18 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 wollen wir u.a. 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 33 Gut genug gemischt? und Kapitel 44 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.


Material

Hier werden die Veranstaltungsmaterialien, d.h. die Folien und Arbeitsblätter der Veranstalterin, hochgeladen.
Inhalt Materialien Version Notizen
Fehlerliste
Buch Randomisierte Algorithmen
PDF Noch nicht freigegeben
Nützliche Formeln PDF Noch nicht freigegeben
Bewertungskriterien
Präsentationen
(Anhaltspunkte)
PDF Noch nicht freigegeben
Checkliste Schreiben PDF Noch nicht freigegeben
Checkliste Vortrag PDF Noch nicht freigegeben

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.
  • Ungefähr 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.
    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: 22.09.2017 von B. Bollig