Algorithmenparadigmen

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

BESTANDTEILE UND VERANSTALTUNGSART

Algorithmenparadigmen – Vorlesung (2 SWS)
Algorithmenparadigmen – Übung (2 SWS)

PRÜFUNGEN

FORM: schriftlich
ANMELDUNG: eCampus
DATUM: 0000-00-00
BEGINN: 00:00:00
DAUER: 120 min
RAUM:

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

Inhalte der Pflichtmodule Mathematik (Module Mathematik 1 – Grundlagen, Mathematik 2 – Algorithmische Mathematik und Mathematik 3 – Anwendungen) und Informatik (Module Informatik 1 – Programmieren, Informatik 2 – Algorithmen und Datenstrukturen und Informatik 3 – Theoretische Informatik)

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

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.