MLU
INF.06236.02 - Komplexitätstheoretische Methoden (Complete module description)
Original version English
INF.06236.02 5 CP
Module label Komplexitätstheoretische Methoden
Module code INF.06236.02
Semester of first implementation
Faculty/Institute Institut für Informatik
Module used in courses of study / semesters
  • Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Version of accreditation (WS 2009/10 - SS 2016) > Theoretische Informatik
  • Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Version of accreditation (WS 2016/17 - WS 2022/23) > Algorithmen und Theoretische Informatik
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2013/14 - SS 2016) > Vertiefende Module der Vertiefungsrichtung `Algorithmen und Theoretische Informatik`
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2016/17 - WS 2022/23) > Basismodule der Vertiefungsrichtung `Algorithmen und Theoretische Informatik`
Responsible person for this module
Further responsible persons
PD. Dr. habil. Klaus Reinhardt
Prerequisites
Skills to be acquired in this module
  • Die Studierenden erwerben in dem Modul Kenntnis, mit welchem Aufwand algorithmische Probleme auf einer Maschine, unabhängig vom konkreten Computer, gelöst werden können. Sie werden ein Verständnis für praktische Grenzen der algorithmischen Lösbarkeit von Problemen bekommen und die Fähigkeit erlangen, die Komplexität spezieller Probleme durch Reduktionsbeweise und Simulationstechniken in Komplexitätsklassen einzuordnen und Schwierigkeiten mit algorithmischen Methoden zu überwinden.
Allgemeines Lernziel ist es, ein Verständnis für abstrakte Zusammenhänge und die Fähigkeit zum logischen Denken zu entwickeln sowie grundlegende mathematische Methoden kennenzulernen. Die Studierenden werden befähigt, verschiedene Problemlösestrategien und Beweisverfahren anzuwenden.
Module contents
  • Parametrisierte Algorithmen:
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.Grenzen der Methodik werden durch parametrisierte Reduktion aufgezeigt.
Forms of instruction Lecture (3 SWS)
Exercises (1 SWS)
Course
Course
Languages of instruction German, English
Duration (semesters) 1 Semester Semester
Module frequency jedes Sommersemester
Module capacity unlimited
Time of examination
Credit points 5 CP
Share on module final degree Course 1: %; Course 2: %; Course 3: %; Course 4: %.
Share of module grade on the course of study's final grade 1
Module course label Course type Course title SWS Workload of compulsory attendance Workload of preparation / homework etc Workload of independent learning Workload (examination and preparation) Sum workload
Course 1 Lecture Vorlesung 3 0
Course 2 Exercises Übung 1 0
Course 3 Course Bearbeitung der Übungsaufgaben 0
Course 4 Course Selbststudium Prüfungsvorbereitung 0
Workload by module 150 150
Total module workload 150
Examination Exam prerequisites Type of examination
Course 1
Course 2
Course 3
Course 4
Final exam of module
Regelmäßige Teilnahme an den Übungen, Erfolgreiche Bearbeitung der Aufgaben
mündl. Prüfung oder Klausur
Exam repetition information
Prerequisites and conditions Prerequisites Frequency Compulsory attendance Share on module grade in percent
Course 1 Summer semester No %
Course 2 Summer semester No %
Course 3 Summer semester No %
Course 4 Summer semester No %