[FIRM] FIRM vortrag am 30.11.

[Kurt Hornik]

Liebe Kollegen,

Am 30.11. wird Herr Frederik Gierlinger um 09:30 einen Vortrag mit dem
Titel

  Das exakte Überdeckungsproblem und Knuths Dancing-Links-Algorithmus

halten.  Der Vortrag wird im Seminarraum StatMath (UZA 2 Ebene 4) statt
finden.

mlg
-kh

Abstract:

Beispiele für das exakte Überdeckungsproblem sind: Lateinische Quadrate,
orthogonale lateinische Quadrate, Sudokus, Langfordpaare, Skolemfolgen,
n-Damenproblem, Steiner-Systeme, Pentomino-Probleme.  Einige dieser
Probleme gehören zur "Unterhaltungsmathematik", es gibt aber auch
ernsthafte Anwendungen, etwa in der Versuchsplanung oder
Codierungstheorie. Das (allgemeine) Problem kann ganz einfach
beschrieben werden: Gegeben sei eine 0/1-Matrix. Eine Lösung des
Problems ist eine horizontale Teilmatrix, in der jede Spalte die
Spaltensumme 1 hat. Das Problem der exakten Überdeckung (englisch:
exact cover) gehört zu den 21 klassischen NP-vollständigen Problemen,
von denen Richard M. Karp 1972 gezeigt hat, daß sie NP-vollständig sind.

Um ein solches exaktes Überdeckungsproblem zu lösen, kann man im
allgemeinen nichts Besseres tun, als die Menge aller Lösungen baummäßig
zu strukturieren und diesen Baum "depth-first" abzusuchen. Jeder Knoten
des Baumes entspricht einer Teillösung (bisher ausgewählte Zeilen) und
dem dazugehörigen Teilproblem (einer Teilmatrix der ursprünglichen
Problemmatrix mit den "noch übrigen" Spalten und Zeilen). Die
Repräsentation der jeweiligen Teilmatrix ist von entscheidender
Bedeutung für das Laufzeitverhalten des entsprechenden Programms, da
diese beim Ab- und Aufstieg im Baum laufend analysiert und geändert
werden muß.

Dazu hat Knuth im Jahr 2000 die Dancing-Links-Repräsentation konzipiert.
Die Problemmatrix wird dabei durch eine orthogonale Struktur doppelt und
zirkular verketteter Listen dargestellt: Jeder 1-er hat je einen Pointer
zu seinem linken, rechten, oberen und unteren Nachbarn. Damit können die
Updates der Problemmatrix äußerst effizient und sehr elegant
bewerkstelligt werden. Der resultierende Algorithmus für das exakte
Überdeckungsproblem wird DLX genannt, weil Knuth dabei auf seinem
("konventionellen") XCOVER-Algorithmus (kurz Algorithmus X) aus dem Jahr
1994 aufbaut. Die mit der DL-Organisation erzielbaren
Laufzeitverbesserungen sind tatsächlich beeindruckend.