Modul
Algorithm Engineering [M-INFO-100795]
Leistungspunkte
5Turnus
Jedes SommersemesterDauer
1 SemesterSprache
Deutsch/EnglischLevel
4Version
3Verantwortung
Einrichtung
- KIT-Fakultät für Informatik
Bestandteil von
Teilleistungen
Identifier | Name | LP |
---|---|---|
T-INFO-111856 | Algorithm Engineering Übung | 1 |
T-INFO-101332 | Algorithm Engineering | 4 |
Erfolgskontrolle(n)
Siehe Teilleistung
Qualifikationsziele
Die Studierenden erwerben 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 kann er/sie erlernte Techniken auf verwandte Fragestellungen anwenden und aktuelle Forschungsthemen im Bereich Algorithm Engineering interpretieren und nachvollziehen.
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 Datenstruktuen 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;
- Machinenmodelle 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.
Voraussetzungen
Siehe Teilleistung
Inhalt
- Was ist Algorithm Engineering, Motivation etc.
- Realisteische 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.
Arbeitsaufwand
Vorlesung und Übung mit 3 SWS, 5 LP
5 LP entspricht ca. 150 Arbeitsstunden, davon
ca. 45 Std. Besuch der Vorlesung und Übung bzw. Blockseminar,
ca. 25 Std. Vor- und Nachbereitung,
ca. 40 Std. Bearbeitung der Übungsblätter / Vorbereitung Minisemiar
ca. 40 Std. Prüfungsvorbereitung