UNI Logo Bilder Heinz Nixdorf Institut
Algorithmen und Komplexität
Prof. Dr. math. Friedhelm Meyer auf der Heide
HNI Logo
Home > Fachgruppen > Prof. Dr. math. Friedhelm Meyer auf der Heide > Lehre > Perlen der Theoretischen Informatik
Wintersemester 2011/12, Seminar
Perlen der Theoretischen Informatik

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 gezeigt werden, dass 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", BI Wissenschaftsverlag 1995, von Uwe Schöning (Unibibliothek 41TVA2403, 60TVA2411) , 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 ihrer Arbeitsgebiete geprägt sein. Ziel des Seminars ist die Aufbereitung aktueller Forschungsarbeiten. Das Seminar findet als externes Blockseminar statt.

Veranstalter und Betreuer

Friedhelm Meyer auf der Heide und Mitarbeiter

Module

  • Modelle und Algorithmen (MuA)
  • Seminar: III.2.1, III.2.2, III.2.3, III.2.4

Termine

  • Achtung Raum- und Zeitänderung! Erstes Treffen: Vorbesprechung und Themenvergabe: 11.10.2011, 15:00 Uhr, F1.310
  • Abgabe der schriftlichen Ausarbeitung: 16. Januar 2012.
  • Externes Blockseminar: 13./14.2.2012 in Schloß Gehrden

Vergabe der Themen und Anmeldung

Die Themen werden auf dem ersten Treffen an die anwesenden Studierenden vergeben. Reservierungen oder Vorbelegungen von Themen sind nicht möglich. Sie müssen sich in  PAUL anmelden. Informationen zu PAUL finden Sie  hier. Nicht angemeldete Studierende werden nicht berücksichtigt. Die Reihenfolge der Anmeldung hat keine Bedeutung. Sollten sich mehr Studierende für das Seminar interessieren als Plätze vorhanden sind, so wird die Auswahl nach dem Studienfortschritt getroffen. Beim Seminar wäre bspw. der fertige Bachelor Voraussetzung.

Scheinerwerb

Ziel ist das selbstständige Erarbeiten, Verstehen und Wiedergeben einer wissenschaftlichen Forschungsarbeit. Die Wiedergabe besteht aus einer schriftlichen Ausarbeitung und einer Präsentation (Vortrag) über das behandelte Thema. Die Ausarbeitung im Umfang von 10-25 Seiten erfolgt mit eigenen Worten, d.h. eine rein wörtliche Übersetzung ist nicht ausreichend. Die Anfertigung der Ausarbeitung erfolgt vor der Präsentation und soll sicherstellen, dass die Inhalte verstanden wurden. Die Präsentation im Umfang von 45 Min. (+15 Min. Diskussion) soll das Problem klar machen, den Lösungsweg ausreichend tief beschreiben und eine Bewertung aufzeigen.

Für die TeilnehmerInnen gilt Anwesenheitspflicht während der Vorträge. In Anschluss an das Seminar findet eine mündliche Prüfung über 4 Seminarthemen statt. Die zu prüfenden Themen können aus den präsentierten Themen frei ausgewählt werden.

Betreuung: Wir empfehlen inhaltliche Fragen zum Thema, Gestaltung und Aufbau der schriftlichen Ausarbeitung und die Folien und das Konzept zum Vortrag mit dem Betreuer zu diskutieren. Die Termine mit dem Betreuer sind vom Studierenden zu organisieren. Eine Terminfindung erst unmittelbar vor Abgabe der schriftlichen Ausarbeitung oder vor den Vorträgen kann nicht garantiert werden, da die Betreuer Ihre eigenen Termine für Forschung und Lehre berücksichtigen müssen. Die Termine mit dem Betreuer sollten daher rechtzeitig von den Studierenden geplant werden.

Hinweise zur Ausarbeitung von Seminaren


Themen

Themen erscheinen hier rechtzeitig zu Vorlesungsbeginn.

Primal-Dual (1)

