Home | deutsch  | Legals | Sitemap | KIT

Algorithmen II

Algorithmen II
Type: Vorlesung (V)
Semester: WS 16/17
Time: 18.10.2016
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude


19.10.2016
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

25.10.2016
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

26.10.2016
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

02.11.2016
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

08.11.2016
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

09.11.2016
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

15.11.2016
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

16.11.2016
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

22.11.2016
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

23.11.2016
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

29.11.2016
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

30.11.2016
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

06.12.2016
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

07.12.2016
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

13.12.2016
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

14.12.2016
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

20.12.2016
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

21.12.2016
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

28.12.2016
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

04.01.2017
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

10.01.2017
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

11.01.2017
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

17.01.2017
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

18.01.2017
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

24.01.2017
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

25.01.2017
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude

31.01.2017
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

07.02.2017
15:45 - 17:15 wöchentlich
30.46 Neue Chem 30.46 Chemie-Hörsaalgebäude

08.02.2017
15:45 - 17:15 wöchentlich
50.35 HS a. F. 50.35 Fasanengarten-Hörsaalgebäude


Lecturer: Prof.Dr. Peter Sanders
Dr. Simon Gog
Dr. Christian Schulz
SWS: 4
Lv-No.: 24079
Voraussetzungen

Siehe Modubeschreibung.

Literaturhinweise

K. Mehlhorn, P. Sanders: Algorithms and Data Structures - The Basic Toolbox

Mehlhorn, Naeher: The LEDA Platform of Combinatorial and Geometric Computing  Topic: Algorithm Engineering, Flows, Geometrie

Ahuja, Magnanti, Orlin: Network Flows

de Berg, Cheong, van Kreveld, Overmars: Computational Geometry: Algorithms and Applications

Gonzalo Navarro: Compact Data Structures "A Practical Approach", Cambridge University Press

R. Niedermeier: Invitation to Fixed-Parameter Algorithms, Oxford University Press, 2006.

Lehrinhalt

Diese Lehrveranstaltung soll Studierenden die grundlegenden theoretischen und praktischen Aspekte der Algorithmentechnik vermitteln. Es werden generelle Methoden zum Entwurf und der Analyse von Algorithmen für grundlegende algorithmische Probleme vermittelt sowie die Grundzüge allgemeiner algorithmischer Methoden wie Approximationsalgorithmen, Lineare Programmierung, Randomisierte Algorithmen, Parallele Algorithmen und parametrisierte Algorithmen behandelt.

Arbeitsbelastung

Vorlesung mit 3 SWS + 1 SWS Übung.

6 LP entspricht ca. 180 Stunden

ca. 45 Std. Vorlesungsbesuch,

ca. 15 Std. Übungsbesuch,

ca. 90 Std. Nachbearbeitung und Bearbeitung der Übungsblätter

ca. 30 Std. Prüfungsvorbereitung

Ziel

Der/die Studierende besitzt einen vertieften Einblick in die theoretischen und praktischen Aspekte der Algorithmik und kann algorithmische Probleme in verschiedenen Anwendungsgebieten identifizieren und formal formulieren. Außerdem kennt er/sie weiterführende Algorithmen und Datenstrukturen aus den Bereichen Graphenalgorithmen, Algorithmische Geometrie, String-Matching, Algebraische Algorithmen, Kombinatorische Optimierung und Algorithmen für externen Speicher.

Er/Sie kann unbekannte Algorithmen eigenständig verstehen, sie den genannten Gebieten zuordnen, sie anwenden, ihre Laufzeit bestimmen, sie beurteilen sowie geeignete Algorithmen für gegebene Anwendungen auswählen. Darüber hinaus ist der/die Studierende in der Lage, bestehende Algorithmen auf verwandte Problemstellungen zu übertragen.

Neben Algorithmen für konkrete Problemstellungen kennt der/die Studierende fortgeschrittene Techniken des algorithmischen Entwurfs. Dies umfasst parametrisierte Algorithmen, approximierende Algorithmen, Online-Algorithmen, randomisierte Algorithmen, parallele Algorithmen, lineare Programmierung, sowie Techniken des Algorithm Engenieering. Für gegebene Algorithmen kann der/die Studierende eingesetzte Techniken identifizieren und damit diese Algorithmen besser verstehen. Darüber hinaus kann er/sie für eine gegebene Problemstellung geeignete Techniken auswählen und sie nutzen, um eigene Algorithmen zu entwerfen.

Prüfung

Die Erfolgskontrolle erfolgt in Form einer schriftlichen Prüfung im Umfang von 120 Minuten nach § 4 Abs. 2 Nr. 1 SPO.

Klausur am 22.02.2017

Sie können sich ab sofort und noch bis einschließlich 15.02.2017 am Studierendenportal anmelden, die Abmeldung ist bis einschließlich 21.02.2017 möglich. Bei Anmeldungen in Papierform gelten dieselben Fristen, bitte geben Sie die Prüfungszulassung im Sekretariat von Prof. Sanders ab.

Skript:

Folien:

`

Übungen:

Übungsblätter:

Programmier-Challenge: