Graph Searching GamesModule description #40110 / Version 1
- 3 CP
- Portfolio examination
- Graded
- Winter and summer semester
- English, German
This module description is not valid in the current semester (Winter semester 2026/27).
| Module / Version | #40110 / #1 |
|---|---|
| Validity | SS 2014 – WS 2018/19 |
| Available language(s) | German |
| Credit points | 3 |
| Person responsible for the module | Kreutzer, Stephan |
| Grading | Graded |
| Exam format | Portfolio examination |
| Language(s) of instruction | English, German |
Affiliation
| Faculty | Fakultät IV |
|---|---|
| Institute | Institut für Softwaretechnik und Theoretische Informatik |
| Academic chair | 34352200 FG Logik und Semantik (LaS) |
Contact
| Office | TEL 7-3 |
|---|---|
| Contact person | Pilz, Jana |
| E-mail address | stephan.kreutzer@tu-berlin.de |
| Website | http://www.las.tu-berlin.de |
Learning outcomes
- Fähigkeit, wissenschaftliche, vor allem mathematische Quellen zu lesen und zu verstehen.
- Sich formal korrekt und verständlich auszudrücken.
- Einen publizierreifen mathematischen Text zu produzieren.
- Folien für einen verständlichen Vortrag zu einem mathematischen Thema vorzubereiten.
- Vor einem Fachpublikum einen mathematischen Vortrag zu halten.
- Fertigkeit im Umgang mit LaTeX
-Teilnehmer werden vertraut gemacht in Graphsuch-Spielen und den entsprechenden Maßen der Graph-Verbundenheit.
-Sie werden typische Argumente und Anwendungen der Graphsuche und wichtige Konzepte wie z. B. das der Monotonie verstehen.
- Sich formal korrekt und verständlich auszudrücken.
- Einen publizierreifen mathematischen Text zu produzieren.
- Folien für einen verständlichen Vortrag zu einem mathematischen Thema vorzubereiten.
- Vor einem Fachpublikum einen mathematischen Vortrag zu halten.
- Fertigkeit im Umgang mit LaTeX
-Teilnehmer werden vertraut gemacht in Graphsuch-Spielen und den entsprechenden Maßen der Graph-Verbundenheit.
-Sie werden typische Argumente und Anwendungen der Graphsuche und wichtige Konzepte wie z. B. das der Monotonie verstehen.
Content
Graphsuch-Spiele werden in den letzten Jahrzehnten intensiv studiert. Die ursprüngliche Motivation war es, einen Algorithmus zu konstruieren, der es garantieren würde, einen Höhlenforscher zu finden, der sich in einem Labyrinth der dunklen Höhlen verloren hat und nach einem Ausgang vergeblich sucht. Im schlimmsten Fall läuft er so, als wollte er den Rettern ausweichen. Die Frage ist, wie viele Retter man braucht, um den Forscher zu finden, und welche Routen diese dafür wählen sollen.
In der formaleren Fassung betrachtet man ein Zwei-Spieler-Spiel, das zwischen einem Räuber und einer Polizistenmannschaft gespielt wird. Zu jedem Zeitpunkt besetzt der Räuber einen Knoten und jeder Polizist entweder besetzt auch einen Knoten oder ist außerhalb des Graphen. Das Ziel der Polizisten ist es, den Räuber zu fangen, also mit einem Polizisten den Knoten des Räubers zu besetzen, so dass der Räuber keine Ausweichmöglichkeit hat. Dann gewinnen sie. Kann der Räuber dies unendlich lang vermeiden, gewinnt er. Genaue Regeln für Züge der Spieler und die Bedingung, wann der Räuber gefangen ist, definieren ein Spiel auf einem gegebenen Graphen. Uns wird vor allem die kleinste Anzahl von Polizisten interessieren, die ausreichend ist, um den Räuber zu fangen.
Für viele Spiele induziert eine Gewinnstrategie für k Polizisten eine spezielle Zerlegung des Graphen in kleine Teile, jede der Größe höchstens k, die in einer einfachen Weise miteinander verknüpft sind. Solche Zerlegungen erlauben es, schwere, zum Beispiel NP-vollständige, Probleme auf Graphen in Polynomzeit zu lösen.
In der formaleren Fassung betrachtet man ein Zwei-Spieler-Spiel, das zwischen einem Räuber und einer Polizistenmannschaft gespielt wird. Zu jedem Zeitpunkt besetzt der Räuber einen Knoten und jeder Polizist entweder besetzt auch einen Knoten oder ist außerhalb des Graphen. Das Ziel der Polizisten ist es, den Räuber zu fangen, also mit einem Polizisten den Knoten des Räubers zu besetzen, so dass der Räuber keine Ausweichmöglichkeit hat. Dann gewinnen sie. Kann der Räuber dies unendlich lang vermeiden, gewinnt er. Genaue Regeln für Züge der Spieler und die Bedingung, wann der Räuber gefangen ist, definieren ein Spiel auf einem gegebenen Graphen. Uns wird vor allem die kleinste Anzahl von Polizisten interessieren, die ausreichend ist, um den Räuber zu fangen.
Für viele Spiele induziert eine Gewinnstrategie für k Polizisten eine spezielle Zerlegung des Graphen in kleine Teile, jede der Größe höchstens k, die in einer einfachen Weise miteinander verknüpft sind. Solche Zerlegungen erlauben es, schwere, zum Beispiel NP-vollständige, Probleme auf Graphen in Polynomzeit zu lösen.
Module components
Compulsory area
The following courses are mandatory for this module:
| Courses | Type | Number | Frequency | Language | Hours per week | Course catalog |
|---|
Workload and credit points
Course-independent workload
| Workload description | Multiplier | Hours | Total |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-und Nachbereitung | 15 | 4 h | 60 h |
| 90 h | |||
The workload of the module adds up to 90 hours. The module therefore comprises 3 credit points.
Description of teaching and learning methods
Jeder Teilnehmer bekommt einen wissenschaftlichen Artikel. Man soll sich mit Inhalt und dem Kontext des Artikels auseinandersetzen. Später wird allen eine Teilnehmern ein Vortrag zum jeweiligen Artikel gehalten.
Außerdem muss eine schriftliche Ausarbeitung zum Thema erfolgen.
Der Vortrag und die Ausarbeitung können auf Deutsch oder Englisch gehalten werden.
Außerdem muss eine schriftliche Ausarbeitung zum Thema erfolgen.
Der Vortrag und die Ausarbeitung können auf Deutsch oder Englisch gehalten werden.
Requirements for participation and examination
Desirable prerequisites for participation in the courses:
Interesse an der Theoretischen Informatik
Mandatory requirements for the module examination registration:
This module has no examination requirements.
Completion of the module
| Grading | Graded |
|---|---|
| Exam format | Portfolio examination |
| Type of portfolio examination | 100 points in total |
| Language | English, German |
Test elements
| Name | Points/Weight | Category | Duration/Extent |
|---|---|---|---|
| Paper | 50 | written | ca. 15 Seiten |
| Talk | 50 | oral | ca. 20 Minuten |
Duration of the module
The following number of semesters is estimated for taking and completing the module: 1 semester(s).
This module can be started in the following semesters: Winter and summer semester.
Maximum number of participants
The maximum capacity of participants is 14.
Registration procedures
Die Information erfolgt über unsere Webseite http://www.las.tu-berlin.de.
Recommended reading, lecture notes
Lecture notes
unavailable
Electronic lecture notes
unavailable
Recommended literature
- Originalartikel
Assigned programs
This module is not used in any program.
Miscellaneous
Das Seminar wird als Blockveranstaltung am Ende des Semesters angeboten.