Institut für Theoretische Informatik, Algorithmik

Bachelor-/Masterarbeiten, Hiwi-Stellen

Offene Hiwi-Stellen

Offene Bachelor- und Masterarbeiten

Die hier aufgeführten Themenbereiche decken den Großteil der Forschungsthemen am Lehrstuhl ab. Es gibt (fast) immer aktuelle, konkrete Themen für Abschlussarbeiten in den genannten Bereichen. Interessierte Studierende sollten sich an die jeweils genannten Mitarbeiter wenden.

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: Sascha Gritzbach, M.Sc., Matthias Wolf, M.Sc.

Graph Layouts und Graphrepräsentationen

Graph Layouts beschäftigen sich mit der geometrischen oder kombinatorischen Repräsentation von Graphen und Netzwerken. Die Anwendungen reichen von Visualisierungen von Graphen für menschliche Betrachter:innen über Bioinformatik bis zu Layouts integrierter Schaltkreise. Aus wissenschaftlicher Sicht bietet das Gebiet ein breites Spektrum an Themen für Abschlussarbeiten, von theoretischen Betrachtungen (z.B. Graphzerlegungen und -färbungen, Existenz von Zeichnungen oder Algorithmen mit gewissen Eigenschaften) bis hin zu praxisnahen Fragestellungen, die konkrete Anforderungen einer Anwendung modellieren und durch Anpassung etablierter Algorithmen oder Entwicklung neuer Techniken lösen sollen.

Ansprechpartner:innen: Paul Jungeblut, M.Sc., Laura Merker, M.Sc.

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: Jonas Sauer, M.Sc. und Tim Zeitz, M.Sc.

Abgeschlossene Bachelor- bzw. Masterarbeiten und Dissertationen