Zum Inhalt springen
Technische Universität Berlin English
Vorlesungsverzeichnis und Modultransfersystem

Graphsuch-SpieleModulbeschreibung #40110 / Version 1

← Zur Modulseite English version
Diese Modulbeschreibung gilt nicht im aktuellen Semester (WiSe 2026/27).
Modul / Version#40110 / #1
GültigkeitSS 2014 – WS 2018/19
Verfügbare Sprache(n)Deutsch
Leistungspunkte3
Modulverantwortliche*rKreutzer, Stephan
BenotungBenotet
PrüfungsformPortfolioprüfung
Lehrsprache(n)Englisch, Deutsch

Zugehörigkeit

FakultätFakultät IV
InstitutInstitut für Softwaretechnik und Theoretische Informatik
Fachgebiet34352200 FG Logik und Semantik (LaS)

Kontakt

SekretariatTEL 7-3
Ansprechpartner*inPilz, Jana
E-Mail-Adressestephan.kreutzer@tu-berlin.de
Webseitehttp://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.

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.

Modulbestandteile

Pflichtbereich

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

LehrveranstaltungenArtNummerTurnusSpracheSWSVVZ

Arbeitsaufwand und Leistungspunkte

Lehrveranstaltungsunabhängiger Aufwand

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

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

BenotungBenotet
PrüfungsformPortfolioprüfung
Art der Portfolioprüfung100 Punkte insgesamt
SpracheEnglisch, Deutsch

Prüfungselemente

NamePunkte/GewichtKategorieDauer/Umfang
Paper50schriftlichca. 15 Seiten
Talk50mündlichca. 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.