INF.01116.07 - Komplexitätstheorie (Complete module description)

INF.01116.07 - Komplexitätstheorie (Complete module description)

Original version English
INF.01116.07 5 CP
Module label Komplexitätstheorie
Module code INF.01116.07
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 valid from SoSe 2023 > Algorithmen und Theoretische Informatik (Anteil gem. § 5 Abs. 4-6, Anlage 2)
  • Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Version of accreditation (WS 2009/10 - SS 2016) > Hauptgebiet ”Mathematik und ausgewählte Module der Theoretischen Informatik”
  • Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Version of accreditation (WS 2016/17 - WS 2022/23) > Mathematik
  • Informatik (MA120 LP) (Master) > Informatik InformatikMA120, Version of accreditation valid from SoSe 2023 > Vertiefende Module der Vertiefungsrichtung `Algorithmen und Theoretische Informatik`
  • 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 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) > Vertiefende Module der Vertiefungsrichtung `Algorithmen und Theoretische Informatik`
  • Mathematik (MA120 LP) (Master) > Mathematik MathematikMA120, Version of accreditation valid from WS 2022/23 > Anwendungsfach Informatik (20 LP sind zu erbringen)
  • Mathematik (MA120 LP) (Master) > Mathematik MathematikMA120, Version of accreditation (WS 2006/07 - SS 2013) > Anwendungsfach Informatik
  • Mathematik (MA120 LP) (Master) > Mathematik MathematikMA120, Version of accreditation (WS 2013/14 - SoSe 2023) > Anwendungsfach Informatik
Responsible person for this module
Further responsible persons
apl. Prof. Dr. Klaus Reinhardt
Prerequisites
keine
Skills to be acquired in this module
Studierende sollen durch dieses Modul die folgenden Kompetenzen erwerben:
  • Sie können beurteilen, mit welchem Aufwand algorithmische Probleme auf einer Maschine, unabhängig vom konkreten Computer, gelöst werden können.
  • Sie verstehen praktische Grenzen der algorithmischen Lösbarkeit von Problemen und können die Komplexität spezieller Probleme einschätzen und klassifizieren.
  • Sie sind in der Lage, mit Reduktions- und Simulationstechniken komplexitätstheoretische Untersuchungen anzustellen.
  • Sie verstehen abstrakte Zusammenhänge und können selbstständig mit grundlegenden mathematische Methoden umgehen.
  • Sie können verschiedene Problemlösestrategien und Beweisverfahren anwenden.
Module contents
  • Das Bestreben der Komplexitätstheorie ist es, grundlegende Aussagen zu treffen, mit welchem Zeit- und Speicherplatzaufwand algorithmische Prozesse auf einer Maschine gelöst werden können. Als Grundlage für geräteunabhängige Untersuchungen dient die Turingmaschine, mit der Komplexitätsabschätzungen mathematisch exakt behandelt werden können. Konsequenzen der Resultate für den praktischen Rechnereinsatz erhält man über den Zwischenschritt der Registermaschine.
  • In dem Modul wird untersucht, mit welchem Aufwand ein nichtdeterministscher Algorithmus auf einer deterministischen Maschine simuliert werden kann. Bewiesen werden Enthaltenseinsbeziehungen zwischen verschiedenen Komplexitätsklassen.
  • Zusammenfassend betrachtet das Modul die Inhalte
Komplexitätsmaße für Turing- und Registermaschinen
Raum- und Zeitkomplexität sowie bedeutende Komplexitätsklassen
Deterministische und nichtdeterministische Berechnungen
Hierarchien und Lücken bei Komplexitätsklassen
Reduzierbarkeit und vollständige Probleme
Das P-NP-Problem
Forms of instruction Lecture (3 SWS)
Exercises (1 SWS)
Course
Languages of instruction German, English
Duration (semesters) 1 Semester Semester
Module frequency beginnend im Wintersemester im Wechsel mit
Module capacity unrestricted
Time of examination
Credit points 5 CP
Share on module final degree Course 1: %; Course 2: %; Course 3: %.
Share of module grade on the course of study's final grade 1
Reference text
Vertiefungsmodul für die Vertiefungsrichtung "Algorithmen und Theoretische Informatik" im Masterstudiengang Informatik ab Version 2013.
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
Workload by module 150 150
Total module workload 150
Examination Exam prerequisites Type of examination
Course 1
Course 2
Course 3
Final exam of module
mindestens 50% der Punkte aus den Übungsblättern zur Komplexitätstheorie
mündl. Prüfung oder Klausur
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 %