Friedhelm Meyer auf der Heide

Termine

Anmeldung und Themenvergabe

22.10.2003 (Mittwoch) um 16:15 im F1.310.

 

Abgabe der schriftlichen Ausarbeitungen

(8-12 Seiten)
bis Montag, 12. Januar 2004

Blockseminar (S2)

 

28.+29. Januar 2004
im Schloß Gehrden bei Brakel/Höxter.

• Diashow
• Schloß
• Kloster
• Dorf
• Umgebung
• Anfahrt

Das nächste Perlen-Seminar findet voraussichtlich im WS04/05 statt.

 

Zeitplan

Beginn am Mittwoch, dem 28.1.2004:

 

9:30	Anreise/Ankunft
10:00	Basil Becker:	"3SUM-hardness "	(Martin Ziegler)
11:15	Karsten Tiemann:	"Fixed-Parameter Komplexität "	(Rolf Wanka)
12:30	Mittagessen, Spatziergang
14:00	Peter Janacik:	"Theorie von Peer-to-Peer Netzwerken: Tapestry "	(Miroslaw Korzeniowski)
15:15	Helmer Krämer:	"Das Periodification Scheme "	(Rolf Wanka)
16:30	Daniel Kuntze:	"Unkomprimierbarkeit "	(Martin Ziegler)
18:00	Abendessen
Donnerstag, 29.1.2004:
8:00	Frühstück, Zimmer räumen
9:15	Eugen Schilke:	"Randomisierung: Komplexitätstheorie und Praxis "	(Martin Ziegler)
10:15	Helene Schilke:	"Aspekt Graph unter orthographischer Projektion "	(Michael Kortenjan)
11:15	Andrea Steinke:	"IP=PSPACE "	(Marcin Bienkowski)
12:30	Mittach
13:30	Evgenija Wetzel:	"Random Knapsack in expected polynomial time "	(Valentina Damerow)
14:30	Abschluß-Kaffee

Kosten (Unterkunft+Verpflegung) voraussichtlich ca. 60 Euro.

Inhalt

In diesem Seminar soll anhand einer Reihe ausgewählter Aufsätze und Lehrbuch-Abschnitte die Schönheit von Problemlösungen aus dem Bereich der Theoretischen Informatik demonstriert werden und daß die Beschäftigung mit raffinierten Beweistechniken, eleganten Argumenten und überraschenden Konstruktionen höchst vergnüglich ist.
Inspiriert wird dieses Seminar durch das Buch ,,Perlen der Theoretischen Informatik`` von Uwe Schöning, in dem er eine Sammlung von Ergebnissen vorstellt, die seiner Meinung nach Highlights der Theoretischen Informatik darstellen.
Natürlich wird die Themenauswahl unseres Seminars durch den Geschmack der Themensteller und ihre Arbeitsgebiete geprägt sein.

Um für etwas Abwechslung zu sorgen, sind hier nur Themen aufgelistet, die im letzten oder vorletzten Jahr nicht vergeben wurden:

 

Themen

• Lernbarkeit und VC-Dimension
  Was ist normal? Bin ich zu dick oder zu dünn? Bin ich zu groß oder zu klein?
  Möchte man herausfinden, wie ein Ottonormalverbraucher aussieht, schaut man sich Maße von normalen Beispielpersonen, die zufällig aus der Menge gegriffen werden. Damit kann man einen Rahmen bestimmen, in den alle normalen Leute hineinfallen. Weil man aber nur einen kleinen Ausschnitt aller normalen Leute kennen lernt, macht man dann Fehler (Also bin ich doch nicht zu dick). Dieser Fehler ist klein, wenn die Gewichtsverteilung und Längenverteilung aller Personen bezüglich eines einfachen kombinatorisches Maßes (mit dem schwierigen Namen Vapnik-Chervonenkis-Dimension) klein ist.
