| 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
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