Algorithmenparadigmen

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

INFOS

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


PRÜFUNGUNGSFORM

Schriftliche Modulabschlussprüfung über 120 Minuten


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


Algorithm Paradigms

NUMMER: n.n. KÜRZEL: AlgPara DOZENT: Prof.‘in Dr. Maike Buchin FAKULTÄT: Fakultät für Mathematik SPRACHE: English SWS: 4 SWS CREDITS: 5 CP WORKLOAD: 150 h ANGEBOTEN IM: each winter semester

INFOS

Algorithm paradigms – Lecture (2 SWS)
bAlgorithm paradigms – Exercise (2 SWS)


PRÜFUNGUNGSFORM

Written final exam of 120 Minutes


LERNFORM

Lecture with media support as well as tutorials as seminar lessons


LERNZIELE

After successfully completing the module
- Students know a number of algorithm paradigms
- Students can develop efficient algorithms for problems based on the paradigms
- students understand the advantages and disadvantages of different paradigms


INHALT

In the lecture different algorithm paradigms are considered, i.e. schemes for the design of efficient algorithms. For this purpose, the already known paradigms incremental, divide-and-conquer and greedy are first examined and these are applied to various problems. Based on this, dynamic programming is taught and the backtracking and branch-and-bound methods are presented. A paradigm especially for geometric problems - the sweepline method - is also considered.


VORAUSSETZUNGEN

Contents of the mandatory courses Mathematics (modules Mathematics 1 - Basics, Mathematics 2 - Algorithmic Mathematics and Mathematics 3 - Applications) and Computer Science (Modules Computer Science 1 - Programming, Computer Science 2 - Algorithms and Data Structures and Computer Science 3 - Theoretical Computer Science)


VORAUSSETZUNGEN CREDITS

Passed examination


EMPFOHLENE VORKENNTNISSE

Design and analysis of algorithms and data structures


LITERATUR

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