• 19.06.2017: Der zweite Blocktermin findet am Samstag, den 24. Juni 2017, ab 10 Uhr im SR 055 statt. Der Raum befindet sich direkt neben dem Haupteingang.
• 18.05.2017: Der erste Blocktermin findet am Samstag, den 20. Mai 2017, ab 10 Uhr im SR 055 statt. Der Raum befindet sich direkt neben dem Haupteingang.
• 03.05.2017: Um den Terminkonflikt mit der Vorlesung Wissenschaftliches Arbeiten zu umgehen, werden wir Blocktermine durchführen, und zwar am Samstag, den 20. Mai 2017 und am Samstag, den 24. Juni 2017, jeweils ab 10 Uhr im SR 055.
  Alle Vortragenden müssen in der Woche vor ihrem Vortrag mit mir eine Vorbesprechung durchführen. Bitte vereinbaren Sie den Termin dazu mit mir per E-Mail.
• 18.04.2017: Die vorläufige Themenvergabe und ein vorläufiger Zeitplan sind online. Bei Fragen oder Änderungswünschen wenden Sie sich bitte an mich.
• 01.04.2017: Die Themenliste ist verfügbar.
• 02.02.2017: Die Website ist online.

Voraussetzungen

Erfolgreicher Abschluss der Veranstaltung "Algorithmen, Datenstrukturen und Datenabstraktion".

Termin

Das Proseminar findet statt am Dienstag von 16–18 Uhr im SR 046.

Literatur

• [VADRSVW]
  B. Vöcking, H. Alt, M. Dietzfelbinger, R. Reischuk, C. Scheideler, H. Vollmer, D. Wagner. Taschenbuch der Algorithmen. Springer Verlag, 2008
  [Springer-Link]
• [AP]
  G. Ausiello, R. Petreschi. The Power of Algorithms. Springer Verlag, 2013
• [C]
  T.H. Cormen. Algorithms Unlocked. MIT Press, 2013
• [CLRS]
  T.H. Cormen, C.E. Leiserson, R.L. Rivest, C. Stein. Introduction to Algorithms. MIT Press
• [KT]
  J. Kleinberg, E. Tardos. Algorithm Design. Pearson, 2006

Scheinkriterien

Für den Scheinerhalt muss man

• einen erfolgreichen Vortrag von insgesamt 70 Minuten Dauer halten.
• eine Kurzbeschreibung des Vortrags, ca. 4 DIN A4-Seiten in PDF, vorbereiten. Davon sind vor dem Vortrag Kopien an alle Teilnehmer_innen auszuteilen und ein elektronisches Exemplar abzugeben. Hier ist eine LaTex-Vorlage.
• regelmäßig am Proseminar teilnehmen (max. 2 Fehltermine).

Perspektiven

Im Anschluss an die Veranstaltung können Bachelorarbeiten vergeben werden.

Das Proseminar baut auf der Vorlesung "Algorithmen, Datenstrukturen und Datenabstraktion" auf und vertieft die dort behandelten Themen.

• 01. Paralleles Sortieren []

  Sortieren ist eines der ältesten Probleme der Informatik. Schneller geht es, wenn man einen Parallelrechner verwenden kann.

  Literatur: [VADRSVW, Kapitel 4] [CLRS, zweite Auflage, Kapitel 27]

• 02. Texte durchsuchen []

  Die Suche in Zeichenketten ist eines der häufigsten algorithmischen Probleme. Es sollen die Algorithmen von Boyer-Moore und von Knuth-Morris-Pratt vorgestellt werden.

  Literatur: [VADRSVW, Kapitel 6] [CLRS, dritte Auflage, Kapitel 34]

• 03. Datenkompression [Zacharias]

  Wie kann man einen Text so kompakt wie möglich speichern?

  Literatur: [C, Kapitel 9]

• 04. Der Pledge-Algorithmus [Benjamin Kahl]

  Wie kann man im Dunklen aus einem Labyrinth entkommen?

  Literatur: [VADRSVW, Kapitel 8]

• 05. Page-Rank [Anonymus]

  Wie bewertet Google Seiten im World-Wide-Web?

  Literatur: [VADRSVW, Kapitel 10] [J. Kleinberg. Hubs, Authorities, and Communities] [AP, Kapitel 5]

• 06. Multiplikation langer Zahlen [Yoshi]

  Der Algorithmus aus der Grundschule zum Multplizieren zweier Zahlen ist nicht optimal.

  Literatur: [VADRSVW, Kapitel 11]

• 07. Das Teilen von Geheimnissen [Luis Herrmann]

  Wie kann man ein Geheimnis unter mehreren Personen aufteilen, so dass sie es nur gemeinsam entschlüsseln können?

  Literatur: [VADRSVW, Kapitel 17]

• 08. Poker per E-Mail []

  Wie kann man per E-Mail Poker spielen, ohne dass jemand schummelt?

  Literatur: [VADRSVW, Kapitel 18]

• 09. Der Alpha-Beta Algorithmus [Maria Hartmann]

  Der Alpha-Beta Algorithmus ist ein klassischer Algorithmus zum Durchsuchen von Spielbäumen.

  Literatur: [VADRSVW, Kapitel 28]

• 10. Flüsse in Netzwerken [Gesa]

  Mit Hilfe von Netwerkflüssen lassen sich vielen Probleme modellieren, von Eisenbahnen über Buslinien zu Devisenhandel.

  Literatur: [VADRSVW, Kapitel 36] [CLRS, Kapitel 27]

• 11. Stabile Paarungen [Mika]

  Wie kann man Praktikanten auf Stellen verteilen, so dass niemand unglücklich wird?

  Literatur: [VADRSVW, Kapitel 37] [KT, Kapitel 1]

• 12. Keinster umschließender Kreis [Janis Meyer]

  Was ist der optimale Ort, um eine Eisdiele zu eröffnen?

  Literatur: [VADRSVW, Kapitel 38]

• 13. Online-Algorithmen []

  Was tun, wenn man die Zukunft nicht kennt?

  Literatur: [VADRSVW, Kapitel 39]

• 14. Simuliertes Abkühlen und andere Heuristiken []

  Für manche Probleme ist es sehr schwierig, effiziente Algorithmen zu entwickeln. Hier helfen Heuristiken, in vielen Situationen trotzdem eine einigermaßen gute Lösung zu finden. Simuliertes Abkühlen ist ein bekanntes Beispeil, aber es unzählige weitere Verfahren.

  Literatur: [VADRSVW, Kapitel 43] [KT, Kapitel 12]

(Die Zusammenfassungen und Folien der Teilnehmer_innen sind ohne Gewähr der Richtigkeit.)

Im Web gibt es viele Ressourcen mit nützlichen Tipps zur effektiven Gestaltung eines Vortrags. Hier einige Beispiele, die mir gefallen haben.

1. Christian Knauer und Frank Hoffmann.
   Wie gestalte ich einen Seminarvortrag?
   Etwas alt, aber immer noch interessant.
2. Ian Parberry.
   How to Present a Paper in Theoretical Computer Science: A Speaker's Guide for Students.
   Spezielle Tipps für die theoretische Informatik.
3. Paul Halmos.
   How to talk Mathematics.
   Für Mathematiker, aber vieles trifft auch auf die theoretische Informatik zu.
4. Patrick Winston.
   How to speak.
   Lustiges Video. Die ersten fünf Minuten kann man getrost überspringen.

Hier die Fragen, von denen ich mich bei der Bewertung eines Seminarvortrags leiten lasse.