MLU
INF.02606.03 - Approximative und randomisierte Algorithmen (Vollständige Modulbeschreibung)
Originalfassung Englisch
INF.02606.03 5 CP
Modulbezeichnung Approximative und randomisierte Algorithmen
Modulcode INF.02606.03
Semester der erstmaligen Durchführung
Fachbereich/Institut Institut für Informatik
Verwendet in Studiengängen / Semestern
  • Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Akkreditierungsfassung (WS 2009/10 - SS 2016) > Datenstrukturen und effiziente Algorithmen
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Akkreditierungsfassung (WS 2006/07 - SS 2013) > Primärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Akkreditierungsfassung (WS 2006/07 - SS 2013) > Sekundärmodule
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Akkreditierungsfassung (WS 2006/07 - SS 2013) > Sekundärmodule
  • Physik (MA120 LP) (Master) > Physik PhysikMA120, Akkreditierungsfassung gültig ab WS 2019/20 > Nichtphysikalische Wahlpflichtmodule
  • Physik (MA120 LP) (Master) > Physik PhysikMA120, Akkreditierungsfassung (WS 2009/10 - SS 2019) > Wahlpflichtmodule
Modulverantwortliche/r
Weitere verantwortliche Personen
Prof. Dr. Matthias Müller-Hannemann
Teilnahmevoraussetzungen
Kompetenzziele
  • 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.
Modulinhalte
  • Klassifikation von Problemen auf Approximierbarkeit
  • kombinatorische Approximationsalgorithmen
  • Approximationsalgorithmen basierend auf linearer Programmierung
  • randomisierte Algorithmen für Optimierungsprobleme
  • randomisierte Datenstrukturen
  • probabilisitische Analyse
Lehrveranstaltungsformen Vorlesung (3 SWS)
Übung (1 SWS)
Kursus
Kursus
Unterrichtsprachen Deutsch, Englisch
Dauer in Semestern 1 Semester Semester
Angebotsrhythmus Modul nicht festlegbar
Aufnahmekapazität Modul unbegrenzt
Prüfungsebene
Credit-Points 5 CP
Modulabschlussnote LV 1: %; LV 2: %; LV 3: %; LV 4: %.
Faktor der Modulnote für die Endnote des Studiengangs 1
Hinweise
Angebotsturnuns: Zweijahresrhythmus im Wintersemester Primärmodul für Vertiefungsrichtungen:Algorithmen und Datenstrukturen Sekundärmodul für Vertiefungsrichtungen:Theoretische Informatik, Wirtschaftsinformatik, Bioinformatik
Modulveran­staltung Lehrveranstaltungs­form Veranstaltungs­titel SWS Workload Präsenz Workload Vor- / Nach­bereitung Workload selbstge­staltete Arbeit Workload Prüfung incl. Vorbereitung Workload Summe
LV 1 Vorlesung Vorlesung 3 0
LV 2 Übung Übung 1 0
LV 3 Kursus Selbststudium zur Vorlesung 0
LV 4 Kursus Bearbeitung der Übungsaufgaben 0
Workload modulbezogen 150 150
Workload Modul insgesamt 150
Prüfung Prüfungsvorleistung Prüfungsform
LV 1
LV 2
LV 3
LV 4
Gesamtmodul
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
Wiederholungsprüfung
Regularien Teilnahme­voraussetzungen Angebots­rhythmus Anwesenheits­pflicht Gewicht an Modulnote in %
LV 1 Wintersemester Nein %
LV 2 Wintersemester Nein %
LV 3 Wintersemester Nein %
LV 4 Wintersemester Nein %