Algorithm Engineering

  • Type: Vorlesung (V)
  • Semester: SS 2020
  • Time: 21.04.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten


    28.04.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    05.05.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    12.05.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    19.05.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    26.05.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    02.06.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    09.06.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    16.06.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    23.06.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    30.06.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    07.07.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    14.07.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten

    21.07.2020
    15:45 - 17:15 wöchentlich
    50.34 Raum 236
    50.34 INFORMATIK, Kollegiengebäude am Fasanengarten


  • Lecturer: Dominik Schreiber
    Prof. Dr. Peter Sanders
  • SWS: 2/1
  • Lv-No.: 2400051
Beschreibung

Die Studierenden erwerben in dieser Veranstaltung ein systematisches Verständnis algorithmischer Fragestellungen und Lösungsansätze im Bereich Algorithm Engineering, das auf dem bestehenden Wissen im Themenbereich Algorithmik aufbaut. Außerdem können sie erlernte Techniken auf verwandte Fragestellungen anwenden und aktuelle Forschungsthemen im Bereich Algorithm Engineering interpretieren und nachvollziehen.

Lehrinhalt
  • Was ist Algorithm Engineering, Motivation etc.
  • realistische Modellierung von Maschinen und Anwendungen
  • praxisorientierter Algorithmenentwurf
  • Implementierungstechniken
  • Experimentiertechniken
  • Auswertung von Messungen

Die oben angegebenen Fertigkeiten werden vor allem anhand von konkreten Beispielen gelehrt. In der Vergangenheit waren das zum Beispiel die folgenden Themen aus dem Bereich grundlegender Algorithmen und Datenstrukturen:

  • linked lists ohne Sonderfälle
  • Sortieren: parallel, extern, superskalar,...
  • Prioritätslisten (cache effizient,...)
  • Suchbäume für ganzzahlige Schlüssel
  • Volltextindizes
  • Graphenalgorithmen: miminale Spannbäume (extern,...), Routenplanung

Dabei geht es jeweils um die besten bekannten praktischen und theoretischen Verfahren. Diese weichen meist erheblich von den in Anfängervorlesungen gelehrten Verfahren ab.

Arbeitsbelastung

Vorlesung und Übung mit 3 SWS, 5 LP entsprechen ca. 150 Arbeitsstunden, davon

ca. 30 Std. Besuch der Vorlesung und Übung bzw. Blockseminar
ca. 60 Std. Vor- und Nachbereitung
ca. 30 Std. Bearbeitung der Übungsblätter/Vorbereitung Minisemiar
ca. 30 Std. Prüfungsvorbereitung

Ziel

Nach erfolgreicher Teilnahme an der Lehrveranstaltung können die Studierenden

  • Begriffe, Strukturen, grundlegende Problemdefinitionen und Algorithmen aus der Vorlesung erklären;
  • auswählen, welche Algorithmen und Datenstrukturen zur Lösung einer algorithmischen Fragestellung geeignet sind und diese ggf. den Anforderungen einer konkreten Problemstellung anpassen;
  • Algorithmen und Datenstrukturen ausführen, mathematisch präzise analysieren und die algorithmischen Eigenschaften beweisen;
  • Maschinenmodelle aus der Vorlesung erklären sowie Algorithmen und Datenstrukturen in diesen analysieren;
  • neue Probleme aus Anwendungen analysieren, auf den algorithmischen Kern reduzieren und daraus ein abstraktes Modell erstellen; auf Basis der in der Vorlesung erlernten Konzepte und Techniken eigene Lösungen in diesem Modell entwerfen, analysieren und die algorithmischen Eigenschaften beweisen.
Prüfung

Die Erfolgskontrolle erfolgt in Form einer mündlichen Prüfung nach § 4 Abs. 2 Nr. 2 SPO und einer Übung als Erfolgskontrolle anderer Art nach § 2 Abs. 2 Nr. 3.
Gewichtung: 80 % mündliche Prüfung, 20 % Übung.

Beschreibung

 

Die Studierenden erwerben in dieser Veranstaltung ein systematisches Verständnis algorithmischer Fragestellungen und Lösungsansätze im Bereich Algorithm Engineering, das auf dem bestehenden Wissen im Themenbereich Algorithmik aufbaut. Außerdem können sie erlernte Techniken auf verwandte Fragestellungen anwenden und aktuelle Forschungsthemen im Bereich Algorithm Engineering interpretieren und nachvollziehen.

Lehrinhalt
  • Was ist Algorithm Engineering, Motivation etc.
  • realistische Modellierung von Maschinen und Anwendungen
  • praxisorientierter Algorithmenentwurf
  • Implementierungstechniken
  • Experimentiertechniken
  • Auswertung von Messungen

Die oben angegebenen Fertigkeiten werden vor allem anhand von konkreten Beispielen gelehrt. In der Vergangenheit waren das zum Beispiel die folgenden Themen aus dem Bereich grundlegender Algorithmen und Datenstrukturen:

  • linked lists ohne Sonderfälle
  • Sortieren: parallel, extern, superskalar,...
  • Prioritätslisten (cache effizient,...)
  • Suchbäume für ganzzahlige Schlüssel
  • Volltextindizes
  • Graphenalgorithmen: miminale Spannbäume (extern,...), Routenplanung

Dabei geht es jeweils um die besten bekannten praktischen und theoretischen Verfahren. Diese weichen meist erheblich von den in Anfängervorlesungen gelehrten Verfahren ab.

Arbeitsbelastung

Vorlesung und Übung mit 3 SWS, 5 LP entsprechen ca. 150 Arbeitsstunden, davon

ca. 30 Std. Besuch der Vorlesung und Übung bzw. Blockseminar
ca. 60 Std. Vor- und Nachbereitung
ca. 30 Std. Bearbeitung der Übungsblätter/Vorbereitung Minisemiar
ca. 30 Std. Prüfungsvorbereitung

Ziel

Nach erfolgreicher Teilnahme an der Lehrveranstaltung können die Studierenden

  • Begriffe, Strukturen, grundlegende Problemdefinitionen und Algorithmen aus der Vorlesung erklären;
  • auswählen, welche Algorithmen und Datenstrukturen zur Lösung einer algorithmischen Fragestellung geeignet sind und diese ggf. den Anforderungen einer konkreten Problemstellung anpassen;
  • Algorithmen und Datenstrukturen ausführen, mathematisch präzise analysieren und die algorithmischen Eigenschaften beweisen;
  • Maschinenmodelle aus der Vorlesung erklären sowie Algorithmen und Datenstrukturen in diesen analysieren;
  • neue Probleme aus Anwendungen analysieren, auf den algorithmischen Kern reduzieren und daraus ein abstraktes Modell erstellen; auf Basis der in der Vorlesung erlernten Konzepte und Techniken eigene Lösungen in diesem Modell entwerfen, analysieren und die algorithmischen Eigenschaften beweisen.
Prüfung

Die Erfolgskontrolle erfolgt in Form einer mündlichen Prüfung nach § 4 Abs. 2 Nr. 2 SPO und einer Übung als Erfolgskontrolle anderer Art nach § 2 Abs. 2 Nr. 3.
Gewichtung: 80 % mündliche Prüfung, 20 % Übung.