TU Berlin

Algorithmics and Computational Complexity Research GroupWinter term 2020/2021

isti-logo

Page Content

to Navigation

To top

Bachelor

Berechenbarkeit und Komplexität

Beschreibung: (6 LP)

Absolventinnen und Absolventen dieses Moduls beherrschen den Umgang mit Turingmaschinen und weiteren Modellen der Berechenbarkeit. Sie besitzen ein  Grundverständnis der Berechenbarkeit von Entscheidungsproblemen und  grundlegender Komplexitätsklassen. Sie sind befähigt, die Komplexität ausgewählter Problembeispiele zu beurteilen. Entsprechende Aufgabenstellungen können sie sowohl selbständig als auch in Kleingruppen bearbeiten.

Veranstaltung
Zeit
Lehrperson
Ort
Sprache
2 SWS
Vorlesung
Prof. Dr. Rolf Niedermeier
deutsch

Organisation:

  • Eine Anmeldung im ISIS ist aus organisatorischen Gründen erforderlich. Bitte beachten Sie, dass diese Anmeldung Sie nicht von der regulären Prüfungsanmeldung befreit, entweder direkt über QISPOS oder indem Sie dieses pdf ausfüllen und an Ihr Prüfungsteam schicken.
  • Modulbeschreibung 

Aktuelle Themen der Algorithmik

Beschreibung: (3 LP)

 

Die Inhalte des Seminars richten sich nach aktuellen Entwicklungen der Algorithmik, insbesondere auch Neuerscheinungen in Buchform oder Artikelsammlungen.

 

Thema in diesem Semester: TBA

Das Seminar in diesem Semester richtet sich an Studierende im fortgeschrittenen Bachelor. Die Studierenden bekommen Themenkomplexe mit Aufgaben zur eigenen Erarbeitung und Präsentation im Plenum vorgestellt.

 

Veranstaltung
Zeit
Lehrperson
Ort
Sprache
2 SWS
Seminar
nach Vereinbarung
Matthias Bentert
deutsch

Organisation:

  • Eine Anmeldung im ISIS ist aus organisatorischen Gründen erforderlich. Bitte beachten Sie, dass diese Anmeldung Sie nicht von der regulären Prüfungsanmeldung befreit; entweder direkt über QISPOS oder indem Sie dieses pdf ausfüllen und an Ihr Prüfungsteam schicken.
  • Das Seminar wird als Blockveranstaltung durchgeführt. Die Vereinbarung der Termine sowie die Vorstellung der Themen erfolgt am über den ISIS-Kurs.
  • Modulbeschreibung (PDF)
  • Module description (PDF)

To top

Bachelor and Master

Algorithm Engineering für schwere Probleme

Beschreibung: (9 LP)

Der Kurs
  - gibt eine Einführung in die grundlegenden Techniken des Algorithm Engineering, insbesondere für NP-schwere Probleme,
  - lehrt Design, Analyse, Implementierung und Test von Algorithmen und
  - gibt Einblick in Problemmodellierung und Lösungsmethoden wie Suchbaumalgorithmen, Datenreduktionstechniken und Vorverarbeitung, exakte, approximative und heuristische Algorithmen und Strategien basierend auf linearem Programmieren (unter Benutzung von etablierten Solvern).

 

The course
  - gives an introduction to the basic techniques of Algorithm Engineering, with a particular focus on NP-hard problems,
  - helps to design, analyze, and implement algorithms, and
  - provides insight into problem modeling and solution strategies including search tree algorithms, data reduction techniques, preprocessing, approximation, heuristics, and approaches based on linear programming (using established solvers).

 

Event
Time
Lecturer
Location
Language
2 SWS
Lecture
Dr. André Nichterlein
german/ english
4 SWS
Practical course
Leon Kellerhals, Philipp Zschoche



german/ english

Organisation:

Master

Randomized Algorithmics

Description:  (6 CP)

Introduction into the mathematical and algorithmic foundations of algorithm, design and analysis using the resource “random bits”.

Particular topics are:

  • randomized algorithms for graph problems and geometric problems
  • probabilistic method
  • limits of randomized algorithms
Event
Time
Lecturer
Location
Language
4 SWS
Lecture/Tutorial
Dr. Till Fluschnik,
Dr. Hendrik Molter
english/deutsch

Organization:

  • A registration within the ISIS is necessary. Please note that registration at the Prüfungsamt is still mandatory - either via QISPOS or by filling in this pdf and sending it to your Prüfungsteam.
  • The default language is english. If all participants prefer german, the course can be held in german.
  • Module description (PDF)

To top

Parameterized Algorithmics

Description: (6 CP)

 

Graduates of this module

  • know the approach of parameterized complexity analysis for solving NP-hard computational problems,
  • are able to design and analyze parameterized algorithms, and

  • can use complexity-theoretic methods to determine the limits of parameterized algorithmics.

Particular topics include:

  • algorithms for exactly solving NP-hard optimization problems by exploiting important problem parameters such as solution size

  • 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

Event
Time
Lecturer
Location
Language
4 SWS
Lecture + Tutorial
Dr. Vincent Froese
german/english

Organization:

  • A registration within the ISIS is necessary. Please note that registration at the Prüfungsamt is still mandatory - either via QISPOS or by filling in this pdf and sending it to your Prüfungsteam.
  • Module description (PDF)

To top

Advanced Algorithmics

Description: (9 CP)

 

Students who have completed this module can design and analyze algorithms for computational problems arising in various application contexts. When facing a concrete computational problem, they are able to choose, from a wide range of techniques, a solution strategy to efficiently solve the problem.
This includes in particular strategies for solving problems that are computationally hard in the worst case.

Particular topics are:

  • algorithmic decision theory,
  • algorithmic graph theory,
  • computational geometry,
  • algorithms for strings,
  • approximation and online algorithms,
  • parameterized and exact algorithms,
  • randomized algorithms and analysis,
  • universal solvers,
  • distributed algorithms,
  • algorithmic data mining
  • algorithms for massive data,
  • quantum computation.
Event
Time
Lecturer
Location
Language
6 SWS
Lecture + Tutorial



Prof. Dr. Rolf Niedermeier, Dr. André Nichterlein,
Matthias Bentert



german/english

Organization:

  • A registration with ISIS is necessary. Please note that registration with the Prüfungsamt is still mandatory - either via QISPOS or by filling in this pdf and sending it to your Prüfungsteam.
  • Module description (PDF)

Für Interessierte

(Bachelor, Master, Externe)

Research Colloquium on Algorithms and Complexity

Description: (3 CP)

 

In this seminar recent research of our group and special invited guests is presented. The main topics are parameterized algorithmics and complexity. The seminar is an excellent opportunity for advanced students to get in touch with current topics in our research field.

Students that participate in the seminar and also present a current publication in algorithmic research can receive 3 ECTS credit points.

Event
Zeit
Lecturer
Speaker
Location
Language
2 SWS
Colloquium
Tue 16-18
Prof. Dr. Rolf Niedermeier
Guests,
PhD students,
students
TEL 512
german/english

Navigation

Quick Access

Schnellnavigation zur Seite über Nummerneingabe