MLU
INF.06236.02 - Komplexitätstheoretische Methoden (Vollständige Modulbeschreibung)
Originalfassung Englisch
INF.06236.02 5 CP
Modulbezeichnung Komplexitätstheoretische Methoden
Modulcode INF.06236.02
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) > Theoretische Informatik
  • Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Akkreditierungsfassung (WS 2016/17 - WS 2022/23) > Algorithmen und Theoretische Informatik
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Akkreditierungsfassung (WS 2013/14 - SS 2016) > Vertiefende Module der Vertiefungsrichtung `Algorithmen und Theoretische Informatik`
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Akkreditierungsfassung (WS 2016/17 - WS 2022/23) > Basismodule der Vertiefungsrichtung `Algorithmen und Theoretische Informatik`
Modulverantwortliche/r
Weitere verantwortliche Personen
PD. Dr. habil. Klaus Reinhardt
Teilnahmevoraussetzungen
Kompetenzziele
  • 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.
Modulinhalte
  • 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.
Lehrveranstaltungsformen Vorlesung (3 SWS)
Übung (1 SWS)
Kursus
Kursus
Unterrichtsprachen Deutsch, Englisch
Dauer in Semestern 1 Semester Semester
Angebotsrhythmus Modul jedes Sommersemester
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
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 Bearbeitung der Übungsaufgaben 0
LV 4 Kursus Selbststudium Prüfungsvorbereitung 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 an den Übungen, Erfolgreiche Bearbeitung der Aufgaben
mündl. Prüfung oder Klausur
Wiederholungsprüfung
Regularien Teilnahme­voraussetzungen Angebots­rhythmus Anwesenheits­pflicht Gewicht an Modulnote in %
LV 1 Sommersemester Nein %
LV 2 Sommersemester Nein %
LV 3 Sommersemester Nein %
LV 4 Sommersemester Nein %