Software-Projektpraktikum WS2021 (B.Sc. Informatik)
Algorithmic Battle
Kurzzusammenfassung
In diesem Praktikum treten mindestens 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.Aufbau
Das Softwarepraktikum findet semesterbegleitend während der Vorlesungszeit statt und endet mit dieser. Die Teilnehmer werden bei dem ersten Treffen in zwei bis drei gleich große Gruppen eingeteilt, in denen diese bis zum Ende des Praktikums bleiben. Jede dieser Gruppen soll im Verlaufe des Semesters mehrere, meist schwere Entscheidungs- bzw. Optimierungsprobleme lösen und für diese möglichst schwere Instanzen variabler Größe erstellen. Diese Probleme werden jeweils nach der Bearbeitung des jeweils vorherigen Problems bekanntgegeben. Programmiersprachen und Werkzeuge dürfen dafür beliebig gewählt und kombiniert werden. Neben eigenen Implementierungen dürfen auch vorgefertigte Programme verwendet werden. Es gibt in der Regel keine Einschränkung in der Wahl der Bibliotheken, mit Ausnahme einzelner Aufgaben.Mit Ausnahme der nullten Aufgabe hat jede Gruppe in der Regel zwei Wochen Zeit um eine Aufgabe vollständig zu bearbeiten. Jede Woche gibt es Zwischen- oder Abschlusstreffen. In den Zwischentreffen tauschen sich die Assistenten mit den Studierenden über den aktuellen Stand aus und beantworten Fragen. Bei den Abschlusstreffen stellen zwei zufällig ausgewählte Studierende einer Gruppe die Ergebnisse vor und gehen auf Fragen ein. Hierfür ist ein freier Vortrag ausreichend, wir empfehlen mindestens die später beschriebene Dokumentation hinzuzuziehen. Es besteht jeweils Anwesensheitspflicht.
Zu Beginn jeder Aufgabe erhalten die Studierenden eine ausführliche Aufgabenbeschreibung, welche das neue Problem einführt. Aufgabe beider Gruppen ist es anschließend einen Solver und einen Generator zu schreiben. Es gewinnt die Gruppe, welche die größten Instanzen innerhalb eines Zeitlimits löst.
Der Generator soll für eine gegebene Zahl n eine Instanz der Größe bis n erzeugen, welche für die andere Gruppe möglichst schwer zu lösen sein soll. Hierbei ist die Strategie der anderen Gruppe natürlich nicht bekannt, daher bietet es sich an Instanzen zu generieren, welche durch Solver, die nicht auf diese Art von Instanz spezialisiert sind, schwer zu lösen sind. Zusätzlich zu der Instanz soll auch ein Zertifikat erzeugt werden, das eine gültige Lösung für die generierte Instanz darstellt. Dieses dient als Maßstab für die zu erzeugende Lösung: Eine Lösung der anderen Gruppe ist nur gültig, wenn Sie mindestens so gut wie die des Zertifikats ist. Das Zertifikat wird der anderen Gruppe selbstverständlich nicht zur Verfügung gestellt.
Der Solver bildet das Gegenstück zum Generator und soll die Instanzen der anderen Gruppe möglichst schnell korrekt lösen und ein Zertifikat für die Lösung ausgeben. Die Lösung sollte so gut wie möglich sein um zu garantieren, dass die Zertifikatslösung nicht besser ist.
Wir stellen an Code für jede Aufgabe jeweils folgendes bereit: Einen Parser, der überprüft, ob eine gegebene Instanz wohlgeformt ist, einen Verifier, der überprüft, ob ein gegebenes Zertifikat eine gültige Lösung für eine Instanz darstellt, das framework, in dem der Solver und Generator beider Gruppen für ein Battle eingebettet werden sowie einen primitiven Dummy-Solver und einen Dummy-Generator, welche extrem simple, aber gültige Instanzen für das Problem erzeugen.
Bei jedem Zwischentreffen erwarten wir bereits einen funktionierenden Prototypen der Software, der das entsprechende Problem einlesen und lösen kann. Dieser muss zu diesem Zeitpunkt noch nicht optimiert sein oder besonders gute Ergebnisse liefern.
Lernziele des Praktikums
Das Praktikum soll dazu dienen, die algorithmische Denkweise weiter zu verfeinern und neue Techniken und Anregungen für ungewöhnliche Lösungsansätze bieten. Dabei werden auch wichtige praxisbezogene Fähigkeiten erlernt: Von der Kollaboration an einem Softwareprojekt in einer größeren Gruppe, über Versionierung, Dokumentation und gute Codestandards machen die Teilnehmer des Praktikums insgesamt zu alltagstauglicheren Informatiker*Innen.Vorraussetzungen
Vorraussetzungen sind algorithmisches Denken sowie Grundkenntnisse aus Datenstrukturen und Algorithmen. Hilfreich, aber nicht notwendig sind Kenntnisse in linearer Programmierung und Vertrautheit mit Reduktionen sowie randomisierten Algorithmen. Unser Framework basiert auf Linux. Insbesondere Teilnahme mit einem Windowssystem wird nicht unterstützt und geschieht auf eigene Gefahr.Programmiersprachen, Docker, VMs
Ein Bewertungskriterium für das Praktikum ist die Performance der Software in Form von Laufzeitkomplexität und Speicher, sprich: Welche Gruppe die andere besiegen kann. Wir empfehlen, effiziente Programmiersprachen wie zum Beispiel C, C++ oder Rust zu verwenden, empfehlen aber sich auf eine Sprache zu einigen, mit der möglichst viele Gruppenmitglieder arbeiten können. Wir erwarten nicht, dass diese Programmiersprachen bereits gut beherrscht werden, aber das für diese eigenständig das nötige Verständnis angelernt wird.Der Code aller Gruppen wird auf unserer Infrastruktur abgekapselt ausgeführt. Wir erwarten, dass uns für jede Aufgabe ein Docker-Image bereitsgestellt wird, das "Out-of-the-box" funktioniert.
Das erlaubt einerseits eine freie Wahl (und Mischung) von Programmiersprachen, Bibliotheken etc. für Generator und Solver und erlaubt uns, auf einfache Art und Weise den Code mit Speicher- und Zeitrestriktionen zu versehen. Netzwerkverbindungen nach außen unterbinden wir nach bauen des Containers.
Da wir die Battles automatisiert ausführen, erwarten wir, dass sich bei dem Aufbau des directory trees an unsere Vorgaben gehalten wird, die wir seperat bekanntgegeben.
Dokumentation und Codestandards
Wir möchten gerne nachvollziehen können, welche Ideen in die Umsetzung von dem Code geflossen sind. Daher ist zum Tag der finalen Abgabe ein .pdf-Dokument abzugeben, in welchem dokumentiert wird, welche Ansätze für den Generator und Solver ausprobiert wurden, selbst wenn sich diese in der Praxis als nicht sehr nützlich erwiesen haben. Es ist zu dokumentieren, welche Literatur oder sonstige Quellen zu Rate gezogen wurden. Die Person, welche die Dokumentation schreibt, wechselt zwischen allen Gruppenmitgliedern durch. Es ist außerdem klar erkennbar anzugeben, welche Person welche Arbeit in der jeweiligen Woche vollbracht hat. Dieses wird dadurch sichergestellt, dass jede Person der in der Woche zuständigen Dokumentationsperson kurz schriftlich mitteilt, was er oder sie getan hat.Beim Erstellen von des Codes ist ein sauberes Vorgehen wichtig, da in späteren Aufgaben vermutlich Code recyclet wird. Zu Beginn sollte eine sinnvolle Software- und Ordnerstruktur konzipiert und die Best Practices und Codestandards für die gewählten Programmiersprache eingehalten werden. Insbesondere soll der Code in einem sinnvollen Maß dokumentiert werden.
Bei jedem Battle sollen zwei von uns an dem Tag ausgewählte Mitglieder einer Gruppe eine kurze Präsentation halten, in der diese das Vorgehen der Gruppe für die entsprechende Aufgabe vortragen. Wir erwarten, dass jedes Mitglied einen Überblick über den Stand und die Vorgehensweisen der eigenen Gruppe hat und die Vorgehensweise der Gruppe wiedergeben kann.