Vorlesung: Datenstrukturen und Effiziente Algorithmen II - Details

Allgemeine Informationen

Veranstaltungsname	Vorlesung: Datenstrukturen und Effiziente Algorithmen II
Semester	WS 2019/20
Aktuelle Anzahl der Teilnehmenden	58
Heimat-Einrichtung	Leitung des Instituts für Informatik
beteiligte Einrichtungen	Praktische Informatik (Datenstrukturen)
Veranstaltungstyp	Vorlesung in der Kategorie Offizielle Lehrveranstaltungen
Erster Termin	Donnerstag, 17.10.2019 10:15 - 11:45, Ort: Hörsaal 1.23 [VSP 1]
Art/Form	Vorlesung
Voraussetzungen	Modul "Datenstrukturen und Effiziente Algorithmen II"
Leistungsnachweis	Studienleistung und Klausur
SWS	2+2
ECTS-Punkte	5

Lecturers

• Prof. Dr. Matthias Müller-Hannemann
• Sebastian Stefan Schmidt

Tutor

• Sara Michalowski

Räume und Zeiten

Hörsaal 1.23 [VSP 1]

Donnerstag: 10:15 - 11:45, wöchentlich (14x)

Hörsaal 3.31 [VSP 1] (Informatik)

Dienstag, 25.02.2020 09:30 - 11:00

(VSP1, 3.07 und 3.28)

Donnerstag, 27.02.2020 10:00 - 12:00

Studienbereiche

• Naturwissenschaftliche Fakultät III - Agrarwiss., Geowiss. und Informatik > Informatik > Institut für Informatik > Bachelor
• Naturwissenschaftliche Fakultät III - Agrarwiss., Geowiss. und Informatik > Informatik > Institut für Informatik > Fachrichtungen > Informatik

Modulzuordnungen

• Informatik Inform (Gymnasium) (ELF), Version of accreditation gültig ab WS 2012/13 > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Informatik (Sekundar) (WLF), Version of accreditation (WS 2007/08 - WS 2015/16) > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Bioinformatik Bioinformatik180, Version of accreditation (WS 2012/13 - SS 2016) > Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Informatik180, Version of accreditation (WS 2006/07 - SS 2012) > Pflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Inform (Gymnasium) (WLF), Version of accreditation gültig ab WS 2012/13 > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Informatik180, Version of accreditation (WS 2012/13 - SS 2016) > Pflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Mathematik Mathematik180, Version of accreditation (WS 2013/14 - SS 2022) > Anwendungsfach Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Informatik (Sekundar) (ELF, WLF), Version of accreditation (WS 2007/08 - SS 2012) > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Wirtschaftsinformatik Wirtschaftsinformatik180, Version of accreditation gültig ab WS 2020/21 > 2.2 Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Inform (Gymnasium) (ELF, WLF), Version of accreditation (WS 2007/08 - SS 2012) > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Informatik180, Version of accreditation (WS 2016/17 - SS 2018) > Pflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Mathematik Mathematik180, Version of accreditation gültig ab WS 2019/20 > Anwendungsfach Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Wirtschaftsmathematik Wirtschaftsmathematik180, Version of accreditation (WS 2013/14 - SS 2022) > Wahlbereich Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Mathematik Mathematik m. Anw.fach180, Version of accreditation (WS 2006/07 - SS 2013) > Anwendungsfach Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Geographie/Erdkunde Geographie180, Version of accreditation (WS 2011/12 - SS 2013) > 10 LP Wahlpflicht > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Bioinformatik Bioinformatik180, Version of accreditation gültig ab SS 2021 > Informatik (mindestens 10 LP) > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Wirtschaftsmathematik WirtschaftsmatheMA120, Version of accreditation (WS 2013/14 - SoSe 2023) > Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Inform (Gymnasium) (ELF), Version of accreditation (WS 2007/08 - SS 2012) > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Inform (Gymnasium) (WLF), Version of accreditation (WS 2007/08 - SS 2012) > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Geographie/Erdkunde Geographie180, Version of accreditation (WS 2006/07 - SS 2011) > 10 LP Wahlpflicht > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Informatik180, Version of accreditation gültig ab SS 2021 > Pflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Physik PhysikMA120, Version of accreditation gültig ab WS 2019/20 > Nichtphysikalische Wahlpflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Geographie/Erdkunde Geographie180, Version of accreditation (WS 2013/14 - SS 2021) > 10 LP Wahlpflicht > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Informatik (Sekundar) (WLF), Version of accreditation (WS 2007/08 - SS 2012) > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Informatik180, Version of accreditation (WS 2018/19 - WS 2022/23) > Pflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Informatik (Sekundar) (ELF), Version of accreditation (WS 2007/08 - SS 2012) > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Bioinformatik Bioinformatik180, Version of accreditation (WS 2016/17 - SS 2018) > Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Informatik (Sekundar) (ELF, WLF), Version of accreditation (WS 2007/08 - WS 2015/16) > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Bioinformatik Bioinformatik180, Version of accreditation (WS 2007/08 - SS 2012) > Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Bioinformatik Bioinformatik180, Version of accreditation (WS 2018/19 - WS 2022/23) > Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Informatik (Sekundar) (ELF), Version of accreditation (WS 2007/08 - WS 2015/16) > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Physik PhysikMA120, Version of accreditation (WS 2009/10 - SS 2019) > Wahlpflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Wirtschaftsmathematik WirtschaftsmatheMA120, Version of accreditation (WS 2006/07 - SS 2013) > Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)
• Wirtschaftsinformatik Wirtschaftsinformatik180, Version of accreditation (SS 2016 - SS 2020) > Wahlbereich Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, gültig ab WS 2006/07 > Course 1: Lecture (Vorlesung)

Kommentar/Beschreibung

Inhalte:
- Polynomialzeitberechenbarkeit und -reduzierbarkeit, NP-Vollständigkeit
- algorithmische Prinzipien (branch-and-bound, Greedy-Algorithmen)
- Höhere Datenstrukturen (balancierte Suchbäume, Prioritätswarteschlangen, union-find)
- Ausgewählte Themen aus den Bereichen Graphenalgorithmen, String-Matching, Zahlentheoretische Algorithmen, Algorithmische Geometrie