Graphsuch-SpieleModulbeschreibung #40110 / Version 1
- 3 LP
- Portfolioprüfung
- Benotet
- Winter- und Sommersemester
- Englisch, Deutsch
Diese Modulbeschreibung gilt nicht im aktuellen Semester (WiSe 2026/27).
| Modul / Version | #40110 / #1 |
|---|---|
| Gültigkeit | SS 2014 – WS 2018/19 |
| Verfügbare Sprache(n) | Deutsch |
| Leistungspunkte | 3 |
| Modulverantwortliche*r | Kreutzer, Stephan |
| Benotung | Benotet |
| Prüfungsform | Portfolioprüfung |
| Lehrsprache(n) | Englisch, Deutsch |
Zugehörigkeit
| Fakultät | Fakultät IV |
|---|---|
| Institut | Institut für Softwaretechnik und Theoretische Informatik |
| Fachgebiet | 34352200 FG Logik und Semantik (LaS) |
Kontakt
| Sekretariat | TEL 7-3 |
|---|---|
| Ansprechpartner*in | Pilz, Jana |
| E-Mail-Adresse | stephan.kreutzer@tu-berlin.de |
| Webseite | http://www.las.tu-berlin.de |
Lernergebnisse
- 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.
Lehrinhalte
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.
Modulbestandteile
Pflichtbereich
Die folgenden Veranstaltungen sind für das Modul obligatorisch:
| Lehrveranstaltungen | Art | Nummer | Turnus | Sprache | SWS | VVZ |
|---|
Arbeitsaufwand und Leistungspunkte
Lehrveranstaltungsunabhängiger Aufwand
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-und Nachbereitung | 15 | 4 h | 60 h |
| 90 h | |||
Der Aufwand des Moduls summiert sich zu 90 Stunden. Damit umfasst das Modul 3 Leistungspunkte.
Beschreibung der Lehr- und Lernformen
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.
Voraussetzungen für die Teilnahme / Prüfung
Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:
Interesse an der Theoretischen Informatik
Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:
Dieses Modul hat keine Prüfungsvoraussetzungen.
Abschluss des Moduls
| Benotung | Benotet |
|---|---|
| Prüfungsform | Portfolioprüfung |
| Art der Portfolioprüfung | 100 Punkte insgesamt |
| Sprache | Englisch, Deutsch |
Prüfungselemente
| Name | Punkte/Gewicht | Kategorie | Dauer/Umfang |
|---|---|---|---|
| Paper | 50 | schriftlich | ca. 15 Seiten |
| Talk | 50 | mündlich | ca. 20 Minuten |
Dauer des Moduls
Für Belegung und Abschluss des Moduls ist folgende Semesteranzahl veranschlagt: 1 Semester.
Dieses Modul kann in folgenden Semestern begonnen werden: Winter- und Sommersemester.
Maximale teilnehmende Personen
Die maximale Teilnehmerzahl beträgt 14.
Anmeldeformalitäten
Die Information erfolgt über unsere Webseite http://www.las.tu-berlin.de.
Literaturhinweise, Skripte
Skript in Papierform
nicht verfügbar
Skript in elektronischer Form
nicht verfügbar
Empfohlene Literatur
- Originalartikel
Zugeordnete Studiengänge
Dieses Modul findet in keinem Studiengang Verwendung.
Sonstiges
Das Seminar wird als Blockveranstaltung am Ende des Semesters angeboten.