Software-Projektpraktikum WS2020

Algorithmic Battle

Inhalt

In diesem Praktikum treten zwei oder mehr Teams von Studierenden gegeneinander an. Jedes Team soll zum einen für ein vorgegebenes Problem schwierige Instanzen generieren, und zum anderen die schwierigen Instanzen der gegnerischen Teams lösen. Dieser Wettstreit findet in mehreren Runden für verschiedene Probleme statt.

Geben wir als Problem zum Beispiel Clique vor, so gilt es Graphen zu generieren, bei denen eine maximale Clique sehr schwer zu finden ist. Außerdem soll ein Programm geschrieben werden, welches für möglichst große Graphen des Gegnerteams die maximale Clique findet. Das Team, welches die größeren Instanzen des Gegnerteams innerhalb einer vorgegebenen Zeit lösen kann, gewinnt die entsprechende Runde.

Dabei ist (fast) alles erlaubt: Programmiersprachen und Werkzeuge könnt ihr euch selbst aussuchen. Ihr könnt eigene Algorithmen implementieren oder vorgefertigte Programme wie ILP Solver verwenden. Ihr dürft alle Bibliotheken beliebiger Programmiersprachen verwenden.

Ziel des Praktikums ist es, praktische Erfahrung mit Problemen der theoretischen Informatik zu sammeln, als Team an einem Softwareprojekt zu kollaborieren und dafür nötige Erfahrungen wie Versionskontrolle, Dokumentation und Programmiererfahrungen zu sammeln.

In die Benotung geht nicht nur die erziehlte Punktzahl ein, sondern auch andere Aspekte, wie Organisation, Kreativität und Teamarbeit.

Vorraussetzungen

Vorraussetzungen sind Algorithmisches Denken sowie Grundkenntnisse aus Datenstrukturen und Algorithmen. Hilfreich, aber nicht notwendig wären Kenntnisse in linearer Programmierung und Vertrautheit mit Reduktionen. Unser Framework basiert auf Linux. Insbesondere Teilnahme mit einem Windows System wird nicht unterstützt und geschieht auf eigene Gefahr.

Materialien

Alle Materialien werden im Moodle-Raum der Veranstaltung veröffentlicht.