Seminar
Ausgewählte Kapitel der Kombinatorik: Kombinatorische Algorithmen


Wintersemester 2017/18
Prof. Stefan Felsner
Sprechstunde n.V.

LV-Nr.: 3236 L 316


Zeichnung



Vorbesprechung und Themenvergabe finden am 19. Oktober um 16:00 im MA541 statt.

Das Seminar selbst wird an einem Wochenende als Blockseminar im Umland durchgeführt.


Thema:

Ein Algorithmus ist ein kombinatorischer, wenn er kombinatorische Daten verarbeitet. Eine klassische Aufgabe ist es einen Algorithmus zu entwerfen, der bei Eingabe von n alle 0-1 Strings der Länge n auflistet. Die einfachste Lösung besteht darin die Strings in lexikographischer Ordnung zu generieren. Es gibt aber auch Algorithmen, die die Strings in einer Reihenfolge erzeugen, in der sich aufeinanderfolgende Strings nur in einer Position unterscheiden. Neben dem Erzeugen aller Elemente einer kombinatorischen Menge M kann die Aufgabe eines kombinatorischen Algorithmus auch im Zählen der Elemente von M oder im Auffinden eines Objekts mit speziellen Eigenschaften in der Menge M bestehen.

Hier ein Zitat von D. Knuth zum Thema kombinatorische Algorithmen The art of writing such programs is especially important and appealing because a single good idea can save years or even centuries of computer time.

In diesem Seminar sollen ausgewählte kombinatorische Algorithmen vorgestellt und analysiert werden. Einführungen in die Theorie der kombinatorischen Algorithmen findet man in:

Zielgruppe:

Studentinnen und Studenten der Mathematik, Techno- und Wirtschaftsmathematik
       Dieses Seminar wird im Rahmen des Studienschwerpunkts Diskrete Strukturen empfohlen.


Zuletzt bearbeitet Sept. 2017