Software-Projektpraktikum WS2019
Algorithmic Battle
Personen:
Inhalt
In diesem Praktikum treten zwei Teams von Studierenden gegeneinander an.
Jedes Team soll zum einen für ein vorgegebenes Problem schwierige Instanzen generieren,
und zum anderen die schwierigen Instanzen des 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,
Vertrautheit mit Reduktionen als auch
Programmiererfahrung in schnellen Programmiersprachen wie C oder Rust.
Material
Ablauf
Es finden mehrere Battles im Laufe des Semesters statt.
Des weiteren wird es regelmäßige Meetings geben.
