Skip to content
Technische Universität Berlin Deutsch
Course catalog and module transfer system

Graph Searching GamesModule description #40110 / Version 1

← Module page Deutsche Fassung
This module description is not valid in the current semester (Winter semester 2026/27).
Module / Version#40110 / #1
ValiditySS 2014 – WS 2018/19
Available language(s)German
Credit points3
Person responsible for the moduleKreutzer, Stephan
GradingGraded
Exam formatPortfolio examination
Language(s) of instructionEnglish, German

Affiliation

FacultyFakultät IV
InstituteInstitut für Softwaretechnik und Theoretische Informatik
Academic chair34352200 FG Logik und Semantik (LaS)

Contact

OfficeTEL 7-3
Contact personPilz, Jana
E-mail addressstephan.kreutzer@tu-berlin.de
Websitehttp://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.

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.

Module components

Compulsory area

The following courses are mandatory for this module:

CoursesTypeNumberFrequencyLanguageHours per weekCourse catalog

Workload and credit points

Course-independent workload

Workload descriptionMultiplierHoursTotal
Präsenzzeit152 h30 h
Vor-und Nachbereitung154 h60 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.

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

GradingGraded
Exam formatPortfolio examination
Type of portfolio examination100 points in total
LanguageEnglish, German

Test elements

NamePoints/WeightCategoryDuration/Extent
Paper50writtenca. 15 Seiten
Talk50oralca. 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.