Moses - Algorithmic Graph Structure Theory

Anzeigesprache

Diese Modulbeschreibung gilt nicht im aktuellen Semester.

Die Modulbeschreibung gilt nur für den Zeitraum WS 2015/16 - WS 2019/20. Die Version für das aktuelle Semester (SoSe 2024) finden Sie hier: Modulbeschreibung des SoSe 2024

Modul / Version:
#40321 / #2

Gültigkeit:
WS 2015/16 - WS 2019/20

Standard-Anzeigesprache:
Deutsch/Englisch

Titel des Moduls:
Algorithmic Graph Structure Theory

Leistungspunkte:
6

Modulverantwortliche*r:
Kreutzer, Stephan

Benotung:
benotet

Prüfungsform:
Mündliche Prüfung

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:
Keine Angabe

Lernergebnisse

Students completing the course will understand how structural information about instances to computational problems can be used in the design of efficient algorithms. They will be familiar with basic notions of graph decompositions and the algorithmic techniques facilitated to use this additional information.

Lehrinhalte

Many algorithmic problems on graphs are NP-hard and therefore there is good evidence that no efficient algorithms solving these problems on all graphs exist. Classical examples are routing problems arising e.g. in integrated circuit layout and design, colouring problems in scheduling applications or domination problems in facility location. However, instances to these problems arising in practical applications may have more ”structure“ than general graphs, e.g. instances may be “hierarchical” or “tree-like”. Using this additional structural information may help in designing efficient algorithms for solving problems in instances of this form. A particularly good example are instances which are planar graphs, i.e. graphs that can be drawn without crossing edges. Planar graphs arise for instance in routing applications, as many road or train maps are nearly planar. It turns out that if the input instance is planar, or a tree, then many hard problems become tractable. In this course we will study methods for solving algorithmic problems on restricted classes of graphs. The most important cases will be planar graphs and graph classes defined by the concept of bounded tree-width. We will then extend this to even more general classes of graphs. The focus of this lecture is to introduce the structural properties of graphs that can be employed in the design of efficient algorithms and to present the algorithmic techniques needed for this.

Modulbestandteile

Pflichtteil:

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

Lehrveranstaltungen	Art	Nummer	Turnus	Sprache	SWS	VZ
Algorithmic Graph Structure Theory (Math)	VL	0432 L 675	k.A.	Englisch	4

Arbeitsaufwand und Leistungspunkte

Algorithmic Graph Structure Theory (Math) (VL):

Aufwandbeschreibung	Multiplikator	Stunden	Gesamt
Präsenzzeit	15.0	4.0h	60.0h
Prüfungsvorbereitung	1.0	30.0h	30.0h
Vor-/Nachbereitung	15.0	6.0h	90.0h
			180.0h(~6 LP)

Der Aufwand des Moduls summiert sich zu 180.0 Stunden. Damit umfasst das Modul 6 Leistungspunkte.

Beschreibung der Lehr- und Lernformen

Keine Angabe

Voraussetzungen für die Teilnahme / Prüfung

Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:

Keine Angabe

Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:

Dieses Modul hat keine Prüfungsvoraussetzungen.

Abschluss des Moduls

Benotung

benotet

Prüfungsform

Sprache

Deutsch/Englisch

Dauer/Umfang

30 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

Dieses Modul ist nicht auf eine Anzahl Studierender begrenzt.

Anmeldeformalitäten

Keine Angabe

Literaturhinweise, Skripte

Skript in Papierform

Verfügbarkeit: verfügbar

Skript in elektronischer Form

Verfügbarkeit: verfügbar

Literatur

Empfohlene Literatur
Lecture notes on paper: nein Lectures notes in electronic form: ja Literature: References to additional literature will be given during the lectures.

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.

Studierende anderer Studiengänge können dieses Modul ohne Kapazitätsprüfung belegen.

Keine Angabe

Sonstiges

Keine Angabe