Algorithmische GraphentheorieModulbeschreibung #40822 / Version 1
- 6 LP
- Mündliche Prüfung
- Benotet
- Sommersemester
- Englisch
| Modul / Version | #40822 / #1 |
|---|---|
| Gültigkeit | Seit SS 2017 |
| 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 | TEL 7-3 |
|---|---|
| Ansprechpartner*in | Keine Angabe |
| E-Mail-Adresse | stephan.kreutzer@tu-berlin.de |
| Webseite | Keine Angabe |
Lernergebnisse
Many real world computational problems can be modeled as graph theoretical problems. In this course we will present algorithmic concepts and methods for solving various types of graph theoretical problems, including colouring problems, matchings, various types of cut and connectivity problems.
In the basic algorithms and data structures course efficient (polynomial time) algorithms for network flow and other problems have been studied. In this course we will cover additional types of problems that can be solved efficiently such as computing maximal matchings.
We will also study NP-hard problems and discuss various attempts of solving these problems efficiently, e.g. by approximating the solution or isolating the exponential running time in a single parameter.
Besides the algorithmic techniques, the course will also focus on the pure graph theoretical methods that make efficient algorithmic solutions possible.
In the basic algorithms and data structures course efficient (polynomial time) algorithms for network flow and other problems have been studied. In this course we will cover additional types of problems that can be solved efficiently such as computing maximal matchings.
We will also study NP-hard problems and discuss various attempts of solving these problems efficiently, e.g. by approximating the solution or isolating the exponential running time in a single parameter.
Besides the algorithmic techniques, the course will also focus on the pure graph theoretical methods that make efficient algorithmic solutions possible.
Lehrinhalte
In the course we will cover the following topics:
- Basic definitions of graphs and digraphs
- Basic concepts of algorithms and complexity
- Connectivity and Cuts
- Matchings
- Graph Colourings
- Tree-Width
- 3-Connectivity and Tutte's Theorem
- Planar graphs
- Basic definitions of graphs and digraphs
- Basic concepts of algorithms and complexity
- Connectivity and Cuts
- Matchings
- Graph Colourings
- Tree-Width
- 3-Connectivity and Tutte's Theorem
- Planar graphs
Modulbestandteile
Pflichtbereich
Die folgenden Veranstaltungen sind für das Modul obligatorisch:
Arbeitsaufwand und Leistungspunkte
Algorithmische Graphentheorie (Vorlesung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 15 | 4 h | 60 h |
| 90 h | |||
Algorithmische Graphentheorie (Übung)
| Aufwandbeschreibung | Multiplikator | Stunden | Gesamt |
|---|---|---|---|
| Präsenzzeit | 15 | 2 h | 30 h |
| Vor-/Nachbereitung | 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
The course consists of a lecture delivered in an interactive style using black board proofs and slides.
Voraussetzungen für die Teilnahme / Prüfung
Wünschenswerte Voraussetzungen für die Teilnahme an den Lehrveranstaltungen:
It is desirable that students taking the course have taken an introduction to graph theory. The course is mostly self-contained, though, but assumes some familiarity with graph theoretical medthods.
Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:
Dieses Modul hat keine Prüfungsvoraussetzungen.
Abschluss des Moduls
| Benotung | Benotet |
|---|---|
| Prüfungsform | Mündliche Prüfung |
| Art der Portfolioprüfung | 100 Punkte insgesamt |
| Sprache | Englisch |
| Dauer/Umfang | 20-40 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: Sommersemester.
Maximale teilnehmende Personen
Dieses Modul ist nicht auf eine Anzahl Studierender begrenzt.
Anmeldeformalitäten
See http://logic.las.tu-berlin.de
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 | |
| Informatik StuPO 2015 | SoSe 2025 | Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik |
| WiSe 2025/26 | Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik | |
| SoSe 2026 | Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik | |
| WiSe 2026/27 | Wahlpflichtbereich › Katalog Informatik | |
| Informatik StuPO 2025 | WiSe 2026/27 | Wahlpflichtbereich › Studiengebiete › Theoretische Informatik › Weitere Module |
| Naturwissenschaften in der Informationsgesellschaft StuPO 2018 | SoSe 2025 | Wahlpflichtbereich › Informatik › Weiterführende Module |
| WiSe 2025/26 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| SoSe 2026 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| WiSe 2026/27 | Wahlpflichtbereich › Informatik › Weiterführende Module | |
| Naturwissenschaften in der Informationsgesellschaft StuPO 2025 | WiSe 2025/26 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik |
| SoSe 2026 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik | |
| WiSe 2026/27 | Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik |
Sonstiges
Keine Angabe