Das Seminar findet statt am Do., den 28. Februar, im Hörsaal 2, HG I, Campus Süd, und zwar in der Zeit von 10 bis 17 Uhr (mit Mittagspause). Die Vortragsreihenfolge richtet sich nach der Reihenfolge der Kapitel aus dem Buch...
Wieviele Lottoreihen muß man tippen, damit man garantiert 3 Richtige hat?
Wieviele Teilmengen von {1,...,20} kann man maximal auswählen, so daß keine
Teilmenge einer anderen ist?
Wieviele 0-1-Vektoren der Länge 10 kann man maximal wählen, so daß je
zwei sich in mindestens drei Positionen unterscheiden?
Gegeben eine Menge M von 0-1-Vektoren. Wieviele Bits müssen wir von einem
Vektor kennen, um ihn eindeutig unter den Vektoren aus M
identifizieren zu können?
Viele Probleme in der Theoretischen Informatik lassen sich,
wenn man genau hinschaut, so oder so ähnlich formulieren, also auf
kombinatorische Fragestellungen zurückführen.
(Daß die Resultate auch Anwendungen in der Praktischen Informatik haben,
wie zum Beispiel bei der Konstruktion von fehlerkorrigierenden Systemen
oder beim Testen von logischen Schaltkreisen etc., will ich hier nicht
extra hervorheben.)
In diesem Seminar soll es um solche und ähnliche Fragestellungen gehen,
es wendet sich also an Studenten und Studentinnen, die Spaß haben an
kombinatorischen Fragestellungen. Grundlage
des Seminars ist das 2001 erschienene Buch
"Extremal combinatorics - with applications in computer science"
von Stasys Jukna.
Das Wort "extremal" im Titel des Buchs erklärt sich aus der Tatsache, daß
es (wie auch in den oben genannten Problemen) fast immer um die Frage geht
"Wieviele Objekte brauchen wir *mindestens*...?", es ist also immer eine
*extrem* kleine Menge gesucht.
Die Teilnehmenden am Seminar sollen sich in Absprache mit mir jeweils ein oder
zwei Kapitel aus diesem Buch auswählen und darüber einen Vortrag halten.
Dies ist deshalb gut möglich, weil die Kapitel nur wenig aufeinander aufbauen,
so daß sie fast unabhängig voneinander gelesen werden können.
Ich werde eine Vorbesprechung am Anfang des Wintersemesters anbieten,
das Seminar selbst soll dann in der Zeit nach dem Semester als
Kompaktseminar stattfinden, den genauen Termin können wir in Absprache
festlegen.
Interessenten können sich natürlich auch vorher
schon bei mir per email melden:
hofmeist@Ls2.cs.uni-dortmund.de