Datenstrukturen und Effiziente Algorithmen II (gültig ab WS 2006/07) (Vollständige Modulbeschreibung)

INF.00885.07	5 CP
Modulbezeichnung	Datenstrukturen und Effiziente Algorithmen II
Modulcode	INF.00885.07
Semester der erstmaligen Durchführung
Fachbereich/Institut	Institut für Informatik
Verwendet in Studiengängen / Semestern	Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, . Akkreditierungsfassung gültig ab SS 2021 > Informatik (mindestens 10 LP) Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, . Akkreditierungsfassung WS 2007/08 - SS 2012 > Informatik Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, . Akkreditierungsfassung WS 2012/13 - SS 2016 > Informatik Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, . Akkreditierungsfassung WS 2016/17 - SS 2018 > Informatik Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, . Akkreditierungsfassung WS 2018/19 - WS 2022/23 > Informatik mehr... Geographie (180 LP) (Bachelor) > Geographie/Erdkunde Geographie180, . Akkreditierungsfassung WS 2006/07 - SS 2011 > 10 LP Wahlpflicht Geographie (180 LP) (Bachelor) > Geographie/Erdkunde Geographie180, . Akkreditierungsfassung WS 2011/12 - SS 2013 > 10 LP Wahlpflicht Geographie (180 LP) (Bachelor) > Geographie/Erdkunde Geographie180, . Akkreditierungsfassung WS 2013/14 - SS 2021 > 10 LP Wahlpflicht Informatik (180 LP) (Bachelor) > Informatik Informatik180, . Akkreditierungsfassung gültig ab SS 2021 > Pflichtmodule Informatik (180 LP) (Bachelor) > Informatik Informatik180, . Akkreditierungsfassung gültig ab WiSe 2026/27 > Pflichtmodule Informatik (180 LP) (Bachelor) > Informatik Informatik180, . Akkreditierungsfassung WS 2006/07 - SS 2012 > Pflichtmodule Informatik (180 LP) (Bachelor) > Informatik Informatik180, . Akkreditierungsfassung WS 2012/13 - SS 2016 > Pflichtmodule Informatik (180 LP) (Bachelor) > Informatik Informatik180, . Akkreditierungsfassung WS 2016/17 - SS 2018 > Pflichtmodule Informatik (180 LP) (Bachelor) > Informatik Informatik180, . Akkreditierungsfassung WS 2018/19 - WS 2022/23 > Pflichtmodule Informatik (Gymnasium) (ELF) (Lehramt) > Informatik Inform (Gymnasium) (ELF), . Akkreditierungsfassung gültig ab WS 2012/13 > Wahlmodule Informatik Informatik (Gymnasium) (ELF) (Lehramt) > Informatik Inform (Gymnasium) (ELF), . Akkreditierungsfassung WS 2007/08 - SS 2012 > Wahlmodule Informatik Informatik (Gymnasium) (ELF, WLF) (Lehramt) > Informatik Inform (Gymnasium) (ELF, WLF), . Akkreditierungsfassung WS 2007/08 - SS 2012 > Wahlmodule Informatik Informatik (Gymnasium) (WLF) (Lehramt) > Informatik Inform (Gymnasium) (WLF), . Akkreditierungsfassung gültig ab WS 2012/13 > Wahlmodule Informatik Informatik (Gymnasium) (WLF) (Lehramt) > Informatik Inform (Gymnasium) (WLF), . Akkreditierungsfassung WS 2007/08 - SS 2012 > Wahlmodule Informatik Informatik (Sekundarschule) (ELF) (Lehramt) > Informatik Informatik (Sekundar) (ELF), . Akkreditierungsfassung WS 2007/08 - SS 2012 > Wahlmodule Informatik Informatik (Sekundarschule) (ELF) (Lehramt) > Informatik Informatik (Sekundar) (ELF), . Akkreditierungsfassung WS 2007/08 - WS 2015/16 > Wahlmodule Informatik Informatik (Sekundarschule) (ELF, WLF) (Lehramt) > Informatik Informatik (Sekundar) (ELF, WLF), . Akkreditierungsfassung WS 2007/08 - SS 2012 > Wahlmodule Informatik Informatik (Sekundarschule) (ELF, WLF) (Lehramt) > Informatik Informatik (Sekundar) (ELF, WLF), . Akkreditierungsfassung WS 2007/08 - WS 2015/16 > Wahlmodule Informatik Informatik (Sekundarschule) (WLF) (Lehramt) > Informatik Informatik (Sekundar) (WLF), . Akkreditierungsfassung WS 2007/08 - SS 2012 > Wahlmodule Informatik Informatik (Sekundarschule) (WLF) (Lehramt) > Informatik Informatik (Sekundar) (WLF), . Akkreditierungsfassung WS 2007/08 - WS 2015/16 > Wahlmodule Informatik Mathematik (180 LP) (Bachelor) > Mathematik Mathematik180, . Akkreditierungsfassung gültig ab WS 2019/20 > Anwendungsfach Informatik Mathematik (180 LP) (Bachelor) > Mathematik Mathematik180, . Akkreditierungsfassung WS 2013/14 - SS 2022 > Anwendungsfach Informatik Mathematik mit Anwendungsfach (180 LP) (Bachelor) > Mathematik Mathematik m. Anw.fach180, . Akkreditierungsfassung WS 2006/07 - SS 2013 > Anwendungsfach Informatik 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 Wirtschaftsinformatik (Business Information Systems) (180 LP) (Bachelor) > Wirtschaftsinformatik Wirtschaftsinformatik180, . Akkreditierungsfassung gültig ab WS 2020/21 > 2.2 Informatik Wirtschaftsinformatik (Business Information Systems) (180 LP) (Bachelor) > Wirtschaftsinformatik Wirtschaftsinformatik180, . Akkreditierungsfassung SS 2016 - SS 2020 > Wahlbereich Informatik Wirtschaftsmathematik (180 LP) (Bachelor) > Wirtschaftsmathematik Wirtschaftsmathematik180, . Akkreditierungsfassung WS 2013/14 - SS 2022 > Wahlbereich Informatik Wirtschaftsmathematik (MA120 LP) (Master) > Wirtschaftsmathematik WirtschaftsmatheMA120, . Akkreditierungsfassung WS 2006/07 - SS 2013 > Informatik Wirtschaftsmathematik (MA120 LP) (Master) > Wirtschaftsmathematik WirtschaftsmatheMA120, . Akkreditierungsfassung WS 2013/14 - SoSe 2026 > Informatik
Modulverantwortliche/r
Weitere verantwortliche Personen	Prof. Dr. Matthias Müller-Hannemann
Teilnahmevoraussetzungen
Kompetenzziele	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.
Modulinhalte	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
Lehrveranstaltungsformen	Vorlesung (2 SWS) Übung (2 SWS) Kursus Kursus
Unterrichtsprachen	Deutsch, Englisch
Dauer in Semestern	1 Semester Semester
Angebotsrhythmus Modul	jedes Wintersemester
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

Modulveranstaltung	Lehrveranstaltungsform	Veranstaltungstitel	SWS	Workload selbstgestaltete Arbeit	Workload Summe
LV 1	Vorlesung	Vorlesung	2		0
LV 2	Übung	Übung	2		0
LV 3	Kursus	Selbststudium und Prüfungsvorbereitung			0
LV 4	Kursus	Bearbeiten der Übungsausgaben			0
Workload modulbezogen				150	150
Workload Modul insgesamt					150

Prüfung	Prüfungsvorleistung	Prüfungsform
LV 1
LV 2
LV 3
LV 4
Gesamtmodul	Bearbeiten und Lösen von Theorie- und Programmieraufgaben, Präsentation eigener Lösungswege in den Übungen	mündl. Prüfung oder Klausur
Wiederholungsprüfung

Regularien	Angebotsrhythmus	Anwesenheitspflicht	Gewicht an Modulnote in %
LV 1	Wintersemester	Nein	%
LV 2	Wintersemester	Nein	%
LV 3	Wintersemester	Nein	%
LV 4	Wintersemester	Nein	%