Algorithm Engineering

Typ: Vorlesung (V)
Semester: SS 2020
Ort:
Geb 50.34, Raum 236
Zeit:
Dienstag 15:45 - 17:15
Dozent: Prof. Dr. Peter Sanders
Dominik Schreiber
SWS: 2/1
LVNr.: 2400051

Links

Bitte wenden Sie sich für einen Termin per E-Mail an das Sekretariat von Prof. Sanders, blancani@kit.edu, und nennen Sie Ihren vollständigen Namen, Ihre Matrikelnummer sowie die Version der Prüfungsordnung, nach der Sie studieren.

Vor der Prüfung melden Sie sich bitte am Studierendenportal an; falls die Veranstaltung zweimal vorhanden ist, wählen Sie bitte die Nummer 13321.

Laut Informationen des KIT-Präsidiums gilt folgendes:

Bitte lesen Sie die beiliegende Erklärung (Erklärung über den fehlenden Verdacht einer Infektion mit dem Coronavirus) und unterschreiben diese am oder kurz vor Prüfungstermin, um Ihren aktuellen Gesundheitszustand zum Prüfungszeitraum zu bestätigen. Bringen Sie die Erklärung zur Präsenzprüfung mit. Blanko-Formulare sind auch bei den Prüferinnen bzw. Prüfern vorrätig.

Beachten Sie bitte auch folgendes (siehe auch hier):

Im Wartebereich vor Einlass in den Prüfungsraum oder während der Prüfung treten bei mir Symptome einer Covid-19-Erkrankung auf. Wie soll ich mich verhalten?

Weisen Studierende im Wartebereich vor Einlass in den Prüfungsraum oder während der Prüfung Symptome einer Covid-19-Erkrankung auf, haben die Prüferinnen bzw. Prüfer diese Personen unverzüglich von der Teilnahme an der betreffenden Prüfung auszuschließen. Der Sachverhalt ist von der Prüferin/dem Prüfer bzw. der aufsichtführenden Person zu dokumentieren und dem zuständigen Prüfungsausschuss zur Kenntnis zu geben. Den ausgeschlossenen Personen wird empfohlen, sich bei Fragen zu dem weiteren Ablauf (z.B. Wiederholung der Prüfung, Wertung der Prüfung) mit dem zuständigen Prüfungsausschuss in Verbindung zu setzen.

Der Ausschluss von der Teilnahme an der Prüfung wird nicht als unentschuldigtes Versäumnis oder als Rücktritt ohne Geltendmachung triftiger Gründe gewertet. Vielmehr gilt der Prüfungsversuch - selbst wenn er bereits begonnen haben sollte – als nicht unternommen. Betroffenen Studierenden verbleibt weiterhin die ihnen regulär vor Beginn der Prüfung zustehende Anzahl von Prüfungsversuchen.

Können betroffene Personen durch eine ärztliche Bescheinigung nachweisen, dass sie an einer chronischen Erkrankung oder Allergie leiden, die zu coronaspezifischen Symptomen führt, ist das KIT bestrebt, ihnen eine Teilnehme an der Prüfung zu gestatten, dies möglichst in einem gesonderten Raum oder unter Tragens einer Mund-Nasen-Bedeckung. Um hier die geeigneten organisatorischen Maßnahmen ergreifen zu können, werden die betroffenen Prüfungskandidatinnen und -kandidaten gebeten, sich frühzeitig mit der Prüferin bzw. dem Prüfer in Verbindung setzen.

Weitere Informationen finden Sie hier.

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.