Jain und Vazirani entwickelten vor ungefähr 10 Jahren den ersten auf dem Primal-Dual Approximationsschema basierenden Algorithmus, der eine 3 Approximation für das Facility Location Problem liefert. Basierend auf diesem Algorithmus wurde von ihnen auch ein Approximationsalgorithmus für das k-median Problem entwickelt, welcher im Rahmen dieses Seminars vorgestellt werden soll. Das k-median Problem ist dem Facility Location Problem sehr ähnlich. Hier kann man die Facilities zwar kostenlos öffnen, es dürfen aber nur höchsten k viele geöffnet werden.

Literatur:
Jain, Vazirani: Approximation Algorithms for Metric Facility Location and k-Median Problems Using the Primal-Dual Schema and Lagrangian Relaxation (Journal of ACM 2001)

Betreuer:  Peter Pietrzyk

Kompakte Datenstrukturen (2)

Kompakte Datenstrukturen (englisch: „succinct data structures“) kodieren einerseits Daten in sehr wenig Speicherplatz und erlauben andererseits schnelle Zugriffe (siehe beispielsweise [2]). Diese Datenstrukturen verwenden Speicherplatz in der Größe des informationstheoretischen Minimums (vergleiche Begriff „Entropie“) plus einer zusätzlichen Redundanz. Auf dieser kodierten Repräsentation unterstützen sie gewisse Zugriffsfunktionen. Frühere kompakte Datenstrukturen besaßen ein lineares Verhältnis zwischen der Größe der Redundanz und der Zugriffszeit. Wenn die Redundanz beispielsweise konstant war, hat ein Zugriff lineare Zeit in der Eingabegröße benötigt. Patrascu [3] stellt eine Technik vor, bei welcher der Zugriff asymptotisch nur logarithmische Zeit benötigt. Dies wird durch erneute Blockkodierung auf verschiedenen Ebenen erreicht. Hreinsson, Krøyer und Pagh [1] bewerten dieses Ergebnis als „recent theoretical breakthrough“. Im Seminar wollen wir diese Art von Datenstrukturen kennenlernen und das vorliegende Ergebnis von Patrascu [3] analysieren.

Literatur
[1] Hreinsson, Jóhannes B. ; Krøyer, Morten ; Pagh, Rasmus: Storing a Compressed Function with Constant Time Access. In: Fiat, Amos (Hrsg.) ; Sanders, Peter (Hrsg.): Algorithms - ESA 2009 Bd. 5757. Springer-Verlag Berlin Heidelberg, 2009, S. 730–741
[2] Jacobson, Guy: Space-efficient static trees and graphs. In: Proceedings of the 30th Annual Symposium on Foundations of Computer Science (SFCS ’89), IEEE Computer Society, Oktober 1989, S. 549–554
[3] Patrascu, Mihai: Succincter. In: Proceedings of the 49th Annual IEEE Symposium on Foundations of Computer Science (FOCS ’08), IEEE Computer Society, Oktober 2008, S. 305–313

Betreuer:  Benjamin Eikel

Randomized Search Trees - Treaps (3)

Treaps sind eine randomisierte Variante von Suchbäumen, die gegenüber anderen Suchstrukturen (AVL-Baum, (a,b)-Baum, BB(alpha)-Baum, Skiplisten, ...) einige Vorteile bieten. So haben sie z.B. für alle Operationen die optimale erwartete Laufzeit und können aufrecht erhalten werden ohne zusätzliche Balance Informationen zu speichern.
Im Seminar wollen wir diese Datenstruktur kennenlernen und analysieren. Außerdem sollen die wesentlichen Unterschiede zu den anderen gängigen Datenstrukturen herausgearbeitet werden.

Literatur:
Raimund Seidel, Cecilia R. Aragon: Randomized Search Trees. Algorithmica, 16(4/5) 464-497. [ paper]

Betreuer:  Ralf Petring

How to Schedule When You Have to Buy Your Energy (4)

