Algorithmenparadigmen

NUMMER: 211043
KÜRZEL: AlgPara
MODULBEAUFTRAGTE:R: Prof. Dr. Buchin Maike
DOZENT:IN: Prof. Dr. Maike Buchin
FAKULTÄT: Fakultät für Informatik
SPRACHE: Deutsch
SWS: 4 SWS
CREDITS: 5 CP
ANGEBOTEN IM: jedes Wintersemester

PRÜFUNGEN

FORM: schriftlich
TERMIN: Siehe Prüfungsamt.

LERNFORM

Hörsaalvorlesung mit Medienunterstützung sowie Tutorien als seminaristischer Unterricht

LERNZIELE

Nach dem erfolgreichen Abschluss des Moduls

- kennen Studierende eine Reihe von Algorithmenparadigmen
- können Studierende basierend auf den Paradigmen effiziente Algorithmen für Probleme entwickeln
- verstehen Studierende die Vor- und Nachteile unterschiedlicher Paradigmen

INHALT

In der Vorlesung werden unterschiedliche Algorithmenparadigmen betrachtet, also Schemata zum Entwurf von effizienten Algorithmen. Dazu werden zunächst die bereits bekannten Paradigmen inkrementell, Teile-und-Herrsche und gierig beleuchtet und diese werden auf verschiedene Probleme angewendet. Darauf aufbauend wird Dynamisches Programmieren gelehrt sowie die Methoden Backtracking und Branch-and-Bound vorgestellt. Auch ein Paradigma speziell für geometrische Probleme – das Sweepline-Verfahren – wird betrachtet.

VORAUSSETZUNGEN CREDITS

Bestandene Modulabschlussprüfung

EMPFOHLENE VORKENNTNISSE

Entwurf und Analyse von Algorithmen und Datenstrukturen

LITERATUR

J. Kleinberg, E. Tardos: „Algorithm Design”, Pearson Education

AKTUELLE INFORMATIONEN

Die Veranstaltung entfällt im WS 22/23.

SONSTIGE INFORMATIONEN

Aktuelle Informationen wie Vorlesungstermine, Räume oder aktuelle Dozent*innen und Übungsleiter*innen sind im Vorlesungsverzeichnis der Ruhr-Universität https://vvz.rub.de/ und im eCampus https://www.rub.de/ecampus/ecampus-webclient/ zu finden.