Friedhelm Meyer auf der Heide

Termine

Anmeldung und Themenvergabe

war am 27. Oktober 2004  16h15  im  F1.310
mit dem unten aufgeführten Ergebnis.

 

Abgabe der schriftlichen Ausarbeitungen

(8-12 Seiten)
bis 16. Januar 2005

Blockseminar (S2)

 

Mittwochnachmittag, 26. Januar 2005 im F1.110;

Mittwoch und Donnerstag, 2.+3. Februar 2005
im Schloß Gehrden bei Brakel/Höxter.

• Diashow
• Schloß
• Kloster
• Umgebung
• Anfahrt: Schloßstr. 6, 33034 Brakel (Gehrden)

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

Bewertung

als ein MuA-Punkt im dritten Abschnitt (Master-Studiengang) bzw. Hauptstudium (DPO4).

Zeitplan

Mittwoch, dem 2.2.2005 in Schloß Gehrden:

9h30	Ankunft
10h00	Dennis Hannwacker	(Christian Schindelhauer)	"Graphenfärbung in erwartet konstanter Zeit"
11h00	Frank Nillies	(Christian Schindelhauer)	"A (fairly) simple Circuit that (usually) Sorts"
12h00	Mittach
14h00	Özkurt Oguzhan	(Martin Ziegler)	"Abgeschlossenheit von Büchi-Automaten unter Komplement"
15h00	Andre Höing	(Bettina Rehberg)	"Das AKS-Netzwerk: Sortieren in O(log N)"
16h00	Tobias Bräutigam	(Klaus Volbert)	"Obere und untere Schranken beim Broadcasting in Funknetzwerken"

 
Donnerstag, dem 3.2.2005 in Schloß Gehrden:

9h00	Senay Kaynar	(Valentina Damerow)	"Umweg-Faktor ebener geometrischer Wegesysteme"
10h00	Tim Süß	(Gereon Frahling)	"Aroras PTAS für das euklidische TSP"
11h00	Jürgen Brinkmann	(Miroslaw Korzeniowski)	"Skip Graphen"
12h00	Mittach/Ende

Inhalt

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

Themen

• Computer programmieren sich selbst
  Ob die Olivanova Model Execution Maschine die angekündigten Erwartungen erfüllt, vermag ich nicht zu sagen. Theoretisch jedoch hat Marcus Hutter im Jahr 2000 tatsächlich einen Algorithmus präsentiert, der beweisbar jedes Problem bei Eingabe seiner funktionalen Spezifikation löst. Darüber hinaus ist sein HSEARCH, asymptotisch höchstens um einen konstanten Faktor langsamer, als jeder andere Algorithmus für das eingegebene Problem. Unter schwachen Voraussetzungen kann man sogar Faktor 5 erreichen!
• Eine Komplexitätstheorie der Adventure-Spiele
  Zu den Adventures gehören so bekannte Spiele wie Monkey Island, die Sierra-Serien Space Quest, Police Quest und King's Quest sowie Leisure Suit Larry aber auch der C64-Klassiker The Dallas Quest oder /usr/games/adventure unter Unix. Von Brauer, Holzer, König und Schwoon stammt eine sehr nette Klassifikation solcher Spiele. Sie illustriert den sonst vielleicht etwas trockenen Stoff "Formale Sprachen/Chomsky-Hierarchie" auf unterhaltsame Weise und impliziert Ergebnisse über die algorithmische Lösbarkeit solcher Adventures.
• C++ Parser sind universell
  Wie alle praktisch handhabbaren Programmiersprachen ist auch C++ kontextfrei, läßt sich also mit Aufwand O(n³) erkennen; allerdings unter Außerachtlassung von type-checking. Ein korrektes C++ Programm unter Berücksichtigung von type-checking zu erkennen, ist hingegen Turing-vollständig: überraschenderweise konnten Böhme und Manthey aus Lübeck zeigen, daß sich bereits beim Kompilieren (!) jede partiell-rekursive Funktion berechnen läßt.
• Büchi-Automaten sind abgeschlossen unter Komplement
  Daß die von nichtdeterministische endlichen Automaten (NEAs) akzeptierte Sprachklasse abgeschlossen ist unter Komplement, zeigt man üblicherweise, indem man den NEA in einen äquivalenten DEA umwandelt. Für Sprachen unendlicher Wörter (sog. ω-reguläre Sprachen) ist dies im allgemeinen nicht mehr möglich. Büchi zeigte 1960, daß die ω-regulären Sprachen dennoch abgeschlossen sind unter Komplement. Dabei spielt Ramseys Theorem für unendliche Graphen eine wichtige Rolle.
• Conways LIFE ist unentscheidbar
  LIFE ist wohl der bekannteste der zellulären Automaten: Auf einem Gitter ist in jedem Schritt der Folgezustand eines Knotens (=Zelle) entweder tot oder lebend, abhägig von seinem bisherigen Zustand und dem seiner acht unmittelbaren Nachbarn.
  Conway, der Erfinder, vermutete, eine Anfangskonfiguration aus endlich vielen lebenden Zellen bleibe asymptotisch von beschränkter Größe. Um so größer die Überraschung, daß man im Gegenteil mit LIFE eine Turingmaschine simulieren kann!
