Structure and Algorithmic Applications of Directed GraphsModulbeschreibung #40111 / Version 1
- 6 LP
- Mündliche Prüfung
- Benotet
- Winter- und Sommersemester
- Englisch
| Modul / Version | #40111 / #1 |
|---|---|
| Gültigkeit | Seit WS 2014/15 |
| Verfügbare Sprache(n) | Englisch |
| Leistungspunkte | 6 |
| Modulverantwortliche*r | Kreutzer, Stephan |
| Benotung | Benotet |
| Prüfungsform | Mündliche Prüfung |
| Lehrsprache(n) | Englisch |
Zugehörigkeit
| Fakultät | Fakultät IV |
|---|---|
| Institut | Institut für Softwaretechnik und Theoretische Informatik |
| Fachgebiet | 34352200 FG Logik und Semantik (LaS) |
Kontakt
| Sekretariat | EN 25 |
|---|---|
| Ansprechpartner*in | Pilz, Jana |
| E-Mail-Adresse | las-lehre@lists.tu-berlin |
| Webseite | https://www.tu.berlin/las |
Lernergebnisse
Students taking the course will be familiar with the structure theory for directed graphs. They will be able to model real world computational problems as directed graphs, where applicable, and to apply general algorithmic techniques for solving these problems efficiently.
Lehrinhalte
Graphs are a ubiquitous model in mathematics and computer science and many computational and other problems arising in computer science have graph theoretical abstractions.
In the last few decades a very extensive structure theory for graphs has been developed which has proved to be extremely useful in the design of algorithms for NP-hard computational problems.
However, most of this theory applies in particular to undirected graphs and for directed graphs much less is known.
In this course we will cover structural and algorithmic aspects of directed graphs.
In particular, we will cover
- structural decompositions of directed graphs
- algorithmic applications of this structure theory
- combinatorial results such as the Erdos-Posa property and Younger’s conjecture
- routing and flow problems for directed graphs
- disjoint paths problems for directed graphs
- tournaments
- general algorithmic techniques applicable to digraphs
In the last few decades a very extensive structure theory for graphs has been developed which has proved to be extremely useful in the design of algorithms for NP-hard computational problems.
However, most of this theory applies in particular to undirected graphs and for directed graphs much less is known.
In this course we will cover structural and algorithmic aspects of directed graphs.
In particular, we will cover
- structural decompositions of directed graphs
- algorithmic applications of this structure theory
- combinatorial results such as the Erdos-Posa property and Younger’s conjecture
- routing and flow problems for directed graphs
- disjoint paths problems for directed graphs
- tournaments
- general algorithmic techniques applicable to digraphs
Modulbestandteile
Pflichtbereich
Die folgenden Veranstaltungen sind für das Modul obligatorisch:
Arbeitsaufwand und Leistungspunkte
Digraph Structure Theory (Vorlesung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung + Prüfungsvorbereitung | 15 | 4 h | 60 h |
| 90 h | |||
Digraph Structure Theory (Übung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung + Prüfungsvorbereitung | 15 | 4 h | 60 h |
| 90 h | |||
Der Aufwand des Moduls summiert sich zu 180 Stunden. Damit umfasst das Modul 6 Leistungspunkte.
Beschreibung der Lehr- und Lernformen
- Lecture presenting the core material
- tutorials in which examples and exercises are discussed
There will not be regular homework. Instead we will work on and discuss exercises in the tutorials with only occasional extra homework.
- tutorials in which examples and exercises are discussed
There will not be regular homework. Instead we will work on and discuss exercises in the tutorials with only occasional extra homework.
Voraussetzungen für die Teilnahme / Prüfung
Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:
The course is entirely self-contained and all concepts needed will be introduced.
However, this is an advanced course in graph theory covering topics very close to current research. Students taking this course therefore should have a significant interest in graph theory or combinatorics and ideally should have some mathematical maturity, i.e. some experience in combinatorial reasoning.
However, this is an advanced course in graph theory covering topics very close to current research. Students taking this course therefore should have a significant interest in graph theory or combinatorics and ideally should have some mathematical maturity, i.e. some experience in combinatorial reasoning.
Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:
Dieses Modul hat keine Prüfungsvoraussetzungen.
Abschluss des Moduls
| Benotung | Benotet |
|---|---|
| Prüfungsform | Mündliche Prüfung |
| Sprache | 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
Die Prüfungsanmeldung erfolgt über QISPOS
ISIS
ISIS
Literaturhinweise, Skripte
Skript in Papierform
nicht verfügbar
Skript in elektronischer Form
nicht verfügbar
Empfohlene Literatur
Keine empfohlene Literatur angegeben
Zugeordnete Studiengänge
Diese Modulversion wird in folgenden Studiengängen verwendet:
| Studiengang / StuPO | Semester | Studiengangsbereich |
|---|---|---|
| Computer Engineering StuPO 2015 | SoSe 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WiSe 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SoSe 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WiSe 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| Computer Science (Informatik) StuPO 2015 | SoSe 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WiSe 2025/26 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| SoSe 2026 | Studiengebiete › Grundlagen der Informatik / Foundations of Computing | |
| WiSe 2026/27 | Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing | |
| Elektrotechnik StuPO 2015 | SoSe 2025 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
| WiSe 2025/26 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| SoSe 2026 | Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing | |
| WiSe 2026/27 | Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing |
Sonstiges
Keine Angabe