Hauptseminar im Wintersemester 2005

Exakte Algorithmen für NP-schwere Probleme

Kontaktpersonen:

Daniel Mölle (moelle@informatik.rwth-aachen.de)
Stefan Richter (richter@informatik.rwth-aachen.de)
Peter Rossmanith (rossmani@informatik.rwth-aachen.de)

Aktuelles und Material zum Download

Vorbesprechung

Die Vorbesprechung fand in der ersten Sitzung am 17.10.2005 statt.

Einordnung

Theoretische Informatik

Ort und Zeit

Montags, 16:45 Uhr, im Seminarraum des Lehrstuhls I1.

Themenspektrum

Eines der Hauptarbeitsgebiete unseres Lehrgebietes liegt im Design und der Analyse von Algorithmen, die NP-schwere Probleme exakt lösen. Aus diesem Themenkreis sollen besonders wichtige und interessante Meilensteine und vor allem auch eigene Arbeiten im Rahmen eines Seminars beleuchtet werden. Es wird voraussichtlich drei große Themenblöcke geben:

  1. Steiner-Bäume: Sowohl der klassische Algorithmus von Dreyfus-Wagner als auch unsere darauf basierenden neuen Methoden sollen thematisiert werden.
  2. Baumweite, dünne Graphen und intuitive Algorithmen: Ein am Lehrgebiet entwickelter neuartiger Ansatz zur schnellen Lösung vieler Graph- und Erfüllbarkeitsprobleme.
  3. Varianten des Erfüllbarkeitsproblems für boolesche Formeln: unter anderem Schönings Algorithmus für 3SAT und unsere Arbeiten über (Res)MaxExactSAT.

Es zeichnet sich bereits ab, daß sich das Seminar sehr nah an aktueller Forschung orientiert, und auch bewußt einen Einblick in die Arbeit am LuFGTI ermöglichen soll. Daher sind bei außergewöhnlichen Leistungen auch etwa Diplomarbeiten in der Folge denkbar.

Modus

Das Seminar soll über das bloße Anhören von Vorträgen hinausgehen. Wir streben dabei die Vermittlung fortgeschrittener Kulturtechniken wie Präsentation, Moderation, zielgerichteter Gruppenarbeit und Diskussion, Textsatz und schriftlichen Ausdruckes an. Deshalb haben wir folgendes experimentelle Konzept entwickelt, um einer statischen Vortragsreihe entgegenzuwirken:

Wir werden eine Reihe von Themen bearbeiten, die vor allem im Umfang noch offen ist. Dazu wird stets nach Beendigung eines Themas ein Team aus etwa zwei Teilnehmern das nächste Problem in einer mediengestützten Kurzpräsentation vorstellen. Das gleiche Team hat zu dieser Zeit auch bereits ein Handout erstellt, das es den anderen Teilnehmern ermöglichen soll, sich bis zur folgenden Sitzung gründlich auf dieses Thema vorzubereiten. Der erste Vortrag und das erste Handout werden am Ende der Vorbesprechung durch die Veranstalter gegeben.

Eine typische Sitzung wird dann etwa wie folgt verlaufen: Eine Moderatorin wird spontan ernannt. Dieser Moderator führt durch die Veranstaltung. In einer moderierten Diskussion soll schrittweise erreicht werden, daß alle Teilnehmer die Lösung des Problems gemeinsam erarbeiten und verstehen. Das bedeutet insbesondere, daß jeder potentielle Moderator - also jede Teilnehmerin - sich vorher eine sinnvolle Gliederung in Zwischenziele überlegen sollte. Wenn alle überzeugt sind, ein Zwischenziel erreicht zu haben, werden wir eine Studierende auswählen, die das Erreichte in einem Spontanvortrag zusammenfasst. Es ist insgesamt nicht wichtig, wie lange es dauert, ein Thema zu bearbeiten. Falls eine Thematik in einer Sitzung abgeschlossen wird, endet die Veranstaltung mit einem Kurzvortrag zur Vorbereitung auf das nächste Mal, siehe oben.

Die Leistung jedes Teilnehmers wird mit einem benoteten Schein bewertet. In die Bewertung fließen insbesondere die Qualität der Spontanvorträge, der Moderation, der Handouts, der Kurzvorträge und Folien, sowie der Beteiligung am Gruppenprozeß ein. Ein Totalausfall in mindestens einer der Kategorien verhindert eine erfolgreiche Teilnahme. Wir sind uns der experimentellen Natur des Vorgehens bewußt. Sollten sich einzelne Regelungen nicht bewähren, so werden wir gemeinsam Verbesserungen finden.

Voraussetzungen

Interesse an Mathematik, offener Zusammenarbeit und experimentellem Lernen. Bereitschaft und Fähigkeit zur Begeisterung und Selbstmotivation. Von Vorteil sind Vorkenntnisse in algorithmischen Aspekten der theoretischen Informatik.