WPP1: Praktische Anwendung von Algorithmen und parallelem Rechnen

Master Informatik
1. Semester

Termine und Allgemeines für das Wintersemester 2025/2026

Ziel: Es sollen die Inhalte der Module EAL, WSY und PAC vertieft und praktisch angewendet werden. Dazu wird eine konkrete Problemstellung aus einem der genannten Bereiche unter Betreuung eines Lehrenden eigenständig in Gruppen bearbeitet. Die Studierenden arbeiten sich in das Themengebiet ein und erstellen einen Projektplan. Erarbeitete Lösungswege setzen sie praktisch um und dokumentieren dabei den Projektverlauf.

Arbeitsaufwand: Das Modul WPP1 ist mit fünf Leistungspunkten (CP) in der Prüfungsordnung angegeben. Laut der Verordnung zur Regelung des Näheren der Studienakkreditierung in Nordrhein-Westfalen (Studienakkreditierungsverordnung – StudakVO) vom 25.01.2018, Paragraph 8 Leistungspunktesystem, Satz (1) entspricht ein Leistungspunkt einer Gesamtarbeitsleistung von 25 bis höchstens 30 Zeitstunden. Insgesamt ergibt sich also ein Arbeitsaufwand von 125 Stunden im Semester. Diese verteilen sich bei 15 Wochen Vorlesungszeit im Semester auf sechs Stunden pro Woche, sodass 35 Stunden zum Erstellen des Projektplans, des Vortrags und der schriftlichen Ausarbeitung verbleiben.

Organisatorisches: Sie müssen alle zwei Wochen über den Stand Ihrer Arbeit einen Zwischenbericht abgeben oder in der Veranstaltung berichten. Zum Abschluss des Projekts gibt es einen gemeinsamen Pflichttermin für alle Projektteilnehmer:innen, an dem Vorträge mit ca. 30 Minuten Länge zu den Projekten gehalten werden.

Weiterhin muss jede Projektgruppe einen Abschlussbericht abgeben. Der Projektbericht soll in Form eines wissenschaftlichen Artikels in englischer Sprache verfasst werden. Er soll mit LaTeX verfasst werden und mindestens zwei Seiten Text pro teilnehmenden Studierenden enthalten. Die Vorlagen für die Artikel finden Sie unter dem folgenden Link: https://www.ieee.org/conferences/publishing/templates.html

Sie können die Plattform IDE3 des Fachbereichs nutzen. Dort stehen unter anderem Gitlab, Mattermost und Etherpad zur Verfügung, die die Arbeit im Team vereinfachen können.

Projekt 1: Routenplanung auf großen Karten

Heute sind große Karten zur Routenplanung im Internet frei verfügbar, z.B. von Open Street Map. In diesem Projekt soll es darum gehen, solche Karten in den Computer einzulesen, aufzubereiten, Routen zu planen, diese Routen in geeigneter Form auszugeben sowie die Algorithmen und Datenstrukturen zu analysieren.

Um die Routenplanung auch auf sehr großen Karten und auch auf Computern mit beschränkten Hardware-Ressourcen durchführen zu können, sind Datenstrukturen notwendig, die externen Speicher wie Festplatten oder SD-Karten nutzen.

Projekt 2: Reinforcement Learning bei kombinatorischen Spielen

Das von Gerald Tesauro 1992 am IBM's Thomas J. Watson Research Center entwickelte Programm TD-Gammon gilt als eine der größten Erfolgsgeschichten des Reinforcement Learning. Es nutzt nur wenig Wissen über Backgammon und spielt dennoch extrem gut, nahe am Niveau der stärksten Großmeister der Welt. In diesem Projekt wollen wir ein Programm für das Spiel Vier-Gewinnt oder Othello schreiben, das Reinforcement Learning und neuronale Netze nutzt und mit Monte-Carlo-Tree-Search bzw. Minimax vergleicht.

Projekt 3: Visualisierung von Graphalgorithmen

Die Boost-Graph-Library stellt Container bereit, um Graphen zu definieren, und stellt Algorithmen bereit, um Probleme wie »kürzeste Wege« oder »minimaler Spannbaum« sehr effizient zu lösen. Wir wollen in diesem Projekt eine stark vereinfachte Bibliothek entwerfen, die in Modulen wie ALD oder PE2 des Bachelor-Studiengangs Informatik eingesetzt werden kann, um grundlegende Kenntnisse der Programmierung in C++ und Wissen über Graphalgorithmen zu vermitteln.

Außerdem sollen die Algorithmen visualisiert werden, es soll also möglich sein, Graphen aus einer Datei zu lesen, einen Algorithmus auszuwählen und schrittweise anzeigen zu lassen. Ein schönes Beispiel dafür ist das Projekt ViGrAl oder die Web-Seite Data Structure Visualizations der University of San Francisco.

Projekt 4: Kombinatorische Optimierung

In diesem Projekt sollen Sie die verschiedenen Ansätze zur Lösung des Traveling-Salesman-Problems (TSP) kennenlernen und implementieren. Durch die Anwendung von lokaler Suche, dynamischer Programmierung und ganzzahliger linearer Programmierung soll ein tieferes Verständnis für die Herausforderungen und Möglichkeiten der Problemlösung in der Informatik entwickelt werden. Die Tests mit Beispielen aus der TSP-LIB ermöglichen eine praktische Evaluierung der Algorithmen und deren Vergleich hinsichtlich Effizienz und Genauigkeit.

Projekt 5: Parallel Single-Source-Shortest-Path

Ziel des Projekts ist das Kennenlernen sowie die Implementierung und Analyse paralleler Algorithmen zur Lösung des Single-Source-Shortest-Path-Problems (SSSP) in C++. Zunächst sind verschiedene parallele SSSP-Algorithmen (wie Delta-Stepping, Crauser-Kainer-Ansatz, Radius-Stepping) zu recherchieren. Dann wählen Sie mindestens zwei unterschiedliche Ansätze aus und implementieren diese in C++ unter Verwendung geeigneter Bibliotheken wie OpenMP, MPI, TBB und OpenCL. Schließlich erstellen Sie eine Testumgebung mit zufällig generierten und realen Graphen und vergleichen die Algorithmen anhand definierter Metriken wie Laufzeit, Skalierung und Ressourcenverbrauch.

Projekt 6: Parallel planar Convex-Hull

Ziel des Projekts ist das Kennenlernen sowie die Implementierung und Evaluation paralleler Algorithmen zur Berechnung der konvexen Hülle für eine Menge von 2D-Punkten. Es soll die Performance gegenüber sequentiellen Algorithmen verglichen und die Skalierbarkeit auf Multicore- oder verteilten Systemen analysiert werden.

Die konvexe Hülle einer Punktmenge ist die kleinste konvexe Menge, die alle Punkte enthält. Klassische Algorithmen sind Graham-Scan mit Laufzeit O(n log n), Jarvis-March mit Laufzeit O(nh), wobei h die Anzahl der Punkte auf der Hülle ist, sowie ein Divide-and-Conquer-Ansatz mit Laufzeit O(n log n). Für eine parallele Umsetzung bietet sich insbesondere der Divide-and-Conquer-Ansatz an, da sich die Punktmenge ganz natürlich in Teilmengen unterteilen lässt.

zurück zur Startseite