Informationen für Studierende
Hiwi-Stellen
Suchst du nach einer Hiwi-Stelle mit algorithmischem Bezug? Dann schreib uns gerne an. Es kann gut sein, dass wir deine Unterstützung gut gebrauchen können; sowohl in der Lehre (zum Beispiel zur Korrektur von Übungsblättern) als auch in der Forschung (zum Beispiel als Scientific Programmer).
Vorlagen
Vorlagen für Ipe-Präsentationen oder eine Abschlussarbeit findet ihr hier.
Abschlussarbeiten
Bei Interesse an einer algorithmischen Bachelor- oder Masterarbeit, gerne einfach bei uns melden. Wir haben meistens verschiedene Themen auf Lager, auch wenn diese hier nicht explizit aufgeführt sind.
Algorithmen für Energienetze
Die Energieinformatik ist ein junges Forschungsfeld an der Schnittstelle von (u.a.) Elektrotechnik, Informatik und den Wirtschaftswissenschaften. Wir betrachten aus realen Anwendungen motivierte Optimierungsprobleme, die sich graphentheoretisch modellieren lassen. Beispiele sind die Erweiterung von Stromnetzen durch Trassenneubau oder durch Platzierung von Kontrolleinheiten, sowie die Verkabelung von Windfarmen. Viele dieser Probleme sind NP-schwer, sodass unser Interesse nicht nur in theoretischen Fragestellungen liegt sondern auch in heuristischen Lösungsverfahren, die experimentell evaluiert werden. Regelmäßig bieten wir Abschlussarbeiten auch als Kooperation mit anderen Arbeitsgruppen an, beispielsweise mit Kollegen vom Institut für Automation und angewandte Informatik (IAI).
Ansprechpartner: Max Göttlicher
Routenplanung und Kürzeste-Wege-Algorithmen
Navigation in Verkehrsnetzen ist ein alltägliches Problem. Hierbei modelliert man das Netzwerk üblicherweise als gewichteten Graphen. Legt man zum Beispiel Reisezeit als Kantenmetrik zugrunde, lassen sich mit diesem Ansatz schnellste Routen berechnen. Dijkstras wohlbekannter Algorithmus aus dem Jahre 1959 findet die gewünschte Route, allerdings sind Verkehrsnetze so groß (das Straßennetzwerk von West- und Mittel-Europa besteht aus ca. 45 Millionen Straßensegmenten), dass der klassische Ansatz zu lange für eine Anfrage braucht. Desweiteren findet dieser Ansatz nur eine einzige Route. Zur Unterstützung von gemischten Verkehrsnetzen, die zum Teil einem Fahrplan unterliegen (Auto, Zug, Fahrrad, Fußwege, …), die Einbeziehung von aktuellen und historischen Stauinformationen, die Abwägung mehrerer Kriterien (Reisezeit, Preis, Energieverbrauch, …) sind erweiterte Modellierungen nötig. Um zugleich Benutzerinteraktivtät oder server-basierte Systeme mit vielen Millionen Anfragen pro Tag zu unterstützen, ist die Entwicklung von Beschleunigungstechniken für Dijkstra's Algorithmus Gegenstand aktueller Forschung. Diese reichern in einem Vorverarbeitungsschritt das Netzwerk mit Zusatzinformationen an, um anschließend die Berechnung von kürzesten Wegen zu beschleunigen.
Wir bieten in diesem Themenfeld Bachelor- und Masterarbeiten sowohl für theoretische Untersuchungen als auch für die praktische Umsetzung an, die den Algorithmenentwurf um Implementierung und ausführliche experimentelle Evaluation auf realistischen Datensätzen ergänzt.
Ansprechpartner: Adrian Feilhauer, Michael Zündorf