Algorithmentheorie

Link zu Stefan Edelkamps Algorithmenseite

Vortragende: PD Dr. Stefan Edelkamp und Dr. Stefan Göller

K 4 SWS (ECTS: 6), Modulbereich Theorie

Termine

Do von 12:00 - 16:00 MZH 4194

Beschreibung

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, Lubys Algorithmus, Millers Primzahltest, Parallele Algorithmen: Präfixsumme, Euler-Touren, Listranking, Dreifärbung von Ringen. Es sind außer mathematischer Fingerfertigkeit keine speziellen Vorkenntnisse erforderlich.

Prüfungsmodalitäten und Scheinbedingungen

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.