Prüfung

Für Seminare können Leistungsnachweise
gemäß Lehramts-Studienordnung sowie Diplom-
Prüfungsordnungen 2 und 3 vergeben werden.
Bei Studierenden nach DPO4 entspricht das
Seminar einem Punkt im Bereich MUA.

Inhalt

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

Themen

• 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ß und wie es dennoch möglich ist, besagt das "Recursion Theorem". 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 Namen tragen wie "Seven Steps to Heaven" oder "Schiffsschaukel".
• Proofs from The Book
  Der berühmte ungarische Kombinatoriker Paul Erdös sprach gerne über Das Buch, in welchem nämlich Gott die ultimativen Beweise mathematischer Theoreme aufbewahrt: "Man muß nicht an Gott glauben, aber als Mathematiker sollte man an Das Buch glauben." Einige dieser Beweise von wirklich verblüffender Einfachheit und Eleganz (zumal wenn sie alte offene Probleme lösen), betreffen beispielsweise den Heiratssatz, Cayley's Anzahl beschrifteter Bäume, den 5-Färbbarkeits-Satz, die Extremalität von Turan-Graphen, die Null-Fehler Kapazität gewisser Übertragungs-Kanäle und und und...
• 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?
• Mathematisches Programmieren: Simplex-Algorithmus, smooth Analysis, Ellipsoid-Methode, interior-Point-Method, LPtype-Problems, Property Testing
  Gegeben eine nxd Matrix A und den n-Vektor b. Entscheide, ob das Ungleichungssystem       A*x<=b       lösbar ist. Äquivalent: Entscheide für n orientierte Hyperebenen im d-dimensionalen Raum, ob der durch sie definierte Polyeder P nichtleer ist.
  Falls nur ganzzahlige Lösungen x zulässig sind -- äquivalent: P geschnitten mit Z^d sei nichtleer -- ist dies das bekanntermaßen NP-harte Problem Integer Linear Program (ILP, nicht zu verwechseln mit NLP). Ohne diese Einschränkung ist dieses Lineare Programmieren (LP) äquivalent zum Problem der Konvexen Optimierung, das beispielsweise in der Wirtschaftswissenschaft ständig auftaucht. Dort hat sich der bekannte Simplex Algorithmus als effizientes Lösungsverfahren etabliert. Seine worst-case Laufzeit wurde von V.Klee untersucht, über die erwartete Laufzeit randomisierter Varianten ist jedoch fast gar nicht bekannt.
  Einen Durchbruch brachte die sogenannte Ellipsoid Methode, die sich teilweise auch auf Quadratisches Programmieren anwenden läßt. In eine andere Richtung weist der neue Algorithmus von Gärtner und Welzl für LPtype problems. Und schließlich kann man das Problem abschwächen, die Verletzung eines kleinen Bruchteils der Constraints erlauben. Alles in allem ein sehr interessantes Gebiet zwischen Geometrie, Algorithmik und Stochastik.
• 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.
• The Incompressibility Method
  Lange Zeit schien die Kolmogorov Komplexität eine rein theoretische Größe zu sein. In letzter Zeit lieferte sie 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 in diesem Jahr endlich gelöst werden. Andere Anwendungen betreffen Heilbron's Problem aus dem Bereich der kombinatorischen Geometrie. Siehe auch das Buch von P. Vitanyi!
• Der NP-Vollständigkeit trotzen: Arora's PTAS für das Euklische TSP
  Kaum ein NP-vollständiges Problem ist so populär wie das Traveling Salesperson Problem, liebevoll TSP genannt. Da es auch auf gewöhnlichen, d.h. Euklidischen Landkarten NP-vollständig ist, bleibt einem kaum etwas anderes übrig, als sich mit Näherungslösungen zufriedenzugeben. Ein großes Ahh und Ohh ging durch die Fachwelt, als S. Arora 1996 auf einer Tagung einen Approximationsalgorithmus vorstellte, der beliebig nah an eine optimale Rundreise herankommen kann und trotzdem bloß ploynomielle Laufzeit hat. In diesem Vortrag soll Aroras Algorithmus aus der polierten Zeitschriftenversion von 1998 vorgestellt werden.
• 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.
• 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, e-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.
• Splay-Trees
  
• 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.
• Ene-meme-muh und raus bist Du: Online Paging
  Üblicherweise ist ein kleiner Teil des Speichers eines Computers ein sehr schneller Cache. Dieses Thema beschäftigt sich mit Paging-Strategien, die jeweils entscheiden, welches Objekt aus dem Cache verdrängt werden soll, wenn ein neues Objekt in den Cache geladen wird.
• 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.
• Pebbles: Ein Spiel mit Murmeln und seine Anwendungen
  Bei Pebbles handelt es sich um ein Spiel auf Graphen mit einfachen Regeln aber überraschenden 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.
• Algorithmisches Lernen
  
• 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
• 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.

Zeitplan

Freitag, den 25.1.2002

7:00 - 8:00	Aktivitäten	(*)
8:00 - 9:00	Frühstück
9:00 - 10:00	Markus Oberließen	Aroras PTAS für das Euklidische TSP
10:00 - 11:00	Eduard Wiebe	Markov-Ketten Monte-Carlo Methode
11:00 - 12:00	Peter Horn	Competitive Paging Algorithms
12:00 - 13:00	Mittagessen
13:00 - 14:00	Aktivitäten	(*)
14:00 - 15:00	Tatjana Voth	Mathematisches Programmieren: Simplex-Algorithmus und Ellipsoid-Methode
15:00 - 16:00	Valentina Damerow	Smoothed Analysis of the Simplex Algorithm