Software-Projektpraktikum WS2019

Algorithmic Battle

Personen:

Peter Rossmanith
Henri Lotze (tcs-teaching@cs.rwth-aachen.de)
Jan Dreier (tcs-teaching@cs.rwth-aachen.de)

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.