Lecture: Datenstrukturen und Effiziente Algorithmen II - Details

General information

Course name	Lecture: Datenstrukturen und Effiziente Algorithmen II
Semester	WS 2020/21
Current number of participants	61
Home institute	Leitung des Instituts für Informatik
participating institutes	Praktische Informatik (Datenstrukturen)
Courses type	Lecture in category Offizielle Lehrveranstaltungen
First date	Thursday, 05.11.2020 10:30 - 12:00
Type/Form	Vorlesung
Pre-requisites	Modul "Datenstrukturen und Effiziente Algorithmen II"
Performance record	Studienleistung und Klausur
Lehrsprache(n)	Deutsch
SWS	2+2
ECTS points	5

Lehrende

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

Rooms and times

Hörsaal 3.07 [VSP 1]

Thursday: 10:30 - 12:00, weekly (1x)

No room preference

Thursday: 10:30 - 12:00, weekly(13x)

Fields of study

• 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

Module assignments

• Informatik Inform (Gymnasium) (ELF), Akkreditierungsfassung valid from WS 2012/13 > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Bioinformatik Bioinformatik180, Akkreditierungsfassung (WS 2012/13 - SS 2016) > Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Informatik Informatik180, Akkreditierungsfassung (WS 2006/07 - SS 2012) > Pflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Informatik Inform (Gymnasium) (WLF), Akkreditierungsfassung valid from WS 2012/13 > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Informatik Informatik180, Akkreditierungsfassung (WS 2012/13 - SS 2016) > Pflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from 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, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Wirtschaftsinformatik Wirtschaftsinformatik180, Akkreditierungsfassung valid from WS 2020/21 > 2.2 Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Informatik Informatik180, Akkreditierungsfassung (WS 2016/17 - SS 2018) > Pflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Mathematik Mathematik180, Akkreditierungsfassung valid from WS 2019/20 > Anwendungsfach Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from 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, valid from 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, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Bioinformatik Bioinformatik180, Akkreditierungsfassung valid from SS 2021 > Informatik (mindestens 10 LP) > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Wirtschaftsmathematik WirtschaftsmatheMA120, Akkreditierungsfassung (WS 2013/14 - SoSe 2023) > Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from 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, valid from 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, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Informatik Informatik180, Akkreditierungsfassung valid from SS 2021 > Pflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Physik PhysikMA120, Akkreditierungsfassung valid from WS 2019/20 > Nichtphysikalische Wahlpflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from 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, valid from 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, valid from 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, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Bioinformatik Bioinformatik180, Akkreditierungsfassung (WS 2016/17 - SS 2018) > Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Bioinformatik Bioinformatik180, Akkreditierungsfassung (WS 2007/08 - SS 2012) > Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from 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, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Physik PhysikMA120, Akkreditierungsfassung (WS 2009/10 - SS 2019) > Wahlpflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Wirtschaftsmathematik WirtschaftsmatheMA120, Akkreditierungsfassung (WS 2006/07 - SS 2013) > Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)
• Wirtschaftsinformatik Wirtschaftsinformatik180, Akkreditierungsfassung (SS 2016 - SS 2020) > Wahlbereich Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from WS 2006/07 > LV 1: Vorlesung (Vorlesung)

Comment/Description

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

Admission settings

The course is part of admission "Anmeldung gesperrt (global)".

The following rules apply for the admission:

• Admission locked.