 Lecture
SS 2011: Algorithm Theory
Instructors
Stefan Göller
MZH 3100
Universität Bremen
Stefan Edelkamp
Am Fallturm 1, Raum 2.62
Universität Bremen
When? Do. 12-16 Uhr (V/Ü)
Where? MZH 4194
Module 602 (Algorithmen- und Komplexitätstheorie), 6 ECTS
Main Lecture Page
Algorithm Theory
Content (German)
Diese Vorlesung befasst sich mit dem Entwurf und der Analyse von Algorithmen.
Einerseits werden Datenstrukturen untersucht mit Hilfe derer sich
bekannte Algorithmen (wie z.B. Kruskals Algorithmus) effizienter
realisieren lassen.
Andererseits werden für konkrete Probleme aus der Informatik Algorithmen entworfen, deren Korrektheit bewiesen und ihre Laufzeit analysiert.
Themen u.a. :
- Schnelle Sortiertverfahren,
- Zeichenkettensuche
(Automaten- und Bitvektor-basiert, Suffix-Bäume und Arrays, Approximativ),
- Cuckoo-Hashing, Perfektes Hashing,
- Strassens Matrixmultiplikation,
- Binomial Heaps, Fibonacci Heaps, Pairing Heaps, Relaxed Weak Queues,
- Splay Trees, Random Search Trees, Planares Separatortheorem,
- Luby's Algorithmus, Millers Primzahltest,
- Parallele Algorithmen: Präfixsumme, Euler-Touren, Listranking,
- Dreifärbung von Ringen.
Es sind außer mathematischer Fingerfertigkeit keine speziellen Vorkenntnisse erforderlich.
Exams (German)
Die Vorlesung kann entweder als mündliche Prüfung oder als Übung mit Fachgespräch geprüft werden. Um für das Fachgespräch zugelassen zu werden, müssen mindestens 50% aller möglichen Punkte der Übungsblätter erreicht werden.
References
Publications in International Conferences and Journals.
|