Proseminar Algorithmen

Inhalt

Dieses Proseminar vertieft und erweitert die Vorlesung Algorithmen. Sie beschäftigen sich zu einem bestimmten Themengebiet mit Rechenverfahren und Prinzipien. Durch eine theoretische Analyse verinnerlichen Sie die Idee und das Konzept der von Ihnen behandelnden Algorithmen.

Das Proseminar wird in Form eines Blockseminars stattfinden. Während des Semesters wird das gewählte Thema erarbeitet und die Ausarbeitung verfasst; am Ende des Semesters trägt jeder seine Ergebnisse in einer Präsentation vor.

Es bestehen keine Voraussetzungen für diese Veranstaltung, allerdings ist es sinnvoll die Vorlesung Algorithmen schon gehört zu haben.

Einen ersten Eindruck über das Seminar findet sich in den Folien der Seminarvorstellung.

Ablauf

Zum Beginn des Seminars findet eine Vorbesprechung statt, an der die einzelnen Themen genauer vorgestellt werden. Anschließend findet die Themenvergabe über die Lernplattform moodle statt.

Das Seminar findet als Blockseminar am Ende des Semesters statt. Um das Seminar erfolgreich zu bestehen, muss eine Ausarbeitung des Themas (ca. 5-10 Seiten) angefertigt, sowie ein Vortrag (ca. 15-20 min) zum Ende des Semesters gehalten werden.

Das Seminar wird über die Lernplattform moodle organisiert, hier finden sich dann auch weitere Lehrmaterialien.

Themenliste (vorläufig)

Kombinatorische Optimierung:

  • Perfektes Matching mit minimalem Gewicht
  • Traveling Salesman Approximation
  • Knotenfärbung in Graphen

Baumartige Strukturen:

  • B-Bäume
  • Rot-Schwarz-Bäume
  • Binomial Heaps

Stringanalyse:

  • Rank und Select auf Bitvektoren
  • Wavelet Trees

Komprimierungstechniken

  • Huffman-Kodierung und arithmetische Kodierung
  • LZ77 und LZ78
  • Burrows-Wheeler-Transformation

Die Themenvergabe erfolgt über die Lernplattform moodle, natürlich können auch eigene Themen vorgeschlagen werden.

Verantwortung

Uwe Baier

Prof. Dr. Enno Ohlebusch

Vorbesprechung

Einführungsveranstaltung in der zweiten Semesterwoche am Mittwoch, dem 25.10. um 13:00 Uhr in O27/531

Weitere Informationen

LSF-Eintrag