Scheduling Probleme treten sowohl in der Praxis als auch in der Theorie in vielfältiger Form auf. In der hier betrachteten Variante geht es um theoretische Modelle und Analysen für Schedulingstrategien im Umfeld von riesigen Hochleistungs-Rechenzentren. Es wird die Sicht des Rechenzentrums modelliert, welches Aufträge unterschiedlicher Größe und Wertes von seinen Kunden erhält. Um einen Auftrag zu einem bestimmten Zeitpunkt abzuschließen, muss eine entsprechend große Energiemenge investiert werden. Der Profit für einen abgeschlossenen Auftrag ergibt sich als Differenz zwischen Wert und investierter Energie. Ziel ist es die Aufträge derart auf die zur Verfügung stehenden Resourcen aufzuteilen, dass der Gesamtprofit maximiert wird.

Im Seminar sollen aktuelle theoretische Modellierungen dieses Problems sowie die jeweiligen Algorithmen und ihre Analyse vorgestellt werden. Ein Schwerpunkt kann hier beispielsweise auf die Analyse von Online-Algorithmen mittels Potentialfunktionen gelegt werden.

Literatur:
[1] K. Pruhs and C. Stein. How to schedule when you have to buy your energy. APPROX/RANDOM 2010. doi: 10.1007/978-3-642-15369-3_27
[2] H.-L. Chan, T.-W. Lam, and R. Li. Tradeoff between energy and throughput for online deadline scheduling. WAOA 1020. doi: 10.1007/978-3-642-18318-8_6
[3] S. Im, B. Moseley, and K. Pruhs. A tutorial on amortized local competitiveness in online scheduling. SIGACT News, 42(2):83–97, June 2011. doi: 10.1145/1998037.1998058.
[4] A. Borodin and R. El-Yaniv. Online Computation and Competitive Analysis, volume 53. Cambridge University Press, 1998.

Betreuer:  Peter Kling

Local Matchings (5)

Alice besucht im Wintersemester die Komplexitätstheorie und sucht dafür eine Lerngruppe. Bob und Charly, mit denen sie bisher immer ihre Lerngruppen hatte, sind leider nicht in der Komplexitätstheorie. Und so muss Alice jemand anders zum Lernen finden. Zufällig kennt Charly aber Dave und Eva, die beide auch in die Komplexitätstheorie gehen und erzählt Alice davon. Charly erzählt aber auch, dass Eva ziemlich unordentlich, Dave aber sehr gewissenhaft ist und immer Ordnung hält. Da Alice Unordnung aber garnicht ausstehen kann, fragt sie also Dave ob er mit ihr eine Lerngruppe bilden möchte.
Was dieses Beispiel beschreibt ist ein lokales Matching in einem Sozialen Netwerk ohne zentrale Instanz. Durch die Vermittlung von Bekanntschaften (triadic closure) können neue Verbindungen (social links) erzeugt werden. Die Teilnehmer des Netzwerkes entscheiden dann aufgrund der lokalen Informationen welche(r) Partner am besten für sie geeignet ist (sind). Matching Probleme liegen zahlreichen Zuweisungs- und Allokationsfragestellungen zu Grunde. Beispiele sind Zuweisungen von Jobs zu Arbeitern, von Organen zu Pationen oder ganz generell von Käufern zu Verkäufern.

Ausgangspunkt dieses Seminarthemas ist eine Arbeit von Martin Hoefer [1] in welcher er ein Netzwerk ohne zentrale Instanz betrachtet. Die Netzwerkknoten suchen dabei lokal die bzw. den jeweils best passende/n Partner um eine gemeinsame Aktion durchzuführen (Übungszettel lösen, Sport machen, in die Kneipe gehen,...). Ein überraschendes Ergebnis dieser Arbeit ist es, dass ein natürlicher Paramter für die Konvergenzzeit bis zum Erreichen stabiler Matchings der Speicher der Netzwerkknoten ist.

Literatur:
[1] Hoefer, M. Local Matching Dynamics in Social Networks. In Automata, Languages and Programming (2011), L. Aceto, M. Henzinger, and J. Sgall, Eds., vol. 6756 of Lecture Notes in Computer Science, Springer Berlin / Heidelberg, p. 113–124.

