Abschlussarbeiten

Bei Interesse an einer algorithmischen Bachelor- oder Masterarbeit, tragt euch bitte in dieses Formular ein: https://portal.wiwi.kit.edu/forms/form/749 Wir haben meistens verschiedene Themen auf Lager, auch wenn diese hier nicht explizit aufgeführt sind. Es kommt aber manchmal auch zu ausreichend vielen Anfragen, dass wir leider nicht immer eine Abschlussarbeit anbieten können.

Viele Algorithmen schneiden hinsichtlich Laufzeit oder Lösungsqualität auf realistischen Eingaben deutlich besser ab als dies von einer theoretischen Analyse des worst-case zu erwarten wäre. In diesem Kontext versuchen wir besser zu verstehen welche Eigenschaften von Echtwelt-Eingaben, hierfür (beweisbar) verantwortlich sind und versuchen unsere Erkenntnisse für das Design besserer Algorithmen auszunutzen. Typische Techniken in diesem Kontext sind average case Analyse, Techniken aus dem Gebiet parametrisierte Algorithmen und des algorithm engineering. Ansprechpartner sind Thomas, Max und Marcus.

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 und Wendy Yi

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