Lecture: Datenstrukturen und Effiziente Algorithmen II - Details

General information

Course name	Lecture: Datenstrukturen und Effiziente Algorithmen II
Semester	WS 2022/23
Current number of participants	78
Home institute	Leitung des Instituts für Informatik
participating institutes	Praktische Informatik (Datenstrukturen)
Courses type	Lecture in category Offizielle Lehrveranstaltungen
First date	Tuesday, 11.10.2022 08:15 - 09:45, Room: Hörsaal 3.04 [VSP 1]
Type/Form	Vorlesung
Pre-requisites	Modul "Datenstrukturen und Effiziente Algorithmen II"
Performance record	Studienleistung und Klausur
SWS	2+2
ECTS points	5

Lecturers

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

Rooms and times

Hörsaal 3.04 [VSP 1]

Tuesday: 08:15 - 09:45, weekly (15x)

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), Version of accreditation valid from WS 2012/13 > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from 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, valid from 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, valid from WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Inform (Gymnasium) (WLF), Version of accreditation valid from WS 2012/13 > Wahlmodule Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from 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, valid from 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, valid from WS 2006/07 > Course 1: Lecture (Vorlesung)
• Wirtschaftsinformatik Wirtschaftsinformatik180, Version of accreditation valid from WS 2020/21 > 2.2 Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from 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, valid from WS 2006/07 > Course 1: Lecture (Vorlesung)
• Mathematik Mathematik180, Version of accreditation valid from WS 2019/20 > Anwendungsfach Informatik > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from 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, valid from 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, valid from WS 2006/07 > Course 1: Lecture (Vorlesung)
• Bioinformatik Bioinformatik180, Version of accreditation valid from SS 2021 > Informatik (mindestens 10 LP) > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from 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, valid from 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, valid from 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, valid from WS 2006/07 > Course 1: Lecture (Vorlesung)
• Informatik Informatik180, Version of accreditation valid from SS 2021 > Pflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from WS 2006/07 > Course 1: Lecture (Vorlesung)
• Physik PhysikMA120, Version of accreditation valid from WS 2019/20 > Nichtphysikalische Wahlpflichtmodule > INF.00885.06 - Datenstrukturen und Effiziente Algorithmen II, valid from 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, valid from 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, valid from 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, valid from 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, valid from 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, valid from 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, valid from 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, valid from 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, valid from 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, valid from 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, valid from 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, valid from 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, valid from WS 2006/07 > Course 1: Lecture (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