Kombinatorische Algorithmen -- Wintersemester 2017/18

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 (JH Bremsdorfer Mühle) durchgeführt. Februar 2-4, 2018.

Für die Blitzvorträge treffen wir uns am 24. Nov. 2017 um 10Uhr.

Probevorträge vor dem 20. Januar 2018!

Themen konkret

Einführung; Kapitel 1,2,3,8 aus Wilf:Update
Bäume; Sec 4.6 (Seiten 73-86) aus Ruskey:Comb.Gen.
Poset Probleme; Sec 4.12, 5.10, 5.11 (Seiten 98-103+163-174) aus Ruskey:Comb.Gen.
Hamiltonicity in Graphs; Kap 6 (Seiten 189-200) aus Ruskey:Comb.Gen.
DeBruijn Cycles und relatives; Kap 7 (Seiten 207-229) aus Ruskey:Comb.Gen.
Determinanten und Pfaffsche ohne Division (Urbaniak)
Optimieren und LP mit Kombinatorik (Gaertner, Welzl)
Entropy Compression (Tao)
k-SAT Algorithms (Moser, Scheder)
Submodular Function Optimization (Iwata, Orlin)
Subexp alg for counting triangulations (Marx, Milzow)

Die PDFs befinden sich in diesem Verzeichnis.

Thema allgemein

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:

Donald E. Knuth, The Art of Computer Programming, Volume 4A: Combinatorial Algorithms: Part 1. Combinatorial Searching. Addison-Wesley (2011)
Dennis Stanton und Dennis White, Constructive Combinatorics. Springer (1986)
Donald L. Kreher und Douglas R. Stinson, Combinatorial Algorithms: Generation, Enumeration, and Search. CRC Press (1999)
Frank Ruskey, Combinatorial Generation. unpublished draft (2003)
Herbert S. Wilf, Combinatorial Algorithms: An Update. SIAM (1989)

Zielgruppe:

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

Zuletzt bearbeitet Sept. 2017