Seminar über Algorithmen

Wintersemester 2011/12

Dozent: Wolfgang Mulzer
Termin: Dienstag, 14–16 Uhr, SR 005

Impressum 

Aktuelles

• 17.02.2012: Die Noten hängen neben dem TI-Sekretariat aus. Die Scheine können im Sekretariat abgeholt werden bzw. der Eintrag ins CM-System wird in einigen Wochen erfolgen.
• 13.02.2012: Morgen der letzte Vortrag im Semester: Terese Haimberger über Epsilon-Netze.
• 26.01.2012: Nächste Woche gibt es zwei Vorträge: am Dienstag spricht Michelle Meekes über Sampling und am Freitag holt Yannik Stein seinen Vortrag über nächste Nachbarsuche nach.
• 23.01.2012: Das morgige Seminar muss leider ausfallen. Der nächste reguläre Termin findet nächste Woche statt.
• 14.01.2012: Nächsten Dienstag: Thilo Ratnaweera über nächste Nachbarn
• 04.01.2012: Nächsten Dienstag: Maximilian Konzack über lineares Programmieren.
• 13.12.2011: Akademische Ferien. Das nächste Seminar findet statt am 03.01.2012. Frohe Weihnachten und ein gutes neues Jahr!
• 08.12.2011: Am Freitag: David Breßler über Triangulierungen.
• 29.11.2011: Heute: Iyasu Beraki über die Verschiebetechnik
• 18.11.2011: Nächster Vortrag: Andreas Weise über die Methode der multiplikativen Gewichte, am Freitag den 25.11.2011 von 14–16 Uhr in SR 053.
• 15.11.2011: Vortrag heute: Erik Sniegula über Clustering.
• 18.10.2011: Eine vorläufige Vortragseinteilung ist online. Der erste Vortrag findet statt am Freitag, den 28.10.2011, von 14–16 Uhr, voraussichtlich in SR053.
• 04.10.2011: Die erste Veranstaltung findet statt am 18.10.2011. Ich werde ein paar einleitende Worte sprechen und noch einige organisatorische Fragen klären. In der zweiten Woche beginnen die Vorträge.
• 18.07.2011: Die Themenliste ist online.
• 01.07.2011: Die Vorbesprechung findet statt am Donnerstag, den 14.07.2011, Raum 137, 14:00 Uhr st.

Voraussetzungen

• Schein in "Höhere Algorithmik", "ALP 3" oder vergleichbarer Veranstaltung
• Vordiplom in Informatik, Mathematik o.ä. oder vier erfolgreiche Semester im BSc-Studiengang.

Themen

Das Seminar befasst sich mit geometrischen Approximationsalgorithmen. Viele geometrische Probleme (z.B., Set Cover, Finden des kleinsten umschließenden Kreises, Finden des nächsten Nachbarn, usw) lassen sich nur mit großem Aufwand exakt lösen. Insbesondere in höheren Dimensionen stoßen die üblichen Techniken an ihre Grenzen. Approximationsalgorithmen bieten einen Ausweg: falls wir mit einer Lösung zufrieden sind, die nur ein wenig schlechter ist als das Optimum, können wir oft wesentlich einfachere und/oder effizientere Algorithmen entwickeln.

1. einfache gitterbasierte Approximation [vergeben]
   • Eine einfache Methode zum Entwurf von geometrischen Approximationsalgorithmen besteht darin, ein regelmäßiges Gitter über die Eingabepunkte zu legen. Die Methode wird angewandt, um das engste Paar einer Punktmenge zu finden, sowie den kleinsten Kreis, welcher eine bestimmte Anzahl an Punkten enthält.
   • Literatur:
     • Har-Peled, Kapitel 1.
2. Quadbäume
   • Quadbäume sind eine einfache und oft auch effiziente Datenstruktur zur Darstellung von Punktmengen, und sie liegen zahlreichen geometrischen Algorithmen zu Grunde. Es sollen die Definition, Eigenschaften und einfache Algorithmen von Quadbäumen beschrieben werden.
   • Literatur:
     • Har-Peled, Kapitel 2;
     • de Berg, Cheong, van Kreveld, Overmars. Computational Geometry: Algorithms and Applications, Kapitel 14.
3. Well-Separated-Pair-Decomposition [vergeben]
   • Für n Punkte in d Dimensionen gibt es im allgemeinen n^2 viele verschiedene paarweise Abstände. Ist man aber mit einer Approximation zufrieden, muss man nur noch linear viele Abstände unterscheiden. Dies leistet die Well-Separated-Pair-Decomposition, mit der man effizient nächste Nachbarn ausrechnen und einen minimalen aufspannenden Baum für die Punkte in O(n log n) Zeit approximieren kann.
   • Literatur:
     • Har-Peled, Kapitel 3;
     • Callahan und Kosaraju. A Decomposition of Multidimensional Point Sets with Applications to k-Nearest-Neighbors and n-Body Potential Fields, JACM 42(1), pp. 67–90, 1995.
