MLU
INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II (Complete module description)
Original version English
INF.00885.06 5 CP
Module label Datenstrukturen und Effiziente Algorithmen II
Module code INF.00885.06
Semester of first implementation
Faculty/Institute Institut für Informatik
Module used in courses of study / semesters
  • Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation valid from SS 2021 > Informatik (mindestens 10 LP)
  • Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation (WS 2007/08 - SS 2012) > Informatik
  • Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation (WS 2012/13 - SS 2016) > Informatik
  • Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation (WS 2016/17 - SS 2018) > Informatik
  • Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation (WS 2018/19 - WS 2022/23) > Informatik
  • Geographie (180 LP) (Bachelor) > Geographie/Erdkunde Geographie180, Version of accreditation (WS 2006/07 - SS 2011) > 10 LP Wahlpflicht
  • Geographie (180 LP) (Bachelor) > Geographie/Erdkunde Geographie180, Version of accreditation (WS 2011/12 - SS 2013) > 10 LP Wahlpflicht
  • Geographie (180 LP) (Bachelor) > Geographie/Erdkunde Geographie180, Version of accreditation (WS 2013/14 - SS 2021) > 10 LP Wahlpflicht
  • Informatik (180 LP) (Bachelor) > Informatik Informatik180, Version of accreditation valid from SS 2021 > Pflichtmodule
  • Informatik (180 LP) (Bachelor) > Informatik Informatik180, Version of accreditation (WS 2006/07 - SS 2012) > Pflichtmodule
  • Informatik (180 LP) (Bachelor) > Informatik Informatik180, Version of accreditation (WS 2012/13 - SS 2016) > Pflichtmodule
  • Informatik (180 LP) (Bachelor) > Informatik Informatik180, Version of accreditation (WS 2016/17 - SS 2018) > Pflichtmodule
  • Informatik (180 LP) (Bachelor) > Informatik Informatik180, Version of accreditation (WS 2018/19 - WS 2022/23) > Pflichtmodule
  • Informatik (Gymnasium) (ELF) (Lehramt) > Informatik Inform (Gymnasium) (ELF), Version of accreditation valid from WS 2012/13 > Wahlmodule Informatik
  • Informatik (Gymnasium) (ELF) (Lehramt) > Informatik Inform (Gymnasium) (ELF), Version of accreditation (WS 2007/08 - SS 2012) > Wahlmodule Informatik
  • Informatik (Gymnasium) (ELF, WLF) (Lehramt) > Informatik Inform (Gymnasium) (ELF, WLF), Version of accreditation (WS 2007/08 - SS 2012) > Wahlmodule Informatik
  • Informatik (Gymnasium) (WLF) (Lehramt) > Informatik Inform (Gymnasium) (WLF), Version of accreditation valid from WS 2012/13 > Wahlmodule Informatik
  • Informatik (Gymnasium) (WLF) (Lehramt) > Informatik Inform (Gymnasium) (WLF), Version of accreditation (WS 2007/08 - SS 2012) > Wahlmodule Informatik
  • Informatik (Sekundarschule) (ELF) (Lehramt) > Informatik Informatik (Sekundar) (ELF), Version of accreditation (WS 2007/08 - SS 2012) > Wahlmodule Informatik
  • Informatik (Sekundarschule) (ELF) (Lehramt) > Informatik Informatik (Sekundar) (ELF), Version of accreditation (WS 2007/08 - WS 2015/16) > Wahlmodule Informatik
  • Informatik (Sekundarschule) (ELF, WLF) (Lehramt) > Informatik Informatik (Sekundar) (ELF, WLF), Version of accreditation (WS 2007/08 - SS 2012) > Wahlmodule Informatik
  • Informatik (Sekundarschule) (ELF, WLF) (Lehramt) > Informatik Informatik (Sekundar) (ELF, WLF), Version of accreditation (WS 2007/08 - WS 2015/16) > Wahlmodule Informatik
  • Informatik (Sekundarschule) (WLF) (Lehramt) > Informatik Informatik (Sekundar) (WLF), Version of accreditation (WS 2007/08 - SS 2012) > Wahlmodule Informatik
  • Informatik (Sekundarschule) (WLF) (Lehramt) > Informatik Informatik (Sekundar) (WLF), Version of accreditation (WS 2007/08 - WS 2015/16) > Wahlmodule Informatik
  • Mathematik (180 LP) (Bachelor) > Mathematik Mathematik180, Version of accreditation valid from WS 2019/20 > Anwendungsfach Informatik
  • Mathematik (180 LP) (Bachelor) > Mathematik Mathematik180, Version of accreditation (WS 2013/14 - SS 2022) > Anwendungsfach Informatik
  • Mathematik mit Anwendungsfach (180 LP) (Bachelor) > Mathematik Mathematik m. Anw.fach180, Version of accreditation (WS 2006/07 - SS 2013) > Anwendungsfach Informatik
  • 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
  • Wirtschaftsinformatik (Business Information Systems) (180 LP) (Bachelor) > Wirtschaftsinformatik Wirtschaftsinformatik180, Version of accreditation (SS 2016 - SS 2020) > Wahlbereich Informatik
  • Wirtschaftsinformatik (Business Information Systems) (180 LP) (Bachelor) > Wirtschaftsinformatik Wirtschaftsinformatik180, Version of accreditation valid from WS 2020/21 > 2.2 Informatik
  • Wirtschaftsmathematik (180 LP) (Bachelor) > Wirtschaftsmathematik Wirtschaftsmathematik180, Version of accreditation (WS 2013/14 - SS 2022) > Wahlbereich Informatik
  • Wirtschaftsmathematik (MA120 LP) (Master) > Wirtschaftsmathematik WirtschaftsmatheMA120, Version of accreditation (WS 2006/07 - SS 2013) > Informatik
  • Wirtschaftsmathematik (MA120 LP) (Master) > Wirtschaftsmathematik WirtschaftsmatheMA120, Version of accreditation (WS 2013/14 - SoSe 2023) > Informatik
