Friedhelm Meyer auf der Heide

Termine

Inhalt

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

Blockseminar

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

Beginn am Donnerstag, dem 6.2.2003:

9:30	Anreise/Ankunft
10:00	Tobias Tscheuschner	Primzahltest in Polynomialzeit	(Martin Otto)
11:00	Kaffeepause
11:30	Sabine Michels	Das Meßbecher-Problem	(Martin Ziegler)
12:30	Mittagessen+Spaziergang
14:00	Michael Hußmann	Daten, Daten, Daten. Und immer an den Zugriff denken!	(Kay Salzwedel)
15:00	Martin Hirsch	Wahlprognosen aus Nachbarschafts-Umfragen	(Martin Ziegler)
16:00	Kaffee+Kuchen
16:30	Martin Ozimek	VC-Dimension und ε-Netze	(Valentina Damerow)
17:30	Socializing
18:00	Abendessen

Freitag, der 7.2.2003:

8:15	Frühstück (mit Harry?)
9:00	Volker Rödig	Kann ein Programm sich selbst ausgeben?	(Christian Schindelhauer)
10:00	Kaffeepause
10:15	Christian Soltenborn	Zur Beweisbarkeit von "P=NP"	(Martin Ziegler)
11:15	Kaffeepause
11:30	Yvonne Bleischwitz	Zwei  'schwere' Computerspiele	(Martin Ziegler)
12:30	Mittagessen
13:30	Nicolas Cuntz	Effiziente Simulation mit Hilfe eines verteilten Zählers	(Matthias Fischer)
14:30	Alexander Lohrmann	Pebble Game	(Harald Räcke)
15:30	Abschlußfoto, Kaffee+Kuchen
16:00	Abreise

Kosten (Unterkunft+Verpflegung) ca. 60 Euro.

Themen

• Das Meßbecher-Problem
  In dem Film "Stirb Langsam - jetzt erst recht" muß der Hauptdarsteller zur Entschärfung einer Bombe vier Liter Wasser abmessen, hat dazu aber nur einen 3l- und einen 5l-Eimer zur Verfügung. Kann er das schaffen?
  Allgemeiner seien n Meßbecher gegeben mit Kapazitäten c₁,...,c_n; kann man damit Flüssigkeit der Menge x abmessen? Und, falls ja, mit wie vielen Operationen?
  Hiermit beschäftigt sich der Artikel "Measuring with jugs", pp.259-270 in der TCS 282 (2002) Special Edition FUN With Algorithms.
• Wahlprognosen aus Nachbarschafts-Umfragen
  Ist dieses Phänomen typisch für Paderborn? Alle Nachbarn und Bekannten schwören Stein und Bein, keinesfalls CDU-Anhänger zu sein; aber am 22.9. erringt sie im Landkreis wie jedesmal eine satte absolute Mehrheit.
  Haben die Befragten gelogen? Kann man Umfragen überhaupt trauen? Oder müssen für repräsentative Stichproben auch die Nachbarn der Nachbarn (der Nachbarn) mit einbezogen werden?
  Mit solchen Fragen beschäftigt sich der Übersichtsartikel "Local majorities, coalitions and monopolies in graphs" von David Peleg, pp.231-257 in TCS 282 (2002) Special Edition FUN with Algorithms. Ziel des Vortrags ist eine verständliche Darstellung der Ergebnisse, nicht der Beweise.
