General information

Course name	Lecture: Parametrisierte Algorithmen (Modul: Komplexitätstheoretische Methoden)
Course number	INF.06236.01
Semester	SS 2019
Current number of participants	8
Home institute	Institut für Informatik
Courses type	Lecture in category Offizielle Lehrveranstaltungen
First date	Tuesday, 02.04.2019 14:15 - 15:45, Room: Hörsaal 3.04 [VSP 1]

Lecturers

apl. Prof. Dr. Klaus Reinhardt

Rooms and times

Hörsaal 3.04 [VSP 1]: Tuesday: 14:15 - 15:45, weekly (15x); Wednesday: 12:15 - 13:45, weekly (14x)

Fields of study

Naturwissenschaftliche Fakultät III - Agrarwiss., Geowiss. und Informatik > Informatik > Institut für Informatik > Master

Module assignments

Informatik InformatikMA120, Version of accreditation (WS 2013/14 - SS 2016) > Vertiefende Module der Vertiefungsrichtung `Algorithmen und Theoretische Informatik` > INF.06236.02 - Komplexitätstheoretische Methoden, valid from SS 2016 > Course 2: Exercises (Übung)
Informatik InformatikMA120, Version of accreditation (WS 2016/17 - WS 2022/23) > Basismodule der Vertiefungsrichtung `Algorithmen und Theoretische Informatik` > INF.06236.02 - Komplexitätstheoretische Methoden, valid from SS 2016 > Course 2: Exercises (Übung)
Bioinformatik BioinformatikMA120, Version of accreditation (WS 2016/17 - WS 2022/23) > Algorithmen und Theoretische Informatik > INF.06236.02 - Komplexitätstheoretische Methoden, valid from SS 2016 > Course 2: Exercises (Übung)
Bioinformatik BioinformatikMA120, Version of accreditation (WS 2009/10 - SS 2016) > Theoretische Informatik > INF.06236.02 - Komplexitätstheoretische Methoden, valid from SS 2016 > Course 2: Exercises (Übung)
Informatik InformatikMA120, Version of accreditation (WS 2013/14 - SS 2016) > Vertiefende Module der Vertiefungsrichtung `Algorithmen und Theoretische Informatik` > INF.06236.02 - Komplexitätstheoretische Methoden, valid from SS 2016 > Course 1: Lecture (Vorlesung)
Informatik InformatikMA120, Version of accreditation (WS 2016/17 - WS 2022/23) > Basismodule der Vertiefungsrichtung `Algorithmen und Theoretische Informatik` > INF.06236.02 - Komplexitätstheoretische Methoden, valid from SS 2016 > Course 1: Lecture (Vorlesung)
Bioinformatik BioinformatikMA120, Version of accreditation (WS 2016/17 - WS 2022/23) > Algorithmen und Theoretische Informatik > INF.06236.02 - Komplexitätstheoretische Methoden, valid from SS 2016 > Course 1: Lecture (Vorlesung)
Bioinformatik BioinformatikMA120, Version of accreditation (WS 2009/10 - SS 2016) > Theoretische Informatik > INF.06236.02 - Komplexitätstheoretische Methoden, valid from SS 2016 > Course 1: Lecture (Vorlesung)

Comment/Description

Behandlung von Algorithmen zur exakten Lösung NP-schwerer Optimierungsprobleme unter Berücksichtigung wichtiger Problemparameter wie z.B. der Lösungsgröße; behandelte Themen u.a. Graph- und Netzwerkprobleme, Zeichenkettenprobleme, Probleme der algorithmischen Biologie; vorgestellte Techniken u.a. Datenreduktion, tiefenbeschränkte Suchbäume, Farbkodierung, iterative Kompression, Baumzerlegung von Graphen.

Die Übungen sind zeitlich in die zwei Vorlesungsblocks zu je 90 Minuten integriert, d.h. etwa 15 der insgesamt 60 Stunden werden für die Übungen verwendet, die anderen 45 Stunden sind Vorlesung. In den Übungen zählt die Bereitschaft, erarbeitete Lösungen von Übungsaufgaben an der Tafel vorzutragen.

Wünschenswert sind Vorkenntnisse über NP-Vollständigkeit z.B. aus der Vorlesung Automaten und Berechenbarkeit.