Responsible person for this module
Further responsible persons
Prof. Dr. Matthias Müller-Hannemann
Prerequisites
Skills to be acquired in this module
Studierende sollen durch dieses Modul folgende Kompetenzen erwerben:
  • Sie können algorithmische Probleme bezüglich ihrer Komplexität analysieren und für schwere Probleme den Nachweis der NP-Vollständigkeit selbstständig führen.
  • Sie können algorithmische Lösungsansätze einschätzen und beurteilen, welche Verfahren für konkrete schwere Probleme aussichtsreich sind.
  • Sie können Entwurfsmethoden wie Dynamische Programmierung, Branch-And-Bound oder Greedy-Verfahren auf algorithmische Probleme selbstständig anwenden und zu algorithmischen Lösungen entwickeln, diese in einer objektorientierten Programmiersprache implementieren und testen.
  • Sie besitzen einen Überblick über fortgeschrittene Datenstrukturen, wissen um deren Einsatzgebiete und können auswählen, welche Datenstrukturen für konkrete Problemstellungen angemessen sind.
  • Sie sind vertraut mit Basisalgorithmen zu ausgewählten Anwendungsgebieten (Graphenalgorithmen, String-Matching, zahlentheoretische Algorithmen und Kryptographie sowie in die algorithmische Geometrie) und können deren Leistungsfähigkeit einschätzen.
Module contents
  • Komplexität von Berechnungen
  • Polynomialzeitberechenbarkeit und -reduzierbarkeit, NP-Vollständigkeit
  • Höhere Datenstrukturen (u.a. Prioriätswarteschlangen, union-find, AVL-Bäume, B-Bäume)
  • Designprinzipien für Algorithmen (Greedy-Verfahren, Branch&Bound)
  • Ausgewählte Themen aus den Bereichen Graphenalgorithmen, String-Matching, Zahlentheoretische Methoden, Algorithmische Geometrie
Forms of instruction Lecture (2 SWS)
Exercises (2 SWS)
Course
Course
Languages of instruction German, English
Duration (semesters) 1 Semester Semester
Module frequency jedes Wintersemester
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 2 0
Course 2 Exercises Übung 2 0
Course 3 Course Selbststudium und Prüfungsvorbereitung 0
Course 4 Course Bearbeiten der Übungsausgaben 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
Erfolgreiches Lösen von Übungsaufgaben., Erfolgreiches Vorrechnen von Übungsaufgaben in der Übung
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 %
Course 4 Winter semester No %