 |
 |
| Algorithmen und Komplexität |
 |
| |
| Orientierung: |
| Heinz
Nixdorf Institut Algorithmen und Komplexität |
| |
| Webmaster |
»Effiziente Algorithmen«
Proseminar - Sommer 2005
Christian
Schindelhauer
Klaus
Volbert
|
|
Neues
- Keine Treffen am 20.05., 27.05., 24.06. (1. Abteilung)
Inhalt
Dieses Proseminar richtet sich an Studenten des Bachelorstudiengangs Informatik. In diesem Seminar werden Vorträge von den Studenten aus dem Bereich der effizienten Algorithmen gehalten.Themenstellungen
- Die diskrete Mathematik der Informatik
- Verschiedene Sortieralgorithmen
- Effiziente Datenstrukturen
- Dynamische Programmierung
- Gierige Algorithmen
- Kürzeste Wege-Suche
- Sortier-Netzwerke
- Algorithmen für parallele Rechner
- Matrixoperationen
- Pattern-Matching
- Geometrische Algorithmen
- Approximationsalgorithmen
Organisation:
Aufgrund des großen Andrangs ist das Proseminar in zwei Abteilungen aufgeteilt worden. Der Besuch der Veranstaltung der anderen Abteilung ist freiwillig.1. Abteilung (freitags), Christian Schindelhauer
| Nr |
Vorname |
Name |
Thema |
Literatur |
1. Vortrag |
2. Vortrag F1.406 |
| 1 | Jens | Winter | Berechnung des Medians | CLR - Kap 10 | 03.06. 09:00 |
26.07. 10:00 |
| 2 | Markus | Kirschke | Kombinieren von Datenstrukturen | CLR - Kap 15 | ||
| 3 | Benjamin | Potyka | Optimale Triangulierung | CLR - Kap 16 | ||
| 4 | Jens | Bennemann | Amortisierte
Analyse |
CLR - Kap 18 | ||
| 5 | Juan | Gomez Fernandez |
B-Trees | CLR - Kap 19 | 10.06. 09:00 | 26.07. 11:00 |
| 6 | Azad | Kamo | Die Analyse von Union | CLR - Kap 22.4 | 10.06. 09:30 | 26.07. 13:00 |
| 7 | Valeri | Felk | Single-Source-Shortest Path | CLR - Kap 25 | 10.06. 10:00 | 26.07. 14:00 |
| 8 | Eugen | Dyck | Max Flow - Preflow Push | CLR - Kap 27 | 10.06. 10:30 | 27.07. 11:00 |
| 9 | Alexander | Kujat | Maximum Flow - Ford Fulkerson | CLR - Kap 27 |
17.06. 09:00 | 27.07. 10:00 |
| 10 | Jens | Ellerweg | Additions- und Multiplikationsschaltkreise | CLR - Kap 29 | 17.06. 09:30 | 27.07. 13:00 |
| 11 | Christoph | Krislin | Strassens Matrix Multiplikation | CLR - Kap 31 | 17.06. 10:00 | 27.07. 16:00 |
| 12 | Martin | Tofall | Boyer-Moore Pattern Matcher | CLR - Kap 34 | 17.06. 10:30 | 27.07. 15:00 |
2. Abteilung (mittwochs),
Klaus Volbert
| Nr |
Vorname |
Name |
Thema |
Literatur |
1. Vortrag |
2. Vortrag F1.310 |
| 1 | Tobias | Nelkner | Huffman Codes und Shannon Bounds |
CLR, Kap 17 |
01.06. 16:00 |
26.07. 10:00 |
| 2 | Michael | Brinkmann | Fibonacci Heaps |
CLR, Kap 21 |
01.06. 16:30 |
26.07. 11:00 |
| 3 | Markus | Jürgens | All-Pairs-Shortest Paths |
CLR, Kap 26 |
01.06. 17:00 |
26.07. 13:00 |
| 4 | Nicolas | Heine | Sortierschaltkreise |
CLR, Kap 28 |
08.06. 16:00 |
26.07. 14:00 |
| 5 | Peter |
Pietrzyk |
PRAM - Pointer Jumping - Brents
Theorem |
CLR, Kap 30 |
08.06. 16:30 | 26.07. 15:00 |
| 6 | Kui |
Chang |
Schnelle Fourier-Transformation |
CLR - Kap 32 |
08.06. 17:00 | 27.07. 10:00 |
| 7 |
Johannes |
Aumüller |
Primzahltests |
CLR - Kap 33 |
15.06. 16:00 | 27.07. 11:00 |
| 8 |
Stefan |
Feldkord |
Knuth Morris Pratt-Pattern
Matching |
CLR - Kap 34 |
15.06. 16:30 | 27.07. 13:00 |
| 9 |
Frank |
Poschner |
Konvexe Hülle |
CLR - Kap 35 |
15.06. 17:00 | 27.07. 14:00 |
| 10 | Tobias |
Kenter |
Sweep-Line Algorithmus zur
Berechnung von Voronoi-Diagrammen |
nach Absprache |
22.06. 16:00 | 27.07. 15:00 |
| 11 | Sascha |
Lutters |
Approximationsalgorithmus
für das Problem des Handlungsreisenden |
CLR |
22.06. 16:30 | 27.07. 16:00 |
Anmeldung nicht mehr
möglich
Anmeldungszeitrum- bis zum Freitag, 15.04.2005, 9 Uhr, in FU.116 (Beethoven/Disko)
- per E-Mail an Christian Schindelhauer
Termine
- 1. Abteilung Freitag, 9-11 Uhr, FU.116, Christian
Schindelhauer
- 2. Abteilung Mittwoch, 16-18 Uhr, F1.310, Klaus Volbert (ab
27.04.2005)
Vorträge
Die Teilnehmer werden in diesem Seminar zwei Vorträge zum
gleichen Thema halten. Der erste Vortrag findet wenige Wochen nach
Themenvergabe statt und dauert 15 Minuten. In diesem Vortrag
erläutert der Teilnehmer kurz die Problemstellung, die
Literaturlage und das weitere Vorgehen.
Der zweite Vortrag (45 Minuten) findet in einem Blockseminar
am Ende des
Semesters statt. Dieser ist entscheidend für die Bewertung der
erfolgreichen Teilnahme. Zur Unterstützung des Vortrags gibt der
Student eine kurze 5-10 seitige schriftliche Zusammenfassung
heraus. Diese ist zwei Wochen vor dem Vortragstermin einzureichen.
Literatur
Dieses Seminar behandelt Themena aus dem Buch CLR: "Introductions to Algorithms", Cormen, Leiserson, Rivest, 1998, MIT-Press/McGraw-Hill.Letzte Änderung: 17.07.2005