INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II (Vollständige Modulbeschreibung)

INF.00885.06	5 CP
Modulbezeichnung	Datenstrukturen und Effiziente Algorithmen II
Modulcode	INF.00885.06
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 (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 2023) > 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	Erfolgreiches Lösen von Übungsaufgaben., Erfolgreiches Vorrechnen von Übungsaufgaben in der Übung	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	%