Aufgrund von Wartungsarbeiten sind keine Änderungen im Schließsystem möglich. Der Menüpunkt Schließsystem wird ausgeblendet. Wir danken für Ihr Verständnis!

186.855 Fixed-Parameter Algorithms and Complexity
Diese Lehrveranstaltung ist in allen zugeordneten Curricula Teil der STEOP.
Diese Lehrveranstaltung ist in mindestens einem zugeordneten Curriculum Teil der STEOP.

2018W, VU, 2.0h, 3.0EC, wird geblockt abgehalten

Merkmale

  • Semesterwochenstunden: 2.0
  • ECTS: 3.0
  • Typ: VU Vorlesung mit Übung

Ziele der Lehrveranstaltung

The goal of this course is to provide an overview of the main advances and techniques used for the development of fixed-parameter algorithms and to introduce students to the rapidly developing paradigm of parameterized complexity. After finishing the course, students should be able to understand recent scientific advances in the field, develop basic kernelization and fixed-parameter algorithms for various problems, and also have access to techniques which can rule out the existence of such algorithms under certain conditions.

Inhalt der Lehrveranstaltung

Fixed-parameter algorithms provide a powerful approach for efficiently solving many NP-hard problems by exploiting structural aspects of problem instances in terms of a problem parameter. This course provides an overview of the main techniques for developing fixed-parameter algorithms (including bounded search trees, kernelization, color coding, modulators) as well as the fundamentals of parameterized complexity theory (such as the Weft-hierarchy, XP and para-NP-hardness, kernelization lower bounds) which allows to provide strong evidence that certain problems cannot be solved by a fixed-parameter algorithm.

Weitere Informationen

The course information meeting and first lecture start on Monday 7 January at 12:00 in the von Neumann seminar room.

The course will be held blocked in January 2019 and all lectures except for the first will take place in library/seminar room of the Algorithms and Complexity Group (room HB0408 at Favoritenstrasse 9-11). The course will take place:

  • on three consecutive Mondays (7.1., 14.1., 21.1.) from 12:00 to 16:00; as an exception, on Monday 14.1. the course starts at 13:30,
  • on three consecutive Thursdays (10.1., 17.1., 24.1.) from 14:00 to 18:00.

There will be a break in the middle of each block (specific timing is up for discussion).

Vortragende

Institut

LVA Termine

TagZeitDatumOrtBeschreibung
Mo12:00 - 16:0007.01.2019 - 21.01.2019Seminarraum FAV EG B (Seminarraum von Neumann) Lecture
Do14:00 - 18:0010.01.2019 - 24.01.2019Seminarraum FAV EG C (Seminarraum Gödel) Lecture
Fr13:00 - 17:0018.01.2019Seminarraum FAV 05 (Seminarraum 186) Fixed-Parameter Algorithms and Complexity (Presentations + Backup)
Fixed-Parameter Algorithms and Complexity - Einzeltermine
TagDatumZeitOrtBeschreibung
Mo07.01.201912:00 - 16:00Seminarraum FAV EG B (Seminarraum von Neumann) Lecture
Do10.01.201914:00 - 18:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture
Mo14.01.201912:00 - 16:00Seminarraum FAV EG B (Seminarraum von Neumann) Lecture
Do17.01.201914:00 - 18:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture
Fr18.01.201913:00 - 17:00Seminarraum FAV 05 (Seminarraum 186) Fixed-Parameter Algorithms and Complexity (Presentations + Backup)
Mo21.01.201912:00 - 16:00Seminarraum FAV EG B (Seminarraum von Neumann) Lecture
Do24.01.201914:00 - 18:00Seminarraum FAV EG C (Seminarraum Gödel) Lecture
LVA wird geblockt abgehalten

LVA-Anmeldung

Von Bis Abmeldung bis
07.01.2019 00:01 11.01.2019 23:59 11.01.2019 23:59

Curricula

Literatur

Es wird kein Skriptum zur Lehrveranstaltung angeboten.

Vorkenntnisse

This course requires basic knowledge on the design and analysis of algorithms as well as basic complexity theory. Knowledge of the topics covered in the Algorithmics course is an advantage.

Vorausgehende Lehrveranstaltungen

Sprache

Englisch