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

Parametrisierte AlgorithmikModulbeschreibung #40627 / Version 7

← Zur Modulseite English version
Diese Modulbeschreibung gilt nicht im aktuellen Semester (WiSe 2026/27). Zur aktuellen Version (v8)
Modul / Version#40627 / #7
GültigkeitSoSe 2023 – WiSe 2024/25
Verfügbare Sprache(n)Englisch
Leistungspunkte6
Modulverantwortliche*rWeller, Mathias
BenotungBenotet
PrüfungsformMündliche Prüfung
Lehrsprache(n)Englisch

Zugehörigkeit

FakultätFakultät IV
InstitutInstitut für Softwaretechnik und Theoretische Informatik
Fachgebiet34351100 FG Algorithmik und Komplexitätstheorie (AKT)

Kontakt

SekretariatEN 23
Ansprechpartner*inThielcke, Christlinde
E-Mail-Adresselehre@akt.tu-berlin.de
Webseitehttps://www.tu.berlin/akt/studium-lehre/lehrveranstaltungen

Lernergebnisse

On successful completion, students will be able to:

- apply the approach of parameterized complexity analysis to solve computationally hard (NP-hard) problems
- design and analyze parameterized algorithms
- identify practically relevant and tractable special cases of problems that are computationally hard in general
- use complexity-theoretic methods to determine the limits of parameterized algorithmics

Lehrinhalte

Particular topics include:

- algorithms for exactly solving NP-hard optimization problems by exploiting important problem parameters such as solution size or special structures in the input
- NP-hard computational problems on graphs and networks and on strings
- algorithmic techniques such as preprocessing by data reduction, depth-bounded search trees, color coding, iterative compression, tree decomposition of graphs, parameterized reductions

Modulbestandteile

Pflichtbereich

Die folgenden Veranstaltungen sind für das Modul obligatorisch:

LehrveranstaltungenArtNummerTurnusSpracheSWSVVZ
Parameterized AlgorithmicsIntegrierte Veranstaltung0434 L 220 Unregelmässig[en]4 ISIS

Arbeitsaufwand und Leistungspunkte

Parameterized Algorithmics (Integrierte Veranstaltung)

AufwandbeschreibungMultiplikatorStundenGesamt
Präsenzzeit154 h60 h
Vor-/Nachbereitung156 h90 h
150 h

Lehrveranstaltungsunabhängiger Aufwand

AufwandbeschreibungMultiplikatorStundenGesamt
Prüfungsvorbereitung130 h30 h
30 h

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

Beschreibung der Lehr- und Lernformen

The course material is presented in lectures. The lectures are accompanied by tutorials in which distributed work sheets are solved together.

Voraussetzungen für die Teilnahme / Prüfung

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

Basic knowledge on algorithms

Verpflichtende Voraussetzungen für die Modulprüfungsanmeldung:

Dieses Modul hat keine Prüfungsvoraussetzungen.

Abschluss des Moduls

BenotungBenotet
PrüfungsformMündliche Prüfung
SpracheEnglisch
Dauer/Umfang30 min

Prüfungsbeschreibung (Abschluss des Moduls)

Final oral exam determining the grade (MP).

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

Please register at QISPOS or directly at the examination office.

Literaturhinweise, Skripte

Skript in Papierform

nicht verfügbar

Skript in elektronischer Form

verfügbar – Slides will be made available during the lecture period: http://www.isis.tu-berlin.de/

Empfohlene Literatur

  • Jörg Flum, Martin Grohe: Parameterized Complexity Theory. Springer, Berlin 2006.
  • Marek Cygan, Fedor V. Fomin, Lukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michal Pilipczuk, Saket Saurabh: Parameterized Algortithms. Springer International Publishing, Cham 2015
  • Rod G. Downey, Michael R. Fellows: Fundamentals of Parameterized Complexity. Springer, New York 2013.
  • Rolf Niedermeier: Invitation to Fixed - Parameter Algorithms. Oxford Univ. Press, Oxford 2006.

Zugeordnete Studiengänge

Diese Modulversion wird in folgenden Studiengängen verwendet:

Studiengang / StuPOSemesterStudiengangsbereich
Wirtschaftsingenieurwesen
StuPO 2015
SoSe 2023Ingenieurwissenschaftliche Studienrichtungen/Engineering Majors › Informations- und Kommunikationssysteme/Information and Communication Systems (IKS) › Informations- und Kommunikationssysteme/Information and Communication Systems (Wahlpflicht/Compulsory-Elective) › Data and Software Engineering
WiSe 2023/24Ingenieurwissenschaftliche Studienrichtungen/Engineering Majors › Informations- und Kommunikationssysteme/Information and Communication Systems (IKS) › Informations- und Kommunikationssysteme/Information and Communication Systems (Wahlpflicht/Compulsory-Elective) › Data and Software Engineering
SoSe 2024Ingenieurwissenschaftliche Studienrichtungen/Engineering Majors › Informations- und Kommunikationssysteme/Information and Communication Systems (IKS) › Informations- und Kommunikationssysteme/Information and Communication Systems (Wahlpflicht/Compulsory-Elective) › Data and Software Engineering
WiSe 2024/25Ingenieurwissenschaftliche Studienrichtungen/Engineering Majors › Informations- und Kommunikationssysteme/Information and Communication Systems (IKS) › Informations- und Kommunikationssysteme/Information and Communication Systems (Wahlpflicht/Compulsory-Elective) › Data and Software Engineering

Sonstiges

This course is not offered regularly, you will find detailed information on our website: http://www.akt.tu-berlin.de/menue/teaching/