Hauptseminar KTuEA: Algorithmik

Wintersemester 2006/2007

Prof. M. Dietzfelbinger

Inhalt: Im Hauptseminar werden vertieft Methoden im Umfeld der Vorlesungen

„Randomisierte Algorithmen“, „Approximationsalgorithmen“ und „Datenstrukturen“

erarbeitet.

Basis: Fortgeschrittene (englischsprachige) Lehrbücher, Originalarbeiten.

Leistungen: Ausarbeitung, Vortrag (min. 60 Min.), Diskussion, Teilnahme.

Vorkenntnisse: Die  Teilnahme an einer der genannten Vorlesungen sowie der Vorlesung "`Effiziente Algorithmen"' ist sinnvoll. Nötig sind ausreichende mathematische Kenntnisse.

Ort und Zeit: in der zweiten Semesterhälfte oder kompakt im Februar/März.

Gemeinsame Vorbesprechung:

Freitag, 27.10.2006, 9:00 Uhr, Informatikgebäude Raum 115

Voranmeldung: per email an jana.kopp(at)tu-ilmenau.de (auch Themenwünsche nennen).

Weitere Information und Material: Webseite des Fachgebiets

Auskunft: jederzeit beim Veranstalter
(Raum 306, Tel. 03677/69-2656, email: martin.dietzfelbinger(at)tu-ilmenau.de

Vortragsthemen:

1. Bälle in Körbe. (VERGEBEN!) (Eine sehr genaue Analyse der maximalen Beladungszahl.) Wir werfen m Bälle zufällig auf n Körbe. Wie viele Bälle landen im maximal besetzten Korb?
2. Randomisiertes MinCut: schneller als deterministische Verfahren. In der Vorlesung „Randomisierte Algorithmen“ wird als einführendes Beispiel die Bestimmung eines minimalen Schnitts in einem Graphen angegeben. In diesem Vortrag wird gezeigt, wie man durch „Tunen“ des Ansatzes einen randomisierten Algorithmus erhält, der schneller als die bekannten deterministischen Verfahren ist.
3. Randomisiertes Schätzen. Gegeben ist (implizit) eine Menge von Strukturen A. Wir sollen schätzen, wie viele Elemente A hat. Beispiel: Als Input erhalten wir eine DNF-Formel $\varphi$. Wie viele erfüllende Belegungen hat $\varphi$ (ungefähr)?
4. Randomisiertes  Routing. Analyse eines randomisierten Routingverfahrens für Hypercube- und Butterfly-Netzwerk. (Besonders für Studierende geeignet, die die Vorlesung „Parallele Algorithmen auf Gittern und Hypercubes“ kennen.)
5. Kürzeste Wege in erwarteter linearer Zeit. Hier wird die Eingabe (Kantenlängen im Graph) als zufällig angenommen. Mit einer geschickten Datenstruktur ergibt sich ein relativ einfacher Algorithmus zur Berechnung der kürzesten Wege von einem Startknoten aus, der in linearer Zeit läuft.
6. Eine alternative Heap-Struktur: Pairing Heaps. Hierbei geht es um eine Implementierung des Datentyps „Priority Queue“ oder „Vorrangswarteschlange“. Pairing Heaps sind eine attraktive, leicht zu implementierende, in der Praxis sehr effiziente Alternative zu Fibonacci-Heaps.
7. Double Ended Priority Queues. (Mengenverwaltung mit Minimum und Maximum.) Bei gewöhnlichen Priority Queues kann man den gegenwärtig kleinsten Eintrag kostengünstig entnehmen. Was ändert sich, wenn man Minimum und Maximum bereitstellen muss?
8. Über Caching-Algorithmen. Dieser Vortrag behandelt die Analyse verschiedener Verdrängungsstrategien, die man sowohl für die Hintergrundspeicherverwaltung als auch für die Cache-Verwaltung benutzen kann. (Kombinatorische Methoden und randomisierte Methoden.)
9. Lokale Suche. Hier geht es um eine sehr allgemeine Strategie zur Anwendung auf Optimierungsprobleme. Nicht immer ist eine Erfolgsgarantie (polynomielle Laufzeit, Approximationsgüte) mitgeliefert; dennoch sind die Strategien dieser Familie nützlich.
10. Simulated Annealing, Tabu Search, Evolutionärer Ansatz (für das TSP). Dieser Vortrag stellt klassische, inzwischen gut verstandene und viel verwendete, heuristische Ansätze zur Lösung schwieriger Optimierungsprobleme vor. Das durchgehende Beispiel ist das Traveling Salesperson Problem (TSP).
11. Aspekte evolutionärer Algorithmen für das TSP. Kann gegebenenfalls von einem 2-Personen-Team bearbeitet werden. Der Entwurf eines evolutionären Algorithmus erfordert eine Reihe von Design-Entscheidungen: Wie sollen Lösungen für eine Problem-Instanz repräsentiert werden, wie sollen Lösungen bewertet werden, welche Veränderungen des „Erbguts“ soll man betrachten, mit welcher Population soll man beginnen?
12. Simulated Annealing ist (manchmal) besser als der Metropolis-Algorithmus. Für ein
    sehr bekanntes, natürliches Optimierungsproblem (Minimaler Spannbaum) funktioniert Simulated Annealing beweisbar besser als der Metropolis-Algorithmus.
13. Baumweite und Baumzerlegungen. Dieses Thema beschäftigt sich mit einer fortgeschrittenen Technik zum Umgang mit Berechnungsproblemen für Graphen, die im allgemeinen Fall schwierig sind. Dem Ansatz liegt die Idee zugrunde, dass man es ausnützen kann, wenn Graphen „baum-ähnlich“ sind.
14. Bearbeitung von Strings in vergleichsbasierten Datenstrukturen. Viele Datenstrukturen und ihre Beschreibungen gehen davon aus, dass die Einträge atomare Objekte sind, die in konstanter Zeit miteinander verglichen werden können. Es wird eine allgemeine Technik vorgestellt, um vergleichsbasierte Datenstrukturen in effizienter Weise für Strings nutzen zu können.

Themen im Detail, Literaturangaben.