Allgemeines

Veranstaltungsnummer  
Veranstalter Prof. Dr. Thomas Schwentick
Klassifikation Seminar
Semester Wintersemester 2019/20
Ort und Zeit  
Vorbesprechung 12.9.2019 10:15 Uhr
(eine spätere Themenvergabe ist nach Absprache möglich)

Inhalt

Das Seminar befasst sich mit fortgeschrittenen Themen in meinen Lehr- und Forschungsgebieten .

Themen sind aus (mindestens) den folgenden drei Gebieten möglich:

- Datenbanktheorie
- Komplexitätstheorie
- Logik und Komplexität

Insbesondere sind Vorträge zum Thema Algorithmen zur Aufzählung von Anfrageergebnissen vorgesehen.

Aufgrund der Heterogenität sollen die jeweils Vorträge eine großzügige Einführung ins Thema bieten, bevor dann eine speziellere Fragestellung vertieft wird.

Die Vorträge sollen deshalb wie eine 90-minütige Vorlesung konzipiert werden, quasi im KoMTI-Stil. 

Die Seminararbeit soll als  dazugehöriges Skript im Umfang von 10 Seiten konzipiert sein.

Es wird zusätzlich weitere Vorträge aus der Arbeitsgruppe LogiDAC geben.

Falls Sie prinzipielles Interesse an diesem Seminar haben, wäre ich für eine baldige, kurze Nachricht dankbar.

 

Allgemeines

Veranstaltungsnummer  
Veranstalter Prof. Dr. Thomas Schwentick
Klassifikation Proseminar
Semester Sommersemester 2017
Ort und Zeit  
Vorbesprechung wird noch angekündigt
Querverbindungen DAP 2, GTI
Voraussetzungen DAP 2

 

Inhalt

In der Algorithmentheorie wird der Aufwand eines Algorithmus üblicherweise (asymptotisch) im Verhältnis zur Größe seiner Eingaben ausgedrückt. Bei Graphenalgorithmen oft auch in der Anzahl der Knoten des Graphen. Für viele algorithmische Probleme sind in dieser Betrachtungsweise nur Algorithmen mit exponentiellem Zeitaufwand bekannt.

Ein Beispiel hierfür ist das Vertex Cover Problem: Gegeben ein Graph G und eine Zahl k, fragt es, ob es eine Menge M von k Knoten gibt, so dass jede Kante des Graphen einen Knoten in M hat. Interessanterweise gibt es jedoch einen sehr simplen Algorithmus, dessen Aufwand O(n 2^k) ist, wobei n die Anzahl der Knoten des Eingabegraphen ist. Intuitiv ist der Aufwand dieses Algorithmus also "nur" schlecht in k, aber nicht in n. Anders gesagt: für Eingaben mit "kleinem" k lässt sich das Problem effizient lösen.

Solche Parametrisierungen gibt es auch für eine Reihe anderer algorithmischer Probleme. Entsprechende Algorithmen dieser Art wollen wir in dem Proseminar betrachten.

Die Vortragsthemen basieren zum Teil auf dem Buch Invitation to Fixed-Parameter Algorithms von Rolf Niedermeier, zum Teil auf dem Buch Fundamentals of Parameterized Complexity von Rodney G. Downey und Michael R. Fellows. Die dem Buch von Herrn Niedermeier zugrunde liegende Habilitationsschrift finden Sie hier: http://theinf1.informatik.uni-jena.de/~niedermr/publications.html.

Darüber können den Vorträgen weitere Bücher und Originalarbeiten zugrunde liegen.