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

Algorithmische GraphentheorieModulbeschreibung #40822 / Version 1

← Zur Modulseite English version
Modul / Version#40822 / #1
GültigkeitSeit SS 2017
Verfügbare Sprache(n)Englisch
Leistungspunkte6
Modulverantwortliche*rKreutzer, Stephan
BenotungBenotet
PrüfungsformMündliche Prüfung
Lehrsprache(n)Englisch

Zugehörigkeit

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

Kontakt

SekretariatTEL 7-3
Ansprechpartner*inKeine Angabe
E-Mail-Adressestephan.kreutzer@tu-berlin.de
WebseiteKeine 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.

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

Modulbestandteile

Pflichtbereich

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

LehrveranstaltungenArtNummerTurnusSpracheSWSVVZ
Algorithmische GraphentheorieVorlesung3435 L 9053 Sommersemester–2 ISIS
Algorithmische GraphentheorieÜbung3435 L 9054 Sommersemester–2 ISIS

Arbeitsaufwand und Leistungspunkte

Algorithmische Graphentheorie (Vorlesung)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit152 h30 h
Vor-/Nachbereitung154 h60 h
90 h

Algorithmische Graphentheorie (Übung)

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

BenotungBenotet
PrüfungsformMündliche Prüfung
Art der Portfolioprüfung100 Punkte insgesamt
SpracheEnglisch
Dauer/Umfang20-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 / StuPOSemesterStudiengangsbereich
Computer Engineering
StuPO 2015
SoSe 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2025/26Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
SoSe 2026Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2026/27Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
Computer Science (Informatik)
StuPO 2015
SoSe 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2025/26Studiengebiete › Grundlagen der Informatik / Foundations of Computing
SoSe 2026Studiengebiete › Grundlagen der Informatik / Foundations of Computing
WiSe 2026/27Wahlpflichtbereich › Studiengebiet › Grundlagen der Informatik / Foundations of Computing
Elektrotechnik
StuPO 2015
SoSe 2025Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2025/26Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
SoSe 2026Wahlpflicht Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
WiSe 2026/27Wahlpflichtbereich › Studiengebiete Fak. IV › Grundlagen der Informatik / Foundations of Computing
Informatik
StuPO 2015
SoSe 2025Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik
WiSe 2025/26Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik
SoSe 2026Wahlpflichtbereich › Wahlpflichtbereich Katalog Informatik
WiSe 2026/27Wahlpflichtbereich › Katalog Informatik
Informatik
StuPO 2025
WiSe 2026/27Wahlpflichtbereich › Studiengebiete › Theoretische Informatik › Weitere Module
Naturwissenschaften in der Informationsgesellschaft
StuPO 2018
SoSe 2025Wahlpflichtbereich › Informatik › Weiterführende Module
WiSe 2025/26Wahlpflichtbereich › Informatik › Weiterführende Module
SoSe 2026Wahlpflichtbereich › Informatik › Weiterführende Module
WiSe 2026/27Wahlpflichtbereich › Informatik › Weiterführende Module
Naturwissenschaften in der Informationsgesellschaft
StuPO 2025
WiSe 2025/26Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik
SoSe 2026Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik
WiSe 2026/27Wahlpflichtbereich › Wahlpflichtbereich Informatik › Weiterführende Module Informatik

Sonstiges

Keine Angabe