4. Clustering [vergeben]
   • Clustering ist ein klassisches Problem, bei dem wir eine Punktmenge sinnvoll in Gruppen aufteilen möchten. Was das heißen kann, und wie sich das effizient erreichen lässt, soll hier beschrieben werden.
   • Literatur:
     • Har-Peled, Kapitel 4;
     • Blum, Blacan, Gupta. Approximate Clustering without the Approximation, [link].
5. VC-Dimension und Epsilon-Netze [vergeben]
   • Sei P eine Menge von Punkten in der Ebene. Es existiert immer eine Teilmenge S von P mit konstanter Größe, so dass folgendes gilt: Jeder Kreis, der mindestens ein Prozent der Punkte aus P enthält, enthält mindestens einen Punkt aus S. P lässt sich also durch eine konstante Teilmenge approximieren! Diesem Phänomen liegt die sogenannte VC-Dimension zu Grunde, welche auch in der Lerntheorie Anwendung findet. Die VC-Dimension und ihre Konsequenzen für geometrische Approximation soll erklärt werden.
   • Literatur:
     • Har-Peled, Kapitel 5;
     • Chazelle. The Discrepancy Method, Kapitel 4, [link].
6. Die Methode der multiplikativen Gewichte [vergeben]
   • Die Methode der multiplikativen Gewichte ist ein Meta-Algorithmus mit vielen Anwendungen in der algorithmischen Geometrie, der künstlichen Intelligenz, dem Entwurf von Approximationsalgorithmen uvam. In der algorithmischen Geometrie lässt sich damit zum Beispiel zeigen, dass es zu jeder Menge von n ebenen Punkten einen aufspannenden Baum gibt, so dass jede Gerade nur sqrt(n) viele Kanten dieses Baumes schneidet.
   • Literatur:
     • Har-Peled, Kapitel 6;
     • Arora, Hazan, Kale. Multiplicative weights method: a meta-algorithm and its applications, [link].
7. Schätzen der Tiefe durch Stichproben [vergeben]
   • Gegeben sei eine Menge von Objekten in der Ebene. Wir definieren die Tiefe eines Punktes als die Anzahl der Objekte, welche ihn enthalten. Mit Hilfe von Stichproben kann man elegante Sätze über die Struktur von Mengen bestimmter Tiefe erhalten. Des weiteren kann man eine effiziente Datenstruktur entwickeln, mit welcher man die Tiefe eines Anfragepunkts schnell approximieren kann.
   • Literatur:
     • Har-Peled, Kapitel 9 und 10.
8. Die Verschiebetechnik [vergeben]
   • Bei der Verschiebetechnik wird ein Gitter zufällig über eine Punktmenge verschoben. Dadurch lässt sich die Punktmenge in Teile aufspalten. Eine Anwendung besteht in der effizienten Approximation der kleinsten Anzahl von Einheitskreisen, um eine ebene Punktmenge zu überdecken.
   • Literatur:
     • Har-Peled, Kapitel 11;
     • Hochbaum und Maaß. Approximation algorithms for covering and packing problems in image processing and VLSI, JACM 32, pp. 130–136, 1985.
9. Erzeugung von guten Triangulierungen [vergeben]
   • Oft möchte man zu einer gegebenen Punktmenge eine Triangulierung (ein Gitter) finden, welches ''weich'' zwischen diesen Punkten interpoliert. Dies ist zum Beispiel nützlich in der Computergraphik oder beim Lösen von Differentialgleichungen. Mit Hilfe von Quadbäumen kann man gute Gitter effizient erzeugen.
   • Literatur
     • Har-Peled, Kapitel 12;
     • Bern, Eppstein, Gilbert. Provably good mesh generation.
10. Approximation für das Rundreiseproblem in der Ebene [vergeben]
    • Wir wollen eine Menge von n Städten besuchen, jede genau einmal. Dabei soll die Gesamtanzahl der zurückgelegten Kilomenter minimiert werden. Dies ist das Rundreiseproblem, ein klassisches NP-schweres Problem, welches höchstwahrscheinlich nicht effizient exakt lösbar ist. Wenn wir aber mit einer nur wenig schlechteren Lösung zufrieden sind, so existiert ein effizienter Algorithmus. Dabei hängt die Laufzeit von der Approximationsgüte ab.
    • Literatur:
      • Har-Peled, Kapitel 13;
      • Arora. Polynomial-time Approximation Schemes for Euclidean TSP and other Geometric Problems, [link].
