English English

Inhalt

Algorithmen sind ein zentrales Themengebiet der Informatik. Dabei werden häufig verschiedene spannende und interessante Ansätze verwendet, um die zu Grunde liegenden Probleme zu lösen. Beispielsweise können Zufallszahlen helfen, einfache und praktikable Algorithmen zu entwerfen (Randomisierte Algorithmen). In anderen Fällen kennen wir die Eingabe für den Algorithmus zu Beginn der Berechnungen nicht komplett, da die Bestandteile der Eingabe erst nach und nach bekannt werden (Online Algorithmen). Diesen Mangel an Informationen müssen wir bewerkstelligen. Besondere Aufmerksamkeit kommt auch Algorithmen für spezielle Anwendungen zu, wenn wir zum Beispiel auf Graphen oder mit Kommunikationsnetzwerken arbeiten.

In diesem Proseminar betrachten wir Algorithmen, die typisch für die verschiedenen Bereiche sind und die die Verwendung der unterschiedlichen Konzepte gut verdeutlichen. Im Mittelpunkt stehen jeweils Entwurf und Analyse des Verfahrens. Die behandelten Themen erweitern die Inhalte, die im Bachelorstudium betrachtet werden.


Voraussetzungen

Das Proseminar ist geeignet für Studierende der Informatik (oder eines vergleichbaren Studienganges) ab dem 2. Fachsemester.

Organisatorisches

Eine Vorbesprechung zum Proseminar findet am 19. Februar um 16 Uhr im Raum 4017 (Seminarraum des Lehrstuhls, Erweiterungsbau 1, Erdgeschoss) statt.

Die Vorträge finden an den unten aufgelisteten Terminen jeweils von 15 bis 17 Uhr 15 in unserem Seminarraum (Raum 4017) statt.

Es gibt folgende Deadlines:

Konzeptspätestens 8 Wochen vor Vortrag
Vorabfolienspätestens 5 Wochen vor Vortrag
fertige Folienspätestens 2 Wochen vor Vortrag
Ausarbeitungspätestens 3 Wochen nach Vortrag

Übersicht über die Themen und Vortragstermine:

VortragsterminThemen
16.5.Hashing
Closest Pair of Points
Finding a Global Minimum Cut
6.6. Finding a Maximal Independent Set
Game Tree Evaluation
Minimal Spanning Tree
27.6.List-Accessing (det.)
List-Accessing (rand.)
Paging (det.)
4.7. Paging (rand.)
Finding Disjoint Paths
Selfish Routing
11.7.Distributed Vertex Coloring
Distributed Sorting
Consensus / Byzantine Agreement
18.7.Dynamic Programming: Interval Scheduling
Approximating Metric TSP
FPTAS for the Knapsack Problem


Kontakt

Oliver Göbel: goebel (at) cs.rwth-aachen.de

Andreas Tönnis: toennis (at) cs.rwth-aachen.de