Vorlesung: Datenstrukturen und Effiziente Algorithmen II - Details

Allgemeine Informationen

Veranstaltungsname	Vorlesung: Datenstrukturen und Effiziente Algorithmen II
Semester	WS 2022/23
Aktuelle Anzahl der Teilnehmenden	79
Heimat-Einrichtung	Leitung des Instituts für Informatik
beteiligte Einrichtungen	Praktische Informatik (Datenstrukturen)
Veranstaltungstyp	Vorlesung in der Kategorie Offizielle Lehrveranstaltungen
Erster Termin	Dienstag, 11.10.2022 08:15 - 09:45, Ort: Hörsaal 3.04 [VSP 1]
Art/Form	Vorlesung
Voraussetzungen	Modul "Datenstrukturen und Effiziente Algorithmen II"
Leistungsnachweis	Studienleistung und Klausur
SWS	2+2
ECTS-Punkte	5

Lehrende

• Prof. Dr. Matthias Müller-Hannemann
• Dr. Steffen Schüler

Räume und Zeiten

Hörsaal 3.04 [VSP 1]

Dienstag: 08:15 - 09:45, wöchentlich (15x)

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