• Zum Umweg-Faktor ebener geometrischer Wegesysteme
  Man will von a nach b; in direkter Verbindung (Luftlinie) haben diese Orte Abstand x, wegen der Straßen- oder Wegführung muß man jedoch einen Umweg der Länge δx gehen. Natürlich soll δ≥1 möglichst klein sein.
  Sind a und b beliebige Knoten eines geometrischen Graphen, so führt dieses Minimierungsproblem auf die wohlbekannten sogenannten Spanner. Diese sind jedoch i.A. nicht planar. Außerdem soll der 'Umweg-Faktor' δ in Praxis nicht nur zwischen zwei Knoten klein sein, sondern auch zwischen allen Paaren von Orten a und b des (nicht notwendig geradlinigen) Wegesystems. Eine preisgekrönte Arbeit des Bonner Lehrstuhls Rolf Klein hat für dieses Problem obere und untere Schranken hinsichtlich des erreichbaren Werts von δ angegeben und dabei viel interessante Geometrie verwendet.
• Graphenfärbung in erwartet konstanter Zeit
  Das Problem der k-Färbung ist eines der ältesten graphthereotischen Probleme. Diese Aufgabe fing wohl mit der Frage an, ob eine Landkarte mit Staatsgebieten so eingefärbt werden kann, dass keine zwei benachbarte Länder die selbe Farbe besitzen. Wegen der eingeschränkten Drucktechnologie war die Reduzierung der Anzahl der verschiedenen Farben elementar. Das Färbungsproblem war unter den ersten Problemen, die als NP-vollständig klassifiziert worden sind. Andererseits ist es aber sehr einfach dieses Problem für einen zufälligen Graphen zu lösen, wie von Herbert Wilf in seinem Buch im letzten Abschnitt beschrieben wird.
• Ein exponentieller Unterschied zwischen deterministischem und probabilistischem Broadcast in Radio-Netzwerken
  Bar-Yehuda, Goldreich und Itai haben in vielen Arbeiten Broadcasting in Radio Netzwerken untersucht. Gegeben sind n Teilnehmer und einer von ihnen besitzt eine Nachricht, die an alle n-1 anderen Teilnehmer drahtlos übermittelt werden soll. Dabei reicht die Reichweite nicht aus, um die Weiterleitung in einem Schritt zu ermöglichen (Multi-Hop Netzwerk). Zusätzlich kann es zu Übertragungsfehlern aufgrund von Interferenzen kommen. Die Zeiteinteilung in diesem Modell erfolgt rundenbasiert, d.h. in einer Runde kann ein Teilnehmer entweder empfangen oder senden. Der Empfang einer Nachricht ist nur dann erfolgreich, wenn kein anderer Teilnehmer zur gleichen Zeit in Reichweite gesendet hat.
  In dieser Arbeit wird nun die Zeitkomplexität von deterministischen und randomisierten Protokollen für erfolgreiches Broadcasting in Radio Netzwerken analysiert. Wesentliche Ergebnisse der Arbeit sind untere und obere Zeitschranken für diese Protokolle, die eine exponentielle Lücke zwischen deterministischem und randomisiertem Broadcasting verdeutlichen.
• Ein einfacher Sortierer, der fast immer sortiert
  Ein Sortierer ist eine schwarze Schachtel mit zwei Eingängen und zwei Ausgängen. Wenn man zwei Zahlen in die Eingänge wirft, dann kommen sie sortiert an den Ausgängen raus. Wenn man jetzt viele von diesen Sortierern mit Röhren geschickt verbindet, so hat man einen n-Sortierer mit n Eingängen und n Ausgängen. Ajtai, Komlos und Szemeredi haben bewiesen, dass so ein n-Sortierer mit Tiefe O(log n) gebaut werden kann. Jede Zahl fliegt dann durch maximal O(log n) Schachteln. Nur versteckt sich hinter dem O in der O-Notation eine vierstellige Konstante...
  Leighton und Plaxton können das viel schneller, nur nicht immer korrekt...
• Erkennen von Unit Disk Graphen
  Es sei eine Menge von Knoten in der Euklidischen Ebene gegeben, z.B. drahtlose Geräte; und der Unit Disk Graph dieser Menge ist nun so definiert, dass zwischen zwei Knoten eine ungerichtete Kante existiert, falls der Euklidische Abstand zwischen den beiden Knoten nicht grösser als 1 ist. Weil bei mobilen Ad-hoc-Netzwerken oft keine GPS-Information zur Verfügung steht, geht man davon aus, dass ein Graph ein in Form einer Nachbarschaftsliste gegeben ist aber keine Koordinaten der einzelnen Knoten.
  Nun wurde gezeigt, dass es NP-schwer ist zu entscheiden, ob dieser Graph ein Unit Disk Graph sein könnte. Selbst die "Approximation" dieses Problems bleibt schwer. Eine weitere Arbeit behandelt die Einbettung des Graphen in die Euklidische Ebene, d.h. die Vergabe virtueller planarer Koordinaten an die Knoten.
  Diese Ergebnisse sollen didaktisch aufgearbeitet und verständlich präsentiert werden.
• Aroras 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ß polynomielle Laufzeit hat. In diesem Vortrag soll Aroras Algorithmus aus der polierten Zeitschriftenversion von 1998 vorgestellt werden.
• Theory of P2P-networks   (3 Topics)
  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.
  1. Continuous-Discrete Approach - a topology which is degree/dilation optimal
  2. Load-Balancing - throwing balls into bins in a very structured environment
  3. Skip lists and skipgraphs - a topology which enables storing of ordered data without decrease of performance

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)
• Tipp: Bei Beamer-Vorträgen nur kräftige Farben verwenden!
• 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.