Betreuer:  Andreas Cord-Landwehr

Rubik's Cube (6)

Rubiks Zauberwürfel ist ein sehr bekanntes, mechanisches Knobelspiel, das in den 70ern von dem ungarischen Architekturprofessor Erno Rubik entwickelt worden ist. In der ursprünglichen Version besteht dieser Zauberwürfel aus 3 x 3 x 3 kleineren Würfeln, deren Position im Zauberwürfel durch Drehung verändert werden kann. Im gelösten Zustand zeigt jede Seite des Zauberwürfels eine andere Farbe. Ziel ist es von einem beliebigen, durch Drehen erzeugten Zustand den gelösten Zustand wiederherzustellen. Im August 2010 gelang es einem Forscherteam zu zeigen, dass "God's Number" (die Anzahl an Drehungen, die notwendig ist, um das Spiel im schlechtesten Anfangszustand zu lösen) genau 20 ist. Auch wenn sie geschickter vorgegangen sind als alle 43.252.003.274.489.856.000 Zustände durchzuprobieren, benötigen die durchgeführten Berechnungen auf einem zeitgemäßen Desktop PC etwa 35 Jahre.


In einer aktuellen Arbeit betrachten Demaine et. al. einen n x n x n Würfel sowie eine n x n x 1 Variante. Es gelingt ihnen zu zeigen, dass "God's Number" in beiden Fällen Theta(n^2/log(n)) beträgt. Dazu geben sie einen Algorithmus an, der O(n^2/log(n)) Drehungen benötigt, und zeigen durch ein Abzählargument, dass im schlechtesten Fall Omega(n^2/log(n)) Drehungen notwendig sind. Darüber hinaus nähern sie sich der weiterhin offenen Frage, ob es NP-schwer ist einen n x n x n oder n x n x 1 Rubikwürfel mit der kleinstmöglichen Anzahl an Drehungen zu lösen. Sie zeigen durch eine geschickte Konstruktion, dass es NP-schwer ist zu entscheiden, ob es eine Folge von k Drehungen gibt, sodass nur ein Teil der kleineren Würfel an der richtigen Position ist. Weiterhin zeigen sie, dass es einen polynomiellen Algorithmus gibt, der die kürzeste Folge von Drehungen zum Lösen eines O(1) x O(1) x n Würfels berechnet.

Literatur:

www.cube20.org
web.mit.edu/newsoffice/2011/rubiks-cube-0629.html
arxiv.org/abs/1106.5736

Betreuer:  Sebastian Abshoff

Peer-to-Peer-Netzwerke

Klassische Internetdienste wie WWW, E-Mail, Internetsuchmaschinen, usw. werden in den Protokollen der Anwendungsschicht als Client-Server Architektur asymmetrisch behandelt. Es gibt einen oder eine geringe Anzahl von Servern und eine hohe Anzahl von Clients, die die Dienste des Servers in Anspruch nehmen. In einem Peer-to-Peer-System dagegen gibt es diese Aufteilung nicht. Alle Teilnehmer übernehmen die Server- bzw. Clientfunktion gleichermaßen. Man spricht daher auch nicht mehr von Client und Server, sondern von Peers. Solche Netzwerke bieten sich besonders gut an, wenn Daten verteilt gespeichert und ausgetauscht werden sollen. In den folgenden beiden Themen werden wir grundlegende Peer-to-Peer-Netzwerke behandeln.

CAN & Chord (7)

„CAN [3] ist eine verteilte Datenstruktur, durch die Daten bestimmten Peers zugewiesen werden. Die Peers sind dabei durch eine Gitterstruktur verbunden. Diese Gitterstruktur kann durch einfache lokale Operationen aufgebaut und aufrecht erhalten werden. CAN war das erste Peer-to-Peer-Netzwerk, das effiziente Datenstrukturen mit einem verteilten Overlay-Netzwerk kombinierte. In Chord [4] werden wie bei CAN verteilte Hash-Tabellen eingesetzt. Im Gegensatz zu dem zwei-dimensionalem Raum bei CAN, wird jedoch ein eindimensionaler Raum verwendet.“[1]