• Mann, ist das flach, Mann: Das Periodification-Scheme
  Sortiernetzwerke haben einen Nachteil, der es oft verbietet, daß man sie tatsächlich in Hardware realisiert: Es ist immer nur ein kleiner Bruchteil aller Einzelkomponenten gleichzeitig aktiv, ja, jede Komponente ist nur ein einzige Mal tätig und wird danach nie wieder benötigt. 1994 wurde ein Verfahren vorgestellt, das jedes Sortiernetzwerk derart umbaut, daß man immer wieder die gleichen drei Schritte wiederholt und trotzdem fast so schnell ist wie das ursprüngliche Netzwerk. Will man nun dieses Verfahren in Hardware realisieren, braucht man nur diese paar Schritte zu in Hardware zu gießen und kann deren Einzelkomponenten immer und immer wieder verwenden. In diesem Vortrag soll dieses Periodification Scheme anhand der Zeitschriften-Version von 2000 vorgestellt werden.
• Phasenübergänge und Zufallsgraphen
  Das Phänomen "Phasenübergang" ist in der Physik wohlbekannt: ein hinreichend großes System von beispielsweise Wasser-Molekülen ändert bei den Temperaturschwellen 0^oC und 100^oC sprungartig (!) seine Eigenschaften. Etwas ähnliches trifft für Zufallsgraphen  G  zu: überschreitet die Kantenwahrscheinlichkeit hier die 'Schwelle' von  logn/n , so ist G fast sicher zusammenhängend, unterhalb fast sicher unzusammenhängend. Man kann sogar beweisen, daß jede Grapheigenschaft, die sich in einer gewissen Sprache der Logik ausdrücken läßt, ein solches 0/1-Gesetz erfüllt.
• IP=PSPACE
  Imagine that you have a program which has to decide some property of the input. Additionally you are allowed to ask questions to some powerful adversary (able to perform any computations), but it always tries to convince you that the input has this property. Assuming that the runtime of your program is polynomial, what is the class of the languages that you can decide? The answer is NP.
  Now we add the posibility to use random number generator. The class of languages that you are now able to decide (with high probability) in polynomial time is called IP (Interactive Proofs). The well-known NON-ISOMORPHISM property, which is believed not to be in NP, belongs to this class. Surprisingly, it appears that IP=PSPACE, i.e. now you have the same power as a Turing machine with polynomially bounded tape length.
• 3SUM-hardness
  Für viele Probleme der algorithmischen Geometrie kennt man keine subquadratischen Lösungen, kann andererseits aber auch keine entsprechende untere Schranke beweisen. Was liegt näher, als, analog zur NP-Vollstädigkeit, "n²-hardness" zu definieren? Aber dann muß man natürlich auch vollständige Probleme identifizieren, sozusagen Pendants zu SAT.
• Unkomprimierbarkeit
  Die Dokumentation von gzip erwähnt, daß in einigen, sehr sehr seltenen Fällen die komprimierte Datei größer sein kann als das Original. Ist ein (verlustfreies!) Kompressionsverfahren überhaupt möglich, das jede Datei echt kleiner macht? Oder gibt es vielmehr redundanzfreie Bitstrings, die sich jeder Komprimierung widersetzen? Versuch' mal, einen anzugeben!
  Lange Zeit schien die Kolmogorov Komplexität eine rein theoretische Größe zu sein. In letzter Zeit lieferte die Incompressibility Method jedoch einige höchst elegante Beweise. Siehe auch das Buch von P. Vitanyi!
• Randomisierung und De-Randomisierung
  Randomisierte Algorithmen bestechen durch ihre konzeptionelle Einfachheit und praktische Anwendbarkeit. Tatsächlich sind zu vielen 'schweren' Problemen nur effiziente randomisierte Lösungen bekannt. Aber ist Randomisierung ECHT mächtiger als Determinismus? Und wie verhält sie sich zum Nichtdeterminismus?
• Theory of P2P-networks (1-3 Themen)
  Peer-to-Peer networks have become very popular in the last few years. They can be used to share files (Napster, Gnutella, Kazaa) but also to share computational power (SETI@home). The definition of a peer-to-peer network says that each of its nodes has equivalent capabilities and responsibilities. This is actually not true for most of the examples - Napster used central servers and Kazaa treats some nodes as supernodes. Such networks have been very well examined in practice and the demands concerning them are well defined. Nowadays also the theory on them is developed.
