Moses - Graphsuch-Spiele

Zur Modulseite PDF generieren

Modul / Version
#40110 / #1

Gültigkeit
SS 2014 - WS 2018/19

Verfügbare Sprache(n)
Deutsch

Titel des Moduls
Graphsuch-Spiele

Leistungspunkte
3

Modulverantwortliche*r
Kreutzer, Stephan

Benotung
Benotet

Prüfungsform
Portfolioprüfung

Lehrsprache(n)
Deutsch, Englisch

Zugehörigkeit

Fakultät
Fakultät IV

Institut
Institut für Softwaretechnik und Theoretische Informatik

Fachgebiet
34352200 FG Logik und Semantik

Prüfungsausschuss
Keine Angabe

Kontakt

Sekretariat
TEL 7-3

Ansprechpartner*in
Pilz, Jana

E-Mail-Adresse
stephan.kreutzer@tu-berlin.de

Webseite

http://www.las.tu-berlin.de

Diese Modulbeschreibung gilt nicht im aktuellen Semester.

Die Modulbeschreibung gilt nur für den Zeitraum SS 2014 - WS 2018/19.

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:

Lehrveranstaltungen	Art	Nummer	Turnus	Sprache	SWS	ISIS	VVZ
Dieser Gruppe enthält keine Lehrveranstaltungen

Arbeitsaufwand und Leistungspunkte

Lehrveranstaltungsunabhängiger Aufwand:

Aufwandbeschreibung	Multiplikator	Stunden	Gesamt
Präsenzzeit	15.0	2.0h	30.0h
Vor-und Nachbereitung	15.0	4.0h	60.0h
			90.0h(~3 LP)

Der Aufwand des Moduls summiert sich zu 90.0 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

Benotung

Benotet

Prüfungsform

Portfolioprüfung

Art der Portfolioprüfung

100 Punkte insgesamt

Sprache(n)

Deutsch, Englisch

Prüfungselemente

Name	Punkte	Kategorie	Dauer/Umfang
Paper	50	schriftlich	ca. 15 Seiten
Talk	50	mündlich	ca. 20 Minuten

Notenschlüssel

Keine Angabe

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

Verfügbarkeit: nicht verfügbar

Skript in elektronischer Form

Verfügbarkeit: nicht verfügbar

Literatur

Empfohlene Literatur
Originalartikel

Zugeordnete Studiengänge

Semester:

Zeige auch ausgelaufene Studiengänge und StuPOs

Diese Modulversion wird in folgenden Studiengängen verwendet:

	Studiengang / StuPO	StuPOs	Verwendungen	Erste Verwendung	Letzte Verwendung
Dieses Modul findet in keinem Studiengang Verwendung.

Sonstiges

Das Seminar wird als Blockveranstaltung am Ende des Semesters angeboten.