Kombinatorische Methoden der Informatik

Der erste Themenkomplex der Vorlesung ist die Ramsey-Theorie:

Ihnen wird wahrscheinlich folgendes "Puzzle Problem" bekannt sein:

 

 

"Auf einer Party mit sechs Personen gibt es immer drei, die sich paarweise kennen,
oder drei, die sich paarweise nicht kennen."

 

Die nach Ramsey benannte Theorie behandelt also Aussagen der Art

 

"Ist eine mathematische Struktur genügend groß, so existiert in ihr eine kleinere spezielle Unterstruktur."

 

Ergebnisse aus der Ramsey-Theorie kann man benutzen, um untere Schranken für die Berechnungskomplexität von Problemen herzuleiten. Dies wird an einigen Beispielen vorgestellt.

 

Ein weiterer Themenkomplex ist die Probabilistische Methode. Hier geht es um
Beweistechniken, mit denen man die Existenz einer "Nadel im Heuhaufen" zeigen kann. Mit der Probabilistischen Methode lassen sich effiziente randomisierte Algorithmen entwickeln.

 

Der letzte Themenkomplex behandelt Explizite Konstruktionen. Wir wollen die Objekte, deren Existenz wir bewiesen haben, auch mit möglichst wenig Resourcen, d.h. effizient, konstruieren.

Einige der dazu entwickelten Techniken (Theorie der quasizufälligen und
Expander-Graphen) mitsamt den wichtigen praktischen Anwendungen werden in der Vorlesung behandelt.