Proseminar Elegante Algorithmen

Sommersemester 2008

Veranstalter: Sven Rahmann (vorname.nachname[at]uni-dortmund.de)
Voraussetzungen: die DAP1-Vorlesung
Teilnehmerzahl: maximal 15
Termin: Freitags 12ct; erster Vortragstermin: 11.04.08
Raum: OH14, Raum 202

Vorbesprechung: Montag 11.02.08, 16:00, in OH14, Raum 202
Wer zu diesem Termin aus triftigen Gründen nicht kommen kann, aber trotzdem teilnehmen möchte, muss sich bei mir vorher per e-mail mit Begründung entschuldigen lassen. Andernfalls wird sie/er automatisch vom Proseminar ausgeschlossen.
Folien und Ergebnisse der Vorbesprechung als .pdf

Neu:Themen und Termine:
in dieser Datei. Bitte ggf. den RELOAD-Butten benutzen, um die aktuellste Version zu erhalten.
Achtung! Keine Sitzung am 18.04. Der Quicksort-Vortrag vom 18.04. findet zusammen mit dem über Kolinearität von 3 Punkten am 25.04. statt.

LaTeX-Muster zum Herunterladen. Ein pdf des Dokuments. (Update am 15.08.2008!)
Das Dokument kann unter linux u.ä. einfach mit make erstellt werden (sowohl dvi als auch pdf). Nennen Sie Ihr Kapitel einfach gemäß Ihrer Themennummer, z.B. 07.tex. Das Hauptdokument ist EleganteAlgorithmen.tex. Binden Sie Ihr Kapitel einfach dort ein und stören Sie sich nicht an der falschen Kapitelnummer.

Inhalt:
Der Mathematiker Paul Erdos war der Ansicht, dass es ein Buch ("das Buch") gibt, in dem Gott (oder ein Spaghetti-Monster) die schönsten und elegantesten Beweise für mathematische Theoreme aufgeschrieben hat, und dass es sehr selten vorkommt, dass ein Mensch einen kleinen Einblick in dieses Buch erhält. Auch Informatiker bemühen sich darum, den schnellsten, einfachsten, schönsten, elegantesten Algorithmus zu einem bestimmten Problem zu finden (nicht immer lassen sich alle diese Ziele gleich gut erreichen, häufig stehen z.B. Geschwindigkeit und Einfachheit im Gegensatz zueinander).
In diesem Proseminar wollen wir elegante Algorithmen für einige ausgewählte Probleme besprechen. Einige davon findet man in dem Buch "Beautiful Code", herausgegeben von Andy Oram und Greg Wilson. Andere werde ich aus weiteren Quellen zusammenstellen. Die Eleganz eines Resultates kann man häufig erst würdigen, wenn man versucht, das Problem einmal selbst zu lösen. In diesem Sinne sollen die Vorträge auch die Lösung des vorgestellten Problems von der ersten naiven Idee bis hin zum eleganten Endergebnis abdecken; eigenes Experimentieren bei der Vorbereitung ist sehr willkommen.
Die behandelten Algorithmen sind relativ kurz und einfach (darin liegt ihre Eleganz). Das bedeutet für die/den Vorrtagende/n, dass jede/r Teilnehmer/in den Vortrag vom Anfang bis zum Ende verstehen können muss.

Ablauf:

• Die Anmeldung erfolgt über das zentrale Verfahren.

• Die Vorträge sollen anhand der ausgegebenen Literatur vorbereitet werden, aber diese nicht einfach wiedergeben. Die Einarbeitung in die vorgeschlagene und bei Bedarf auch weitere Literatur erfolgt selbstständig, d.h., nicht im Rahmen einer Vorlesung o.Ä.

• Der Veranstalter übernimmt die fachliche Betreuung, d.h. er steht für inhaltliche Fragen und Fragen zur Vortragsgestaltung, nicht jedoch zur technischen Betreuung zur Verfügung.

• Eine in LaTeX erstellte Zusammenfassung des Vortragsthemas von ca. 5 Seiten ist bis spätestens 2 Wochen nach dem Vortrag beim Veranstalter abzugegeben. 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 den Vortrag und die Zusammenfassung eines anderen Teilnehmers. Erst wenn der Pate oder die Patin die Zusammenfassung korrekturgelesen und inhaltlich verstanden hat, wird diese beim Veranstalter abgegeben. Die Zusammenfassungen werden anschließend an alle Seminarteilnehmerinnen und -teilnehmer verteilt.

• Spätestens 2 Wochen vor dem Vortrag findet eine Zwischenbesprechung statt. Spätestens bis zu diesem Termin sollen alle inhaltlichen Fragen der jeweiligen Teilnehmer und Teilnehmerinnen geklärt sein. Bei der Zwischenbesprechung stellt der Veranstalter Fragen zum Vortragsthema, um sicherzustellen, dass der Stoff verstanden worden ist. Ein schlüssiges Vortragskonzept mit den wesentlichen Aussagen der zugrundeliegenden Literatur soll vorgestellt werden. Ein erster Entwurf der Vortragsfolien soll hierzu vorliegen! Dieser Entwurf sollte vom Paten begutachtet und für gut befunden worden sein!

• Eine ausreichende Zusammenfassung und eine ausreichende Zwischenbeprechung ist Voraussetzung für einen Proseminarvortrag.

Stand: 14.02.2008 - Sven Rahmann, nach einer Vorlage von Beate Bollig