11. Heuristiken für das Rundreiseproblem mittels Ant Colony Optimization [vergeben]
12. Lineares Programmieren in niedrigen Dimensionen [vergeben]
    • Lineares Programmieren ist ein klassisches Verfahren aus der kombinatorischen Optimierung, bei dem eine lineare Zielfunktion optimiert wird, so dass gleichzeitig eine Menge von linearen Ungleichungen erfüllt ist. Falls die Anzahl der zu optimierenden Variablen konstant ist, so lassen sich elegante und sehr schnelle Algorithmen zur Lösung linearer Programme finden.
    • Literatur:
      • Har-Peled, Kapitel 15;
      • Clarkson, Las Vegas Algorithms for Linear and Integer Programming when the Dimension is Small, [link].
13. Nächste Nachbarn in niedrigen Dimensionen [vergeben]
    • Eine einfache Datenstruktur zur approximativen Suche von nächsten Nachbarn für gleichmäßig verteilte Punkte.
    • Literatur:
      • Har-Peled, Kapitel 17.
14. Nächste Nachbarn durch Punktlokalisierung [vergeben]
    • Eine Datenstruktur für approximative nächste Nachbarn durch Punktlokalisierung zwischen Bällen und ein approximatives Voronoi Diagramm.
    • Literatur:
      • Har-Peled, Kapitel 18.
15. Dimensionsreduktion – Johnson-Lindenstrauss [sehr mathematisch][vergeben]
    • Das Lemma von Johnson-Lindenstrauss besagt, dass man eine hochdimensionale Punktmenge von n Punkten effizient durch eine Menge in log n vielen Dimensionen approximieren kann, so dass die paarweisen Abstände fast erhalten bleiben. Dadurch kann man dem Fluch der Dimension entgehen.
    • Literatur:
      • Har-Peled, Kapitel 19.
16. Nächste Nachbarn in höheren Dimensionen [vergeben]
    • Literatur:
      • Har-Peled, Kapitel 20.
17. Coresets [vergeben]
    • Ähnlich wie Epsilon-Netze bieten Coresets eine Möglichkeit, eine gegebene Punktmenge durch eine Teilmenge konstanter Größe zu approximieren. Hierbei geht es bei Coresets darum, die Ausdehnung der Punktmenge zu erfassen. Anhand eines Coresets kann man zum Beispiel leicht den kleinsten Ball approximieren, welcher die gesamte Menge umschließt.
    • Literatur:
      • Har-Peled, Kapitel 23;
      • Agarwal, Har-Peled und Varadarajan. Geometric Approximation via Coresets, [link].
18. Die Bentley-Saxe Dynamisierungsmethode [vergeben]
    • Für bestimmte Probleme ist es möglich, aus einer statischen Datenstruktur, welche nur Suchanfragen unterstützt, eine dynamische Datenstruktur zu konstruieren, welche Elemente einfügen und löschen kann. Dabei verschlechtert sich die Laufzeit gewöhnlich nur um einen logarithmischen Faktor.
    • Literatur:
      • Klein. Algorithmische Geometrie, Kapitel 3;
      • Bentley und Saxe.Decomposable Searching Problems I: Static-to-Dynamic Transformation, J. Algorithms 1(4), pp. 301–358, 1980.

Vorträge

(Die Zusammenfassungen und Folien der Teilnehmer sind ohne Gewähr der Richtigkeit.)

Literatur

• Sariel Har-Peled, Geometric approximation algorithms, AMS Press, 2011. [link]
  [Bibliographie] (nur aus dem Fachbereichsnetz)

Wie halte ich einen Vortrag?

Im Web gibt es viele Ressourcen mit nützlichen Tipps zur effektiven Gestaltung eines Vortrags. Hier einige Beispiele, die mir gefallen haben.

1. Christian Knauer und Frank Hoffmann.
   Wie gestalte ich einen Seminarvortrag?
   Etwas alt, aber immer noch interessant.
2. Ian Parberry.
   How to Present a Paper in Theoretical Computer Science: A Speaker's Guide for Students.
   Spezielle Tipps für die theoretische Informatik.
3. Paul Halmos.
   How to talk Mathematics.
   Für Mathematiker, aber vieles trifft auch auf die theoretische Informatik zu.
4. Patrick Winston.
   How to speak.
   Lustiges Video. Die ersten fünf Minuten kann man getrost überspringen.

Hier die Fragen, von denen ich mich bei der Bewertung eines Seminarvortrags leiten lasse.

Perspektiven

Im Anschluss an die Veranstaltung können Studien–, Bachelor–, Examens–, Diplom– und Masterarbeiten vergeben werden.

Scheinkriterien

• erfolgreicher Vortrag, insgesamt 90 Minuten Dauer.
• Kurzbeschreibung des Vortrags, ca. 4 DIN A4-Seiten in PDF. Davon sind vor dem Vortrag Kopien an alle Teilnehmer auszuteilen und ein elektronisches Exemplar abzugeben.
• Regelmäßige Teilnahme am Seminar.