Heinz Nixdorf Institut
Universität Paderborn
Algorithmen und Komplexität

Home

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

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.

Erstellt: 05.04.2005
Letzte Änderung: 17.07.2005