MLU
INF.02606.03 - Approximative und randomisierte Algorithmen (Complete module description)
Original version English
INF.02606.03 5 CP
Module label Approximative und randomisierte Algorithmen
Module code INF.02606.03
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) > Datenstrukturen und effiziente Algorithmen
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2006/07 - SS 2013) > Primärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2006/07 - SS 2013) > Sekundärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation (WS 2006/07 - SS 2013) > Sekundärmodule
  • Physik (MA120 LP) (Master) > Physik PhysikMA120, Version of accreditation valid from WS 2019/20 > Nichtphysikalische Wahlpflichtmodule
  • Physik (MA120 LP) (Master) > Physik PhysikMA120, Version of accreditation (WS 2009/10 - SS 2019) > Wahlpflichtmodule
Responsible person for this module
Further responsible persons
Prof. Dr. Matthias Müller-Hannemann
Prerequisites
Skills to be acquired in this module
  • Approximationsalgorithmen sind Verfahren für in der Regel schwere Optimierungsprobleme, die eine nachweisbare Gütegarantie für den erzielten Zielfunktionswert besitzen. Es soll erlernt werden, wie man Algorithmen mit Gütegarantie entwerfen und analysieren kann. Die Studierenden sollen lernen, die Komplexität von Problemen bezüglich ihrer Approximierbarkeit unterscheiden und bestimmen zu können.
  • Im zweiten Teil des Moduls werden randomisierte (zufallsgesteuerte) Verfahren behandelt, die aufgrund ihrer Einfachheit und Effizienz zu einem Standardansatz für den Algorithmenentwurf geworden sind. Erlernt werden sollen die wichtigsten Paradigmen für den Entwurf randomisierter Algorithmen. Die Ideen und Konzepte sollen anhand unterschiedlicher Anwendungen eingeübt werden.
Module contents
  • Klassifikation von Problemen auf Approximierbarkeit
  • kombinatorische Approximationsalgorithmen
  • Approximationsalgorithmen basierend auf linearer Programmierung
  • randomisierte Algorithmen für Optimierungsprobleme
  • randomisierte Datenstrukturen
  • probabilisitische Analyse
Forms of instruction Lecture (3 SWS)
Exercises (1 SWS)
Course
Course
Languages of instruction German, English
Duration (semesters) 1 Semester Semester
Module frequency nicht festlegbar
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
Reference text
Angebotsturnuns: Zweijahresrhythmus im Wintersemester Primärmodul für Vertiefungsrichtungen:Algorithmen und Datenstrukturen Sekundärmodul für Vertiefungsrichtungen:Theoretische Informatik, Wirtschaftsinformatik, Bioinformatik
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 Selbststudium zur Vorlesung 0
Course 4 Course Bearbeitung der Übungsaufgaben 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 und aktive Mitarbeit in den Übungen (Darstellung der Problemlösung in den Übungen), erfolgreiche Bearbeitung der Übungsaufgaben, wobei 50 % der erreichbaren Punkte erzielt werden müssen
mündl./schriftl. Prüfung
Exam repetition information
Prerequisites and conditions Prerequisites Frequency Compulsory attendance Share on module grade in percent
Course 1 Winter semester No %
Course 2 Winter semester No %
Course 3 Winter semester No %
Course 4 Winter semester No %