WPP1: Praktische Anwendung von Algorithmen und parallelem Rechnen

Master Informatik
1. Semester

Termine und Allgemeines für das Wintersemester 2023/2024

Ziel: Es sollen die Inhalte der Module EAL, WSY und PAR 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.

zurück zur Startseite