• Primzahltests
  Wie prüft man am effizientesten, ob eine gegebene Zahl nur durch sich selbst und durch 1 teilbar ist? Der wohl praktischste Algorithmus hierfür stammt von Rabin und ist randomisiert. Erst kürzlich (August'2002) wurde ein deterministischer Test mit garantiert polynomieller worst-case Laufzeit gefunden!
• Schwierigkeitsgrad einiger Computerspiele
  Minesweeper liegt jedem Windows-System mit bei. Du verlierst dabei oft? Und bei Sokoban kommst Du auch nicht weit? Keine Sorge: Mittels Komplexitätstheorie kann man formal beweisen, daß beide Spiele tatsächlich 'sehr schwer' sind.
• Warum ist P<>NP so schwer zu entscheiden?
  1 000 000 US-Dollar erhält, wer das berühmte Problem P<^?>NP löst; und dennoch widersetzt es sich nach wie vor der Entscheidung.
  Gödels berühmter Unvollständigkeitssatz besagt, daß es logische Aussagen gibt, die weder beweisbar noch durch ein Gegenbeispiel widerlegbar sind. Gehört das NP-Problem vielleicht dazu?
  Fast alle heute bekannten Beweise über Turing-Komplexitäten sind relativierbar; das heißt, sie funktionieren auch für Orakel-Turingmaschinen. Andererseits zeigten Baker,Gill,Solovay, daß eben solche Beweise nicht zur Entscheidung des NP-Problems dienen können.
  Nun sind Turingmaschinen ein bekanntermaßen unhandliches Rechenmodell. Deshalb hat Valiant davon völlig unabhängige, rein algebraische Formulierungen von P und NP vorgeschlagen und untersucht.
  Oder lassen NP-vollständige Probleme sich eventuell doch in Polynomialzeit lösen?
• 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.
• VC-Dimension und Epsilon-Netze in der Algorithmischen Geometrie
  Divide-and-Conquer ist ein sehr mächtiges Werkzeug, um Algorithmen mit logarithmischer Laufzeit zu entwickeln. Aber wann kann man es anwenden, d.h. die Anzahl der möglichen Ausgaben in jedem Schritt um einen konstanten Faktor verringern? In der Algorithmischen Geometrie haben sich hierbei Epsilon-Netze sehr bewährt. Es war ein wichtiges Ergebnis von D. Haussler und Emo Welzl, dass konstant große Epsilon-Netze existieren, sofern die VC-Dimension endlich ist. Der Beweis beruht auf der Probabilistischen Methode.
• Kann ein Programm sich selbst ausgeben?
  Genauer gesagt lautet die Frage: Kann ein kompiliertes Programm ohne Dateizugriff seinen eigenen Quelltext ausgeben? Ihn als Stringkonstante zu speichern, löst das Problem offenbar nicht. Daß es manchmal dennoch möglich ist, belegen Beispiele. Tatsächlich geht dies sogar immer: Dies besagt das bzw. folgt aus dem "Fixpunktsatz der Rekursionstheorie". Eigentlich ist es ganz einfach, aber beim Nachdenken darüber bekommt man leicht einen Knoten im Hirn.
• Hypercubes mit eindeutigen Senken
  Der n-dimensionale Hypercube hat 2ⁿ Knoten zu jeweils Grad n und insgesamt n2^n-1 Kanten; diese seien im folgenden orientiert. Eine Senke ist ein Knoten, auf den alle seine n Kanten zulaufen. Eine Unique Sink Orientation (USO) ist eine Orientierung der Hypercube-Kanten derart, daß der Würfel, ebenso wie jeder seiner niedrig-dimensionalen Unterwürfel, eine und nur eine Senke hat. Ziel ist es, für eine beliebige gegebene USO die (eindeutige) Senke zu finden mit Abfragen der folgenden Art:
  Anfrage: ein Knoten,     Ausgabe: die Richtungen seiner n Kanten.
  Wie viele solche Abfragen sind nötig, um in jeder beliebigen USO des n-dimensionalen Hypercubes die eindeutige Senke zu finden? Dieses Problem steht, wie Friedhelm Meyer auf der Heide und Emo Welzl zeigten, in engem Zusammenhang mit der Komplexität gewisser Simplex-Algorithmen. In dem Vortrag sollen zudem verschiedene Strategien dargestellt werden, die mit immer weniger Abfragen die Senke finden und so lyrische
• 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.
• Branching-Programme mit beschr„nkter Breite
  Das Branching Programm ist ein Modell für die Berechnung Boolescher Funktionen. Polynomiell-große Branching Programme könnnen genau LOGSPACE entscheiden. Die Frage nach der Mächtigkeit von Branching Programmen, die gleichzeitig polynomiell-groß und beschränkt breit sind, führte zu einem überraschenden Ergebnis.
• Polynomialzeitalgorithmen für SAT
  Die Erfüllbarkeit einer KNF-Formel zu entscheiden oder, diese vorausgesetzt, eine erfüllende Belegung zu finden, ist NP-vollständig. Diese Erkenntnis hilft in der Praxis jedoch wenig, wenn ein solches Problem konkret gelöst werden muß. Die Literatur beweist für zahlreiche Heuristiken, daß sie zumindest 'im Durchschnitt' gut sind. Aber selbst bei worst-case Laufzeiten im superpolynomiellen Bereich gibt es große Unterschiede zwischen beispielsweise  O(2ⁿ)  und  O(n^{log n}) . Man kann sogar ziemlich genau charakterisieren, welche Arten von SAT-Instanzen 'schwer' und welche 'leicht' sind.
• Unkomprimierbarkeit
  Lange Zeit schien die Kolmogorov Komplexität eine rein theoretische Größe zu sein. Was kann es auch nützen zu wissen, daß 'viele' Strings unkomprimierbar sind, wenn man doch keinen davon konkret hinschreiben kann? In letzter Zeit lieferte die Incompressibility Method jedoch einige höchst elegante Beweise für Untere Schranken. Beispielsweise braucht eine 1-Band Turingmaschine zur Erkennung der Sprache {aⁿbⁿ:n=1,2,3,...} Laufzeit Omega(n log n),   für {w#^|w|w:w} sogar Omega(n²).
  Ganz neu sind Untere Schranken für erwartete Laufzeiten, da diese sich bislang meist einer Analyse widersetzten. So konnte zum Beispiel ein entsprechendes offenes Problem von D. Knuth zum Thema shellsort endlich gelöst werden. Andere Anwendungen betreffen Heilbron's Problem aus dem Bereich der kombinatorischen Geometrie. Siehe auch das Buch von P. Vitanyi!
• Dominos und logische Entscheidungsprobleme
  Die Diagonalsprache und das Halteproblem sind bekanntlich unentscheidbar. Hier soll nun ein weiteres Beispiel vorgestellt werden: Die Überdeckbarkeit der Ebene mit einer gegebenen Menge von Dominotypen. Verglichen mit den ersten beiden, ist dieses Problem von geradezu praktischer Relevanz.
• Die Probabilistische Methode und ihre Anwendungen
  Wenn wir von einem zuf„lligen Graphen zeigen k÷nnen, da˜ es mit positiver Wahrscheinlichkeit eine Eigenschaft E hat, dann ist damit auch klar, da˜ es Graphen mit dieser Eigenschaft gibt.
  So trivial diese Idee des ber�hmten ungarischen Mathematikers Paul Erd÷s scheinen mag, als so m„chtig hat sie sich erwiesen f�r (nicht-konstruktive) kombinatorische Existenzbeweise: zum Beispiel von Expandern, epsilon-Netzen, (Hyper-)Graph F„rbungen, ja sogar zur (nicht-uniformen) Derandomisierung taugt Randomisierung.
• Probabilistische Konstruktionen und Universal Hashing
  Mittels Randomisierung lassen sich viele Probleme eleganter und vermutlich auch effizienter lösen als deterministisch. Solche Algorithmen erwarten als 'Orakel' eine Folge von Münzwürfen: polynomiell viele unabhängige Zufallsbits, also Elemente eines exponentiell großen Zufallsraums. In manchen Fällen genügt jedoch die paarweise (oder auch: k-fache) Unabhängigkeit. Diese lassen sich zu einem deterministischen Polynomialzeit-Algorithmus 'de-randomisieren'.
• Pebbles: Ein Spiel mit Murmeln und seine Anwendungen
  Bei Pebbles handelt es sich um ein Spiel auf gerichteten Graphen mit einfachen Regeln: Man darf dann und nur dann eine Murmel auf einen Knoten legen, wenn auf alle eingehenden Kanten bereits eine liegt. Diese können hernach recycled werden.
  Wie viele Murmeln braucht man, um den Zielknoten des Graphen zu markieren? Wie viele Schritte sind hierzu notwendig?
  Die Beantwortung dieser Fragen hat überraschende Konsequenzen für den Speicherplatzbedarf von Programmen.
• Warum VMware effizient Windows und Linux simuliert -- Die theoretischen Grundlagen von VMware
  VMware ist eine hocheffiziente Software, die einen PC auf einem PC simuliert. Damit ist es möglich, auf einem Linux-PC in einem eigenen Prozeß bzw. Fenster einen Windows-PC zu simulieren (ebenso umgekehrt). Grundsätzlich stellt VMware auf dem  Hostbetriebssystem eines PCs eine vollwertige Simulation eines PCs bereit, auf dem ein beliebiges Gastbetriebssystem läuft. Dieses geht kurioserweise so weit, daß auf dem simulierten PC sogar BIOS Updates eines virtuellen Flashroms durchgeführt werden. Die theoretische Grundlage einer solchen Simulation beantwortet die Frage, ob eine Simulation ohne großen Effizienzverlust möglich ist. Die Simulation einer Maschine auf einer anderen ist relativ einfach und taucht als Grundlage in Komplexitätsvorlesungen auf. Interessanterweise löst ein solcher Simulatior nicht das Grundproblem von VMware. Der Host PC muß eine Kontrolle über die Rechenschritte des simulierten Gastes haben, damit beispielsweise bei I/O kritischen Abschnitten jederzeit die entsprechende Hardware vorgetäuscht werden kann. Erreichbar ist das durch die schrittweise Abarbeitung der Befehle. Dieses ist aus Effizienzgründen  zu teuer. Wünschenswert ist die Simulation einer festen Anzahl  von k Schritten.  Das entsprechende theoretische Problem gestaltet sich schwierig, war lange Zeit offen und wurde 1982 durch Fürer gelöst. Die Lösung mit Hilfe eines distributiven Zählers stellt eine sehr schöne,  leicht einsichtige Grundidee dar. (Als Folge dieses Satzes konnte auch die enge Zeithierarchie gezeigt werden.) Im Seminar soll die Idee und Beweisführung vorgestellt werden, sowie die Frage geklärt werden, in welchen Punkten die Lösung von VMware sich von dem Modell Fürers unterscheidet.
• Daten, Daten, Daten. Und immer an den Zugriff denken
  Daten sind das Kernst�ck von Berechnungen. Gro˜e Datenmengen sind heute keine Seltenheit mehr und verlangen nach einem effizienten Zugriff. Daher versuchen externe Algorithmen die Anzahl der I/O-Operationen zu minimieren. Als besonders schwierig hat sich dabei die Breitensuche erwiesen, da die Knoten nicht immer im Block zugegriffen werden k÷nnen. Vor Kurzem wurde aber eine interessante Datenstruktur entwickelt, die dieses Problem l÷st. Diese Datenstruktur soll bei diesem Thema vorgestellt werden.
• Splay-Bäume
  Eine der wohl bekanntesten Datenstrukturen in der Informatik ist der Bin„rbaum. Bin„rb„ume dienen unter anderem dazu, das sogenannte W÷rterbuchproblem zu l÷sen. D.h., man kann auf Datens„tze mit Hilfe von Schl�sseln zugreifen, neue Datens„tze einf�gen und bereits eingef�gte Daten l÷schen. Bekannte Varianten balanzierter Bin„rb„ume sind z.B. AVL-B„ume und Rot-Schwarz-B„ume. Eine weitere M÷glichkeit Bin„rb„ume zu implementieren sind die sogenannten Splay B„ume. Es handelt sich dabei um Bin„rb„ume, die eine gute amortisierte (durchschnittliche) Zugriffszeit garantieren und die mit Hilfe der Splay Operation implementiert werden. Diese Operation rotiert das aktuelle Element an die Wurzel. Neben den Standard Operationen unterst�tzen Splay B„ume auch Split und Join Operationen und sind im statischen Fall asymptotisch optimal.
• Alles �ber Routing in Hypercubes
  Der Hypercube ist eine sehr populäre Verbindungstopologie für Computernetzwerke. Das Routen von Permutationen zwischen den einzelnen Knoten dieses Netzwerks benötigt sehr viel Zeit wenn man ein deterministisches Modell zu Grunde legt. Wenn man aber Randomisierung erlaubt, wird plötzlich alles besser.
• Das Growing-Rank Routing-Protokol
  
• Raus bist Du noch lange nicht: Caching in Networks
  Dieses Thema besch„ftigt sich mit der Datenverwaltung in Netzwerken. Dabei reicht es nicht, einfach f�r den Speicher eines Computers im Netzwerk eine Paging-Strategie einzusetzen, da z.B. beim L÷schen von Objekten ber�cksichtigt werden mu˜, da˜ niemals die letzte Kopie eines Objektes gel÷scht werden darf.
• Buffer-Trees: Aus alt mach neu
  (a,b)-Bäume sind eine gut erforschte Struktur der Informatik und dienen als Grundlage der Buffer-Trees. Jeder Knoten im Baum wird dabei mit einem Puffer bestimmter Größe erweitert. Im Bereich der Externen Algorithmen kann man mit diesen Strukturen zahlreiche Probleme lösen. In Vortrag soll diese Struktur vorgestellt und ihre günstigen Eigenschaften für Externe Algorithmen aufgezeigt werden.

Literatur

• Rahmenrichtlinien für Seminare
• Ratschläge zum Abfassen eines schlechten Referats
• Three Sins of Authors in Computer Science and Math
• 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.