1. Modulverzeichnis (MTS)
  2. Module
  3. Modulbeschreibung anzeigen

Algorithmische Graphentheorie

Zur Modulseite PDF generieren

#40822 / #1

Seit SS 2017

English

Algorithmische Graphentheorie

6

Kreutzer, Stephan

Benotet

Mündliche Prüfung

English

Zugehörigkeit


Fakultät IV

Institut für Softwaretechnik und Theoretische Informatik

34352200 FG Logik und Semantik

Keine Angabe

Kontakt


TEL 7-3

Keine Angabe

stephan.kreutzer@tu-berlin.de

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.

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

Compulsory area

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

LehrveranstaltungenArtNummerTurnusSpracheSWS ISIS VVZ
Algorithmische GraphentheorieVL3435 L 9053SoSeKeine Angabe2
Algorithmische GraphentheorieUE3435 L 9054SoSeKeine Angabe2
ISIS-Kurssuche nach Veranstaltungen des Moduls

Arbeitsaufwand und Leistungspunkte

Algorithmische Graphentheorie (VL):

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit15.02.0h30.0h
Vor-/Nachbereitung15.04.0h60.0h
90.0h(~3 LP)

Algorithmische Graphentheorie (UE):

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit15.02.0h30.0h
Vor-/Nachbereitung15.04.0h60.0h
90.0h(~3 LP)
Der Aufwand des Moduls summiert sich zu 180.0 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

Oral exam

Sprache(n)

English

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

Verfügbarkeit:  nicht verfügbar

 

Skript in elektronischer Form

Verfügbarkeit:  nicht verfügbar

 

Literatur

Empfohlene Literatur
Keine empfohlene Literatur angegeben

Zugeordnete Studiengänge


Diese Modulversion wird in folgenden Studiengängen verwendet:

Studiengang / StuPOStuPOsVerwendungenErste VerwendungLetzte Verwendung
Computer Engineering (M. Sc.)117SS 2017SoSe 2025
Computer Science (Informatik) (M. Sc.)129SS 2017SoSe 2025
Elektrotechnik (M. Sc.)117SS 2017SoSe 2025
Informatik (B. Sc.)118SS 2017SoSe 2025
Naturwissenschaften in der Informationsgesellschaft (B. Sc.)35SoSe 2024SoSe 2025

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

Sonstiges

Keine Angabe