Logik in der Informatik Prof. Dr. Martin Grohe

Achtung:

Zeit und Raum haben sich geändert

Dozenten

Dr. Isolde Adler und Dipl. Inf. Marc Thurley

Einführung

Faszinierend an der Matroidtheorie ist unter anderem, dass sie die Betrachtung verschiedenartiger, auf den ersten Blick nicht nah verwandter Objekte unter einem gemeinsamen, algebraisch-kombinatorischen Blickwinkel ermöglicht. Ein Matroid ist eine Struktur, die das "Wesentliche" des Konzepts der linearen Unabhängigkeit in Vektorräsumen erfasst. Matroide lassen sich aber auch als diejenigen Strukuren charakterisieren, auf denen der Greedy-Algorithmus immer optimale Lösungen liefert.

In diesem Seminar werden wir uns die Grundbegriffe und wichtigen Konzepte der Matroidtheorie anhand von James Oxleys Einführung "What is a matroid?" erarbeiten. Mit diesem Wissen werden wir uns schließlich aktuellen Forschungsthemen zuwenden.

Voraussetzungen: Grundkenntnisse über Vektorräume und Graphen.

Zeit und Raum

Freitags 13-15 im Schrödinger Zentrum (Rudower Chaussee 26), Raum 1'308.

Literatur

James Oxley, What is a matroid?

James Oxley, Matroid Theory, Oxford University Press; 1992