• Random Knapsack in expected polynomial time
  Das Knapsack Problem ist eines der am häufigsten untersuchten aus dem Gebiet der kombinatorischen Optimierung. Gegeben sind n Güter mit jeweiligen Gewichten, zusätzlich hat jedes Gut noch einen Gewinnwert. Ziel ist es, einen Rucksack mit Gütern zu packen, sodass die Kapazität des Rucksacks nicht vom Gewicht der Güter überschritten wird und zugleich der Gewinn der gepackten Güter maximal wird.
  Dieses Problem ist sowohl von theoretischem als auch praktischem Interesse. Im worst case haben alle bekannten Knapsack Algorithmen eine exponentielle Laufzeit, in praktischem Anwendungen sind diese Algorithmen allerdings sehr viel besser. Daher stellt sich die Frage nach der durchschnittlichen Komplexität der Knapsack Algorithmen.
  Rene Beier und Berthold Vöcking liefern den ersten Beweis, dass zumindest zufällige Instanzen des Knapsack Problems in erwarteter polynomieller Laufzeit gelöst werden können. Diese Arbeit ist im Sommer 2003 auf einer der besten Konferenzen für Theoretische Informatik veröffentlicht worden (STOC). Berhold Vöcking war lange Jahre in Paderborn und hat bei Prof. Meyer auf der Heide promoviert. Heute ist er Professor für Informatik in Dortmund.
• Fixed-Parameter Komplexität
  Fast jedes relevante Problem ist NP-hart. In der Praxis muß es aber trotzdem gelöst werden, und mit geeigneten Heuristiken geht das auch überraschend oft. Die formale Begründung liefert eine worst-case Analyse, bei der man neben n  einen weiteren Parameter betrachtet. So erlaubt beispielsweise k-VertexCover eine Laufzeit von   O((1.29)^k+kn), was für Werte k≤2000 durchaus praktikabel ist. Allgemeiner spricht man von Fixed-Parameter Tractability (FPT) bei Laufzeiten der Form  f(k)+p(n)  mit einem Polynom p(n) und einer beliebigen Funktion f(k).
  Andererseits gibt es Probleme wie k-Clique, die FPT-hart sind, d.h. vermutlich nicht von einem Algorithmus mit obigem Laufzeitverhalten gelöst werden können.
  Siehe auch das Buch "Parametrized Complexity" von Downey und Fellows sowie die Habilitationsschrift von Rolf Niedermeier.
• Aspect Graph unter orthographischer Projektion
  Eine wesentliche Aufgabenstellung in der Computergraphik ist die Erkennung von Sichtbarkeit. Alle qualitativ unterschiedlichen Sichten auf eine Szene können durch den Aspect Graph repräsentiert werden. Betrachterpositionen, die zu Bildern mit gleicher Topologie führen, werden durch einen Knoten zusammengefasst. Die Veränderung von Sichtbarkeit wird durch Kanten in diesem Graph beschrieben. Die Vielzahl unterschiedlicher Ansichten auf eine Szene führt zu einem schnellen Anwachsen der Größe des Aspect Graph. Unter orthographischer Projektion beträgt die Komplextität O(n^2) bei konvexen Szenen und O(n^6) im allgemeinen Fall.
• Sublineare Algorithmen
  Christian Sohler bietet ein eigenes Seminar zu interessanten Aspekten dieses spannenden Themas an!

 

Literatur

• Rahmenrichtlinien für Seminare
• Ratschläge zum Abfassen eines schlechten Referats
• Three Sins of Authors in Computer Science and Math
• Bad Writing Contest
• Help page for English Writing Elements of Style (English)
• Ausgewählte Originalaufsätze bzw. Abschnitte aus Lehrbüchern, sowie
• Uwe Schöning: «Perlen der Theoretischen Informatik», BI Wissenschaftsverlag 1995, 41TVA2403 und 60TVA2411

Dieses Buch gibt es im Semesterapparat in der Bibliothek.

---

Martin Ziegler