INF.00885.07 - Datenstrukturen und Effiziente Algorithmen II (Complete module description)

INF.00885.07 - Datenstrukturen und Effiziente Algorithmen II (Complete module description)

Original version English
INF.00885.07 5 CP
Module label Datenstrukturen und Effiziente Algorithmen II
Module code INF.00885.07
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 2026) > 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 unrestricted
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
Bearbeiten und Lösen von Theorie- und Programmieraufgaben, Präsentation eigener Lösungswege in den Übungen
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 %