Betreuer:  Matthias Fischer

Pastry & Tapestry (8)

“Pastry [5] und Tapestry [6] sind zwei unabhängig voneinander entstandene Peer-to-Peer Netzwerke, die auf derselben Idee aufbauen, nämlich der Verwendung eines Routing-Verfahrens[2]. Hierbei handelt es sich um ein effizientes verteiltes Verfahren zum Zugriff auf Datenkopien in einem verteilten statischen Netzwerk. Auf dieser Basis wurden Pastry und Tapestry entwickelt, die das Verfahren unter anderem um Mechanismen zum Einfügen und Löschen von Peers und Daten erweitern.“ [1]

Betreuer:  Claudius Jähn

Literatur:

[1] Peer-to-Peer-Netzwerke: Algorithmen und Methoden, Peter Mahlmann, Christian Schindelhauer, Springer, 2007.
[2] C. Greg Plaxton, Rajmohan Rajaraman, Andréa W. Richa: Accessing Nearby Copies of Replicated Objects in a Distributed Environment. SPAA 1997: 311-320
[3] Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard M. Karp, Scott Shenker: A scalable content-addressable network. SIGCOMM 2001: 161-172
[4] Ion Stoica, Robert Morris, David R. Karger, M. Frans Kaashoek, Hari Balakrishnan: Chord: A scalable peer-to-peer lookup service for internet applications. SIGCOMM 2001,  149-160, 2001
[5] Antony I. T. Rowstron, Peter Druschel: Pastry: Scalable, Decentralized Object Location, and Routing for Large-Scale Peer-to-Peer Systems. IFIP/ACM International Conference on Distributed Systems Platforms, 329-350, 2001.
[6] Kirsten Hildrum, John Kubiatowicz, Satish Rao, Ben Y. Zhao: Distributed object location in a dynamic network. SPAA’02: 41-52, 2002

Distributed Computation in Dynamic Networks (9)

Dieses Thema behandelt das verteilte Rechnen in dynamischen Netzwerken, bei denen sich die Netzwerktopologie von Runde zu Runde ändern kann. Die Knoten wissen nichts über das Netzwerk. Sie kennen ihre aktuellen Nachbarn nicht, dürfen aber in jeder Runde eine Nachricht an alle Nachbarn broadcasten. So werden mobile drahtlose Netzwerke modelliert, bei denen aufgrund von Mobilität und Interferenzen keine feste Netzwerkstruktur existiert. Die Autoren des Papers führen eine Stabilitätseigenschaft ein, die sie T-interval connectivity nennen. Diese sagt aus, dass in allen T aufeinanderfolgenden Runden ein Spannbaum existiert, der sich innerhalb dieser T Runden nicht ändert. Für T=1 bedeutet das, dass der Graph immer zusammenhängend ist, aber sich von Runde zu Runde beliebig ändern kann.

Die Autoren untersuchen für dieses Modell mehrere Probleme. Sie zeigen, dass die Anzahl der Knoten des Netzwerks für T=1 in O(n^2) Runden berechnet werden kann. Für T > 1 geht es etwas schneller: Es werden O(n + n^2/T) Runden benötigt. Auf eine ähnliche Art können auch weitere Funktionen auf den Eingabedaten der Knoten berechnet werden, z.B. das Minimum oder Maximum aller Eingaben.

Literatur:
Fabian Kuhn, Nancy Lynch, and Rotem Oshman. 2010. Distributed computation in dynamic networks. In Proceedings of the 42nd ACM symposium on Theory of computing (STOC '10). 513-522.

Betreuerin:  Barbara Kempkes


Elektronisches Format der Ausarbeitung

Die Ausarbeitung des Seminars wird in  LaTeX mit dem  svmult-Style (siehe Paket  Beitragswerke, Konferenzbände) des  Springer-Verlags erstellt. Es wird ein Gesamtband erstellt, ein Beispiel sehen Sie  hier. Die LaTeX-Sourcen UND ein fertiges pdf Ihrer Ausarbeitung schicken Sie als zip-Datei per E-Mail an Matthias Fischer ( mafi(at)upb.de). Bitte geben Sie in Ihrer Ausarbeitung keine Matrikelnummer an. Beachten Sie folgende LaTeX-Spielregeln:

  • Das Dokument wird nur mit pdflatex kompiliert. Bilder werden dementsprechend direkt mit pdf, jpg oder png eingebunden. DVI-LaTeX wird nicht erzeugt.
  • Es gibt nur eine .tex Datei für die gesamte Ausarbeitung. Starten Sie am besten mit der im svmult Paket angegebenen Datei "author.tex". Alle Bilder und die Tex-Datei liegen im selben Verzeichnis. Die oberste Gliederungsebene ist \section.
  • Um alle selbst definierten Kommandos, Labels und Referenzen eindeutig zu definieren, bekommt jeder Autor (Beispiel: Matthias Fischer) einen eindeutigen Präfix (Beispiel: MaFi). Kommandos, Labels und Referenzen bestehen dann aus Präfix gefolgt von der selbst gewählten individuellen Bezeichung (Beispiel: TollesLabel). Das fertige Label sieht also so aus: \label{MaFiTollesLabel}.
  • Der Name der LaTeX-Datei (es gibt nur eine text-Datei!) besteht nur aus dem Präfix: "MaFi.tex". Die Namen der Bilddateien bestehen aus dem Päfix und einem individuellem Teil (Beispiel: MeinBild): Der fertige Name für eine Bilddatei sieht also so aus: "MaFiMeinBild.png"
  • Nach \maketitle wird der Abstract in svmult mit \begin{abstract} \end{abstract} erfasst, ihm folgt das lokale Inhaltverzeichnis: \hrule \setcounter{minitocdepth}{2} \dominitoc
  • Wir verwenden durchgängig die svmult theorem-Umgebungen. Die Option "nospthms" und das Paket "amsthm" findet keine Verwendung. Das Paket "amsthm" verträgt sich nicht mit "svmult".
  • Wir verwenden kein BibTex, die Literatur wird so wie im svmult Template „referenc.tex“ angegeben, jedoch nicht in 2 Dateien, sondern zusammen mit dem Haupttext in einer Datei. Der Inhalt von "referenc.tex" sollte daher ans Ende der Autor-Datei kopiert werden. Die Referenzen werden, wie im svmult Template "referenc.tex" gezeigt, angegeben. Es ist einheitlich zur Formatierung der Einträge der in „reference.tex“ angegebene Stil (Autor, Jahr, Titel, ....) zu verwenden.
  • Zur Formatierung der Pseudocode-Algorithmen verwenden wir "algorithmicx" inkl. der floating Umgebung "algorithm" aus "Algorithms". Empfehlenswert ist mit dem bereits vordefinierten Befehlen im Paket "algpseudocode" zu starten. Das Paket "algorithmic" aus "Algorithms" verwenden wir nicht. Alternativ zu "algorithmicx" können die Algorithmen auch mit "listings" oder "verbatim" erstellt werden. Wer Erfahrung mit dem Paket "algorithm2e" hat, melde sich bitte.
  • Zusammen mit dem im svmult Beispiel "author.tex" angegebenen Header
    \documentclass[deutsch]{svmult} \usepackage{makeidx} \usepackage{graphicx} \usepackage{multicol} \usepackage[bottom]{footmisc} \makeindex
    können dann noch die folgenden Pakete verwendet werden; andere sind nicht erlaubt:
    \usepackage[latin1]{inputenc} \usepackage[ngerman]{babel} \usepackage[T1]{fontenc} \usepackage{amsmath, amssymb, amsfonts, amscd} \usepackage{algpseudocode} \usepackage{algorithm} \usepackage{listings} \usepackage{verbatim}
  • Die in svmult effektiv beschreibbare Seitengröße ist für unsere Verwendung zu klein. Die angepasste Form erhalten Sie hier. Tauschen Sie ihre svmult.cls dagegen aus.


Nach oben