Informatik-Logo
Fakultät für Informatik - Technische Universität München

Lehrstuhl für Effiziente Algorithmen

TUM-Logo

Hauptseminar: Algorithm Engineering

[Zusammenfassung] [Themenliste] [Anmeldung] [Vorbesprechung] [Termine] [Hinweise] [Literatur]

Zusammenfassung


Algorithm Engineering hat sich in jüngster Zeit als eigenständiges Teilgebiet der Algorithmik etabliert. Die klassische Algorithmik konzentriert sich hauptsächlich auf theoretische Analysen unter oft stark vereinfachenden, unrealistischen Voraussetzungen. Im Algorithm Engineering versucht man dagegen praxisrelevante Aspekte soweit wie möglich bei dem Entwurf, der Implementierung und der Analyse von Algorithmen zu berücksichtigen. QuickSort ist zum Beispiel in der Praxis häufig effizienter als seine asymptotisch besseren Konkurrenten. Man will nun einerseits verstehen, warum bestimmte Algorithmen in der Praxis besonders gut sind, andererseits aber auch die Erkenntnisse in den Entwurf von praktisch guten Algorithmen einfließen lassen. Dabei werden Algorithmen stets nicht nur theoretisch analysiert, sondern auch durch Experimente auf ihr Praxisverhalten untersucht. Wichtige Aspekte im Algorithm Engineering sind dabei zum Beispiel:

Im Hauptseminar sollen die Konzepte des Algorithm Engineering am Beispiel von grundlegenden Algorithmen und Datenstrukturen wie z.B. Sortieren, einfachen Graphenalgorithmen oder Priority Queues erarbeitet werden. Da es noch kein Buch zu diesem Thema gibt, basieren die einzelnen Themen in der Regel auf aktuellen Forschungsarbeiten. Wegen der interessanten Kombination aus Theorie und Praxis bieten sich einige der Themen auch als Anknüpfungspunkt für Bachelor- oder Diplomarbeiten an.


Themenliste:


Themenliste[pdf]


Anmeldung


Interessenten/innen können sich bei der Vorbesprechung oder vorab per Email an nowakj@in.tum.de mit Subject "Hauptseminar: Algorithm Engineering (Anmeldung)" anmelden. In der E-Mail sollen folgende Informationen enthalten sein:




Vorbesprechung


Donnerstag, 20.7.2006, 14:00(s.t.) im Raum 03.11.018


Termine und Betreuer


Das Seminar findet am Ende des Semesters als Blockveranstaltung statt. Der genaue Termin wird noch bekannt gegeben.

Hinweise


Ein Schein für die erfolgreiche Teilnahme am Proseminar wird vergeben, wenn folgende Leistungen erbracht worden sind (die Gesamtnote setzt sich aus gewichteten Einzelnoten zusammen):

Probevortrag (ohne Bewertung) Der Probevortrag erfolgt spätestens zum angegebenen Termin beim Betreuer. Vorzulegen sind dabei die fertig ausgearbeiteten Folien oder ähnliche Präsentationshilfsmittel und die Erstfassung der Seminarbeit.
Vereinbaren Sie für den Probevortrag rechtzeitig einen Termin beim Betreuer (spätestens eine Woche vor dem anvisierten Termin). Versuchen Sie, alle Verbesserungsvorschläge Ihres Betreuers umzusetzen.
Seminarvortrag (in mindestens zufriedenstellender Qualität) Der Seminarvortrag ist zum festgelegten Termin zu halten und dauert 45 (+/-5) Minuten. Tafelvorträge werden nicht akzeptiert. Nach dem Vortrag muss auf Fragen aus dem Publikum eingegangen werden.
Seminararbeit (in mindestens zufriedenstellender Qualität) Die Endfassung der Seminarbeit ist spätestens 2 Wochen nach dem Votrag als TeX-Datei und Postscript-Datei abzugeben. Der Umfang der Seminararbeit beträgt 5 (+/- 1) Seiten unter LaTeX, beispielsweise im LNCS-Style. Die Seminararbeit sollte von jedem interessierten Leser auch ohne Vortrag verstanden werden können. Auchten Sie besonders darauf, das Thema, über das Sie schreiben zu motivieren und Zusammenhänge herzustellen. (Hinweise siehe unten).
Anwesenheit bei allen Vorträgen Bei den einzelnen Vorträgen wird eine Anwesenheitsliste geführt. Da nur sehr wenige Vorträge stattfinden besteht Anwesenheitspflicht.

Ablauf der Vorbereitung

Der Vortrag und die Ausarbeitung müssen mit dem Betreuer abgesprochen werden. Hierzu sind nachfolgende Terminvorgaben bindend (soweit nicht anders mit dem Betreuer abgestimmt). Werden die Termine nicht eingehalten, führt dies zur Streichung des Vortrags und zum Nichtbestehen des Seminars:

bis 5 Wochen vor dem Vortragerstes Treffen mit dem Betreuer (vor dem Treffen ist die Literatur bereits zu lesen); der genaue Termin ist bei den Vortragsterminen angegeben;
bis 3 Wochen vor dem VortragGliederung des Vortrags und der Ausarbeitung mit dem Betreuer besprechen;
bis 1 Woche vor dem VortragProbevortrag vor den Betreuer; fertige Folien und vollständige erste Version der Ausarbeitung mit dem Betreuer abstimmen;
bis 2 Wochen nach dem Vortragfertige Ausarbeitung abgeben.

Hinweise zur Anfertigung einer Seminararbeit

* Die Seminararbeiten werden nach der letzten Seminarveranstaltung online zur Verfügung gestellt. Damit eine einheitliche Form erzielt wird, müssen alle Ausarbeitungen mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
  • Es ist der LNCS-Style (die Datei llncs.cls) des Springer-Verlages zu verwenden.
  • Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden.
  • Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden)
  • Die Ausarbeitung soll auf die verwendete Literatur verweisen, diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
* Bei Fragen zu LaTeX sei einerseits auf die folgenden Links hingewiesen, ferner kann auch der Betreuer um Hilfestellungen bzw. Literaturangaben gebeten werden:
* Eine weitere Anleitung zur Erstellung von Ausarbeitungen finden sie hier.
* Informationen zur Installation von LaTeX unter Windows finden Sie hier.

Hinweise zur Gestaltung der Vorträge

* Wer seine Folien mit LaTeX erstellen möchte findet hier einige Hinweise (einschließlich Rahmen-Datei als Vorlage)



Literatur



Eine detaillierte Literaturliste finden Sie hier: Literatur[pdf]
Johannes Nowak
Last modified: Tue Jul 18 13:29:03 CEST 2006