Algorithmix (Wintersemester 2018/2019)

Dozent: Prof. Dr. Tobias Friedrich (Algorithm Engineering) , Dr. Pascal Lenzner (Algorithm Engineering)
Website zum Kurs: https://hpi.de//friedrich/teaching/ws18/algorithmix.html

Allgemeine Information

• Semesterwochenstunden: 4
• ECTS: 6
• Benotet: Ja
• Einschreibefrist: 26.10.2018
• Lehrform: Vorlesung / Übung
• Belegungsart: Wahlpflichtmodul

Studiengänge, Modulgruppen & Module

Beschreibung

"I would rather have today's algorithms on yesterday's computers than vice versa." -- Philippe Toint

Effiziente Algorithmen sind das mächtigste und vielfältigste Werkzeug der Informatik. Es gibt viele Möglichkeiten, um ein gegebenes Problem zu lösen und die Suche nach einer geeigneten Lösungsidee erfordert Kreativität und eine strukturierte Herangehensweise. Die Mühe lohnt sich, denn eine gute algorithmische Idee und deren effiziente Implementierung ist oftmals viel mehr Wert als pure Rechenkraft.

In dieser Vorlesungen geht es um die Grundlagen des algorithmischen Denkens, insbesondere Algorithmendesign und -analyse. Wir werden uns dabei verschiedene algorithmische Fragestellungen ansehen und effiziente Algorithmen zu deren Lösung entwerfen und analysieren.

Dieser Kurs gibt dabei einen Überblick über das Thema "Algorithm Engineering" und bereitet auch optimal auf vertiefende Vorlesungen in diesem Bereich vor.

Auf einer abstrakten Ebene ist das Ziel des Kurses, Fähigkeiten in den folgenden Bereichen zu entwickeln:

• Algorithmenanalyse;
• Algorithmendesign;
• Formalisierung von Problemstellungen.

Konkret beschäftigen wir uns mit den folgenden Themen:

• Techniken des Algorithmendesign (Greedy, Brute Force, Divide and Conquer, Dynamic Programming,...);
• Techniken der Algorithmenanalyse (Laufzeitbestimmung, amortisierte Analyse, Korrektheitsbeweise, Schleifeninvarianten,...);
• Datenstrukturen (für Graphen, Suchbäume, Prioritätswarteschlagen, Mengenverwaltung,...).
• Analyse der Komplexität von Problemen (NP-Schwere, Polynomialzeitreduktionen,...)
• Umgang mit schweren Problemen (Approximationsalgorithmen, spezielle Instanzklassen,...)

Voraussetzungen

Vorausgesetzt wird ein Interesse am Knobeln und Kniffeln sowie ein grundlegendes Verständnis von mathematischer Notation und Sprache. Hilfreich ist eine Kenntnis von Landau-Notation (O-Notation), welche kurz wiederholt wird. Außerdem wird Kenntnis von grundlegenden Algorithmen und Datenstrukturen (z.B. binäre Suche, Mergesort, Quicksort, Heapsort, Dijkstras Algorithmus, binäre Min-Heaps, binäre Suchbäume) vorausgesetzt.

Literatur

Die Vorlesung wird sich zum Teil nach folgenden Klassikern der Algorithmenliteratur richten:

• Th. Ottmann, P. Widmayer: Algorithmen und Datenstrukturen. 4. Auflage, Spektrum Akademischer Verlag, Heidelberg, 2002
• T. Cormen, C. Leiserson, R. Rivest, C. Stein: Introduction to Algorithms. Second Edition MIT Press, 2002
• J. Kleinberg, E. Tardos: Algorithm Design. Pearson, Addison-Wesley 2006

Lern- und Lehrformen

In diesem Kurs werden wir problemorientiert lernen. Zu einem gegebenen Problem werden dabei Lösungen gesucht und gemeinsam von Studierenden und dem Dozenten entwickelt. Zu allen Themengebieten wird es zusätzlich Übungsserien geben, welche, nach der Bearbeitung durch die Studierenden, dann gemeinsam besprochen werden.

Leistungserfassung

Es werden wöchentliche Hausaufgaben gestellt, deren erfolgreiche Bearbeitung Zulassungsvoraussetzung für die Endklausur ist. 100% der Note ergeben sich aus der Punktzahl bei der Endklausur.

Termine

Wöchentlich dienstags um 11 Uhr in Hörsaal 3 und donnerstags um 11 Uhr in Hörsaal 2. Beginn in der ersten Vorlesungswoche.

Zurück