Friedhelm Meyer auf der Heide

Termine

Vorbesprechung

Mittwoch, der 25.10.2000 um 16:00 s.t. im F1.406

Anmeldung

durch Email an mich
sowie Teilnahme an obiger Vorbesprechung

Abgabe der schriftlichen Ausarbeitungen

(8-12 Seiten)
bis 17. Januar 2001

Seminar (S2)

1. und 2. Februar 2001 im
Bildungs-und Seminarzentrum Willebadessen

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

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.  

Themen

• 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, 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.
• 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.
• Das AKS-Netzwerk: Sortieren am Limit
  Sortiernetzwerke sind eine besondere Art vergleichsbasierter paralleler Spezialhardware, die nichts anderes kann als zu sortieren, aber das ungeheuer schnell, jedenfalls erhofft man sich das. Fast 30 Jahre lang vermutete man, daß es nicht möglich sei, ein Sortiernetzwerk für n Zahlen zu entwerfen, das eine optimale Beschleunigung, d.h. eine Sortierzeit von O(log n) erreichen könne, doch drei ungarischen Forschern ist es gelungen, eine solche Konstruktion durchzuführen. In diesem Vortrag soll die vereinfachte Methode von Mike Paterson 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.
• 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.
• 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'.
• Die Probabilistische Methode und ihre Anwendungen
  Wenn wir von einem zufälligen Graphen zeigen können, daß er 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.
• Ersetzt der Computer die Mathematiker?
  Gibt es einen Algorithmus, der beispielsweise die Fermatsche Vermutung entweder beweist oder widerlegt? Genauer: Sind arithmetische Aussagen (mit Quantoren über natürliche Zahlen) entscheidbar? Das ist das zehnte einer berühmte Reihe von Problemen, die David Hilbert Anfang des letzten Jahrhunderts gestellt hat.
  Hier geht es auch um eine Variante des obigen Problems, bei dem die Multiplikation nur mit Konstanten zulässig ist: die Presburger Arithmetik.
• P=NP? Ein linearer Entscheidungsbaum polynomieller Tiefe für KNAPSACK
  KNAPSACK ist ein wohlbekanntes NP-vollständiges Problem, man geht also allgemein davon aus, daß es nicht in polynomieller Zeit lösbar ist. Für lineare Entscheidungsbäume, d.h. Algorithmen, die n relle Zahlen als Eingabe bekommen und nur lineare Operationen (+,-, Multiplikation mit Konstanten) und if-Abfragen ausführen können, wird ein polynomieller Algorithmus für das Rucksackproblem vorgestellt. Diese Bäume liefern jedoch ein nicht-uniformes Modell: für jede Eingabelänge n wird ein neuer Algorithmus (dessen Größe mit n wächst) angegeben.
• P<>NP? Eine untere Schranke über die Tiefe algebraischer Berechnungsbäme für KNAPSACK
  Algebraische Berechnungsbäume stellen ein abstraktes Modell für Algorithmen dar, in denen Eingaben aus n reellen Zahlen bestehen: In einem Rechenschritt dürfen auf Eingaben, Konstanten und vorher berechneten Werte   arithmetische Operationen (+,-,*,/) ausgeführt oder bedingte Sprünge (if-Abfragen) durchgeführt werden. Ben Or benutzt eine sehr schöne Technik, um in diesem Modell untere Laufzeitschranken nachzuweisen. Dieses läßt sich insbesondere auf das Rucksackproblem anwenden.
• Backwards-Analysis in Algorithmischer Geometrie
  
• Open Problems -- leicht zu erklären, schwer zu lösen
  Viele Probleme, gerade aus der Geometrie, lassen sich leicht erklären, ihre Antwort ist jedoch noch immer offen. Die interessantesten sind auf einer eigenen WWW-Seite zusammengefaßt.
• Splay-Trees
  
• Linke Strategien zur Last-Balancierung
  
• 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
  
• 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.
• Wie werde ich Millionär: Beweis der Güte des Consistent Hashing
  Dieses Thema beschäftigt sich mit dem Verteilen von Datenblöcken auf Festplatten. Leighton et al haben einen randomisierten Algorithmus vorgestellt, der Daten sehr gleichmäßig über eine sich ändernde Anzahl von Platten verteilt. Der Beweis der Güte benutzt Chernoff Bounds und einige kleine 'Tricks'.
• 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.
• Das Perzeptron-Konvergenztheorem
  Das Perzeptron ist ein Grundbaustein neuronaler Netze: Übersteigen die an seinen Eingängen anliegenden (gewichteten) Reize einen gewissen Schwellwert, so gibt es seinerseits Reize ab. Durch Training lassen sich seine Gewichte ändern: es kann 'lernen' wie das menschliche Neuron. Hier soll nun untersucht werden, welche Eingangsmuster in endlicher Zeit lernbar sind.
• 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
• 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

Donnerstag, den 1.2.2001

9:30	Ankunft     im	Bildungs-und Seminarzentrum, Alter Markt 5, 34439 Willebadessen
10:00 - 11:00	Anke Helbich	Das 10. Hilbert'sche Problem
11:15 - 12:15	Simon Bicskey	Backwards-Analysis in Computational Geometry   (Anhang)
Mittagspause
14:30 - 15:30	Martina Terbahl	Open Problems -- leicht zu erklären, schwer zu lösen
Kaffee
16:00 - 17:00	Marcin Bienkowski	Lower Bounds For Algebraic Computation Trees For KNAPSACK
17:00 - 18:00	Miroslaw Korzeniowski	A Polynomial Linear Search Algorithm for the n-Dimensional KNAPSACK Problem

Freitag, den 2.2.2001

9:00 - 10:00	Ute Schröfel	Die Probabilistische Methode und ihre Anwendungen
10:07 - 11:07	Stefan Nolting	Das AKS-Netzwerk: Sortieren am Limit
11:15 - 12:15	Stefan Rührup	Consistent Hashing
Mittagspause
14:30 - 15:30	Jörn Mühlencord	Das Perzeptron-Konvergenztheorem

 

Anreise

Bildungs- und Seminarzentrum Willebadessen
Alter Markt 5
D-34439 Willebadessen
05646/9810
mailto:bildungsstaette@agnrw.de
http://www.auslandsgesellschaft.de

 

• mit dem Auto
  über die BAB44 Dortmund-Kassel, Abfahrt Diemelstadt (Richtung Bad Driburg). In Willebadessen finden Sie die Einfahrt direkt neben der Volksbank.
• mit Bus/Bahn:
  Die Buslinie 545 verbindet den Bahnhof Altenbeken direkt mit der Internationalen Bildungsstätte. Ab Paderborn Bahnhof gibt es auch die Buslinie 201.

 

---

Martin Ziegler