AGNES -
Lehre und Prüfung online
Studierende in Vorlesung
Anmelden

Parameterized Algorithms - Detailseite

  • Funktionen:
Grunddaten
Veranstaltungsart Vorlesung Veranstaltungsnummer 3313057
Semester SoSe 2019 SWS 4
Rhythmus Moodle-Link  
Veranstaltungsstatus Freigegeben für Vorlesungsverzeichnis  Freigegeben  Sprache deutsch
Belegungsfrist Es findet keine Online-Belegung über AGNES statt!

Termine

Gruppe 1 iCalendar Export iCalendar Export
  Tag Zeit Rhythmus Dauer Raum Raum-
plan
Lehrperson Status Bemerkung fällt aus am Max. Teilnehmer
iCalendar Export Do. 15:00 bis 17:00 wöch
Einzeltermine anzeigen
Erwin Schrödinger-Zentrum /Modul 1 - 1307 Rudower Chaussee 26 (RUD26) - (Unterrichtsraum) Kratsch findet statt   04.07.2019:  1000
iCalendar Export Fr. 13:00 bis 15:00 wöch
Einzeltermine anzeigen
Erwin Schrödinger-Zentrum /Modul 1 - 1307 Rudower Chaussee 26 (RUD26) - (Unterrichtsraum) Kratsch findet statt   05.07.2019:  1000
Gruppe 1:
 


Zugeordnete Person
Zugeordnete Person Zuständigkeit
Kratsch, Stefan , Prof. Dr.
Studiengänge
Abschluss Studiengang LP Semester
Master of Education (GYM)  Informatik 1. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   10  -  
Master of Education (ISS)  Informatik 1. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   10  -  
Master of Education (ISG)  Informatik 1. Fach ( Vertiefung: mit LA-Option; POVersion: 2018 )   10  -  
Master of Education (ISS)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   10  -  
Master of Education (BS)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   10  -  
Master of Education (GYM)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2015 )   10  -  
Master of Education (ISG)  Informatik 2. Fach ( Vertiefung: mit LA-Option; POVersion: 2018 )   10  -  
Master of Science  Informatik Hauptfach ( POVersion: 2009 )   10  -  
Master of Science  Informatik Hauptfach ( Vertiefung: kein LA; POVersion: 2015 )   10  -  
Master of Science  Wirtschaftsinformatik Hauptfach ( Vertiefung: kein LA; POVersion: 2016 )   10  -  
Zuordnung zu Einrichtungen
Einrichtung
Mathematisch-Naturwissenschaftliche Fakultät, Institut für Informatik
Inhalt
Kommentar

Parameterized algorithms are an approach for coping with the intractability of NP-hard computational problems. The central idea therein is to quantify the structure of input instances by one or more parameters. Then, one seeks algorithms that provably perform well when the chosen parameters are sufficiently small. In this way, we can formalize the intuition that typical instances may have plenty of useful structure, which distinguishes them from the worst case.

There is a rich toolbox of algorithmic techniques that will be covered in the lecture. These include branching algorithms, kernelization, iterative compression, color coding, dynamic programming on tree decompositions, inclusion-exclusion, and others. The algorithmic techniques are complemented by lower bound methods that allow to rule out fast parameterized algorithms or that prove optimality of certain running times under appropriate assumptions.

Bemerkung

LV findet in Englisch statt.

Strukturbaum

Keine Einordnung ins Vorlesungsverzeichnis vorhanden. Veranstaltung ist aus dem Semester SoSe 2019. Aktuelles Semester: WiSe 2019/20.
Humboldt-Universität zu Berlin | Unter den Linden 6 | D-10099 Berlin