INF.00679.07 - Datenstrukturen und Effiziente Algorithmen I (Complete module description)

INF.00679.07	5 CP
Module label	Datenstrukturen und Effiziente Algorithmen I
Module code	INF.00679.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 > Pflichtmodule Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation (WS 2012/13 - SS 2016) > Pflichtmodule Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation (WS 2016/17 - SS 2018) > Pflichtmodule Bioinformatik (180 LP) (Bachelor) > Bioinformatik Bioinformatik180, Version of accreditation (WS 2018/19 - WS 2022/23) > Pflichtmodule more... Bioinformatik (MA120 LP) (Master) > Bioinformatik BioinformatikMA120, Version of accreditation (WS 2016/17 - WS 2022/23) > Brückenmodule Informatik 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 > Pflichtmodule Informatik (Gymnasium) (ELF) (Lehramt) > Informatik Inform (Gymnasium) (ELF), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Gymnasium) (ELF, WLF) (Lehramt) > Informatik Inform (Gymnasium) (ELF, WLF), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Gymnasium) () (Lehramt) > Informatik Inform (Gymnasium), Version of accreditation valid from WS 2012/13 > Pflichtmodule Informatik (Gymnasium) () (Lehramt) > Informatik Inform (Gymnasium), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Gymnasium) (WLF) (Lehramt) > Informatik Inform (Gymnasium) (WLF), Version of accreditation valid from WS 2012/13 > Pflichtmodule Informatik (Gymnasium) (WLF) (Lehramt) > Informatik Inform (Gymnasium) (WLF), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Sekundarschule) (ELF) (Lehramt) > Informatik Informatik (Sekundar) (ELF), Version of accreditation valid from WS 2019/20 > Pflichtmodule Informatik (Sekundarschule) (ELF) (Lehramt) > Informatik Informatik (Sekundar) (ELF), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Sekundarschule) (ELF) (Lehramt) > Informatik Informatik (Sekundar) (ELF), Version of accreditation (WS 2007/08 - WS 2015/16) > Pflichtmodule Informatik (Sekundarschule) (ELF, WLF) (Lehramt) > Informatik Informatik (Sekundar) (ELF, WLF), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Sekundarschule) (ELF, WLF) (Lehramt) > Informatik Informatik (Sekundar) (ELF, WLF), Version of accreditation (WS 2007/08 - WS 2015/16) > Pflichtmodule Informatik (Sekundarschule) () (Lehramt) > Informatik Informatik (Sekundar), Version of accreditation valid from WS 2019/20 > Pflichtmodule Informatik (Sekundarschule) () (Lehramt) > Informatik Informatik (Sekundar), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Sekundarschule) () (Lehramt) > Informatik Informatik (Sekundar), Version of accreditation (WS 2007/08 - WS 2015/16) > Pflichtmodule Informatik (Sekundarschule) (WLF) (Lehramt) > Informatik Informatik (Sekundar) (WLF), Version of accreditation valid from WS 2019/20 > Pflichtmodule Informatik (Sekundarschule) (WLF) (Lehramt) > Informatik Informatik (Sekundar) (WLF), Version of accreditation (WS 2007/08 - SS 2012) > Pflichtmodule Informatik (Sekundarschule) (WLF) (Lehramt) > Informatik Informatik (Sekundar) (WLF), Version of accreditation (WS 2007/08 - WS 2015/16) > Pflichtmodule Kernfach Wirtschaftsinformatik (Core Subject Business Information Systems) (120 LP) (Bachelor) > Wirtschaftsinformatik Wirtschaftsinformatik120, Version of accreditation (WS 2006/07 - SS 2008) > Pflichtmodule Kernfach Wirtschaftsinformatik (Core Subject Business Information Systems) (120 LP) (Bachelor) > Wirtschaftsinformatik Wirtschaftsinformatik120, Version of accreditation (WS 2008/09 - SS 2010) > Pflichtmodule Mathematik (180 LP) (Bachelor) > Mathematik Mathematik180, Version of accreditation valid from WS 2019/20 > Pflichtmodule Mathematik (180 LP) (Bachelor) > Mathematik Mathematik180, Version of accreditation (WS 2013/14 - SS 2022) > Pflichtmodule Mathematik mit Anwendungsfach (180 LP) (Bachelor) > Mathematik Mathematik m. Anw.fach180, Version of accreditation (WS 2006/07 - SS 2013) > Informatik Physik (180 LP) (Bachelor) > Physik Physik180, Version of accreditation valid from WS 2019/20 > Nichtphysikalische Ergänzungsmodule Physik (180 LP) (Bachelor) > Physik Physik180, Version of accreditation (WS 2006/07 - SS 2012) > Nichtphysikalische Ergänzungsmodule Physik (180 LP) (Bachelor) > Physik Physik180, Version of accreditation (WS 2012/13 - SS 2019) > Nichtphysikalische Ergänzungsmodule Physik und Digitale Technologien (180 LP) (Bachelor) > Physik Physik u. Dig. Tech. 180, Version of accreditation valid from WS 2019/20 > Pflichtmodule 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 > 1.3 Informatik Wirtschaftsinformatik (Business Information Systems) (180 LP) (Bachelor) > Wirtschaftsinformatik Wirtschaftsinformatik180, Version of accreditation (WS 2006/07 - SS 2008) > Pflichtmodule Wirtschaftsinformatik (Business Information Systems) (180 LP) (Bachelor) > Wirtschaftsinformatik Wirtschaftsinformatik180, Version of accreditation (WS 2008/09 - WS 2015/16) > Pflichtmodule Wirtschaftsmathematik (180 LP) (Bachelor) > Wirtschaftsmathematik Wirtschaftsmathematik180, Version of accreditation valid from WS 2019/20 > Pflichtmodule Wirtschaftsmathematik (180 LP) (Bachelor) > Wirtschaftsmathematik Wirtschaftsmathematik180, Version of accreditation (WS 2006/07 - SS 2013) > Informatik Wirtschaftsmathematik (180 LP) (Bachelor) > Wirtschaftsmathematik Wirtschaftsmathematik180, Version of accreditation (WS 2013/14 - SS 2022) > Pflichtmodule
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 kennen die grundlegenden Methoden zum Entwurf von Algorithmen und können diese Entwurfsmethoden auf algorithmische Problemstellungen anwenden. Sie sind in der Lage, für neue Problemstellungen geeignete Methoden auszuwählen und selbstständig algorithmische Lösungen zu entwickeln. Sie können die Korrektheit von Algorithmen überprüfen, geeignete Invarianten herleiten und formale Korrektheitsbeweise führen. Sie erwerben die Fähigkeit, Laufzeit und Speicherbedarf eines Algorithmus asymptotisch abschätzen zu können und insbesondere rekursive Algorithmen zu analysieren. Sie besitzen einen Überblick über die wichtigsten elementaren Datenstrukturen und können deren Vor- und Nachteile beurteilen. Sie verstehen, dass die Effizienz eines Algorithmus von der geeigneten Wahl der Datenstrukturen abhängt, und können eigenständig die Auswahl der Datenstrukturen treffen. Sie können einfache Algorithmen effizient in einer objektorientierten Programmiersprache implementieren und testen.
Module contents	Korrektheit von Algorithmen: Verifikation Asymptotische Kosten eines Algorithmus: Effizienzanalyse Grundlegende Datenstrukturen (Felder, Listen, Bäume, Queues, Stacks) Rekursive Algorithmen, Rekurrenzgleichungen Sortierverfahren (Mergesort, Quicksort, Heapsort, Bucketsort) Suchen: Wörterbücher, Suchbäume, Hashing einfache Graphenalgorithmen (Tiefen- und Breitensuche, Zusammenhang, kürzeste Wegeprobleme) algorithmische Prinzipien: dynamisches Programmieren, divide and conquer
Forms of instruction	Lecture (2 SWS) Exercises (2 SWS) Course Course Course
Languages of instruction	German, English
Duration (semesters)	1 Semester Semester
Module frequency	jedes Sommersemester
Module capacity	unlimited
Time of examination
Credit points	5 CP
Share on module final degree	Course 1: %; Course 2: %; Course 3: %; Course 4: %; Course 5: %.
Share of module grade on the course of study's final grade	1

Module course label	Course type	Course title	SWS	Workload of independent learning	Sum workload
Course 1	Lecture	Vorlesung	2		0
Course 2	Exercises	Übung	2		0
Course 3	Course	Bearbeiten der Übungsausgaben			0
Course 4	Course	Bearbeiten praktischer Programmieraufgaben			0
Course 5	Course	Selbststudium			0
Workload by module				150	150
Total module workload					150

Examination	Exam prerequisites	Type of examination
Course 1
Course 2
Course 3
Course 4
Course 5
Final exam of module	Erfolgreiches Lösen von Übungsaufgaben, Korrekte Bearbeitung der Programmieraufgaben, Erfolgreiches Vorrechnen von Übungsaufgaben in der Übung	mündl. Prüfung oder Klausur
Exam repetition information

Prerequisites and conditions	Frequency	Compulsory attendance	Share on module grade in percent
Course 1	Summer semester	No	%
Course 2	Summer semester	No	%
Course 3	Summer semester	No	%
Course 4	Summer semester	No	%
Course 5	Summer semester	No	%