Sofwareprojektpraktikum: Cops'n'Robber – Suchspiele auf Graphen, Zerlegungen und Zusammenhang

Kontakt

Telefon

work
+49 241 80 21716

E-Mail

E-Mail

Kontakt

Telefon

work
+49 241 80 21702

E-Mail

E-Mail
 
 

Sofwareprojektpraktikum: Cops'n'Robber

Das “Cops’n’Robber”-Spiel ist ein abstraktes Spiel, bei dem sich die Spieler auf den Knoten eines Graphen bewegen und eine feste Anzahl von “Cops” einen “Robber” zu fangen versucht.

Suchspiele auf Graphen, von denen das “Cops’n’Robber”-Spiel das wichtigste ist, erlauben es, den globalen Zusammenhang von Graphen und damit letztlich die Robustheit von Netzwerktopologien zu messen. Eng damit zusammen hängt die Zerlegbarkeit von Graphen in kleine Teile, auf der wiederum viele dynamische Programmierungsalgorithmen beruhen.

Aufgabe


In diesem Praktikum sollen effiziente Strategien für die Spieler im Cops’n’Robber Spiel implementiert werden. Zum Abschluss des Praktikums werden die Strategien der einzelnen Gruppen gegeneinander in einem Wettbewerb antreten.

Gebiet und Voraussetzungen


Inhaltlich ist das Praktikum im Bereich Graphalgorithmen angesiedelt. Gute Kenntnisse im Bereich Datenstrukturen und Algorithmen werden vorausgesetzt. Die Implementierung erfolgt in Python, möglicherweise mit C++-Komponenten. Kenntnisse dieser Sprachen werden ebenfalls erwartet.