Praktikum Algorithmentechnik

Werkzeugentwicklung für die Routenplanung

Die Berechnung optimaler Routen ist ein aktuelles Forschungsthema der Algorithmik

In der Routenplanung werden Straßen- und Bahnnetze üblicherweise durch gewichtete Graphen reprasentiert. Mit Dijkstras Algorithmus kann in einfacher Weise eine optimale Route berechnet werden. Für realistische Problemgroßen ist Dijkstras Algorithmus jedoch viel zu langsam.

In den letzten Jahren hat die Forschung auf dem Gebiet der Routenberechnung große Fortschritte erzielt. Aktuelle Algorithmen besitzen gegenüber Dijkstras Algorithmus eine mehr als 1000-mal kürzere Rechenzeit. Der Lehrstuhl Algorithmik II ist auf diesem Gebiet eine weltweit führende Forschungsgruppe.

Was soll in diesem Praktikum passieren?

Beim Algorithmenentwurf ist es hilfreich, das Verhalten von Datenstrukturen und Algorithmen bis zu einem gewissen Grad beobachten zu können. Hierbei helfen Visualisierungen. Des weiteren stellen sich auch bei der graphischen Darstellung von Landkarten aus Rohdaten durchaus interessante algorithmische Probleme. Dazu passen auch die folgenden möglichen Themen:

    • Performante Visualisierung von Straßennetzwerken und -daten
    • Visualisierung von Algorithmenverhalten, z.B. von Suchräumen, Zwischenzuständen,...
    • Paralleles Rendering von Landkarten aus Rohdaten mit intelligenter Verteilung auf mehrere Prozessoren

Vorraussetzungen

    • Interesse und solide Kenntnisse über Algorithmen und Datenstrukturen
    • Gute Programmierkentnisse in C++

Organisatorisches

Das erste Treffen findet Donnerstag, den 30. April, um 14:00 Uhr im Raum 236 im Informatikhauptgebäude am Fasanengarten statt.

Bitte möglichst frühzeitig per Email bei Dennis Luxen oder anmelden.