Hasso-Plattner-Institut
Prof. Dr. Tobias Friedrich
 

Algorithmix

MSc Lecture - Winter 2015/16

Beschreibung

In dieser Vorlesungen geht es um die Grundlagen des algorithmischen Denkens, insbesondere Algorithmendesign und -analyse. Wir werden uns dabei verschiedene algorithmische Fragestellungen ansehen, wie zum Beispiel das Finden kürzester Wege durch eine Stadt oder das Berechnen von Ähnlichkeitswerten für verschiedene Spezies anhand von DNA-Sequenzen. Es geht dabei immer um das Entwickeln effizienter Algorithmen.

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

Auf einer abstrakten Ebene sind die Ziele 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ätslisten...).

Dabei werden wir klassische Probleme und ihre Lösungen kennenlernen; insbesondere befassen wir uns mit Problemen auf den folgenden Strukturen:

  • Arrays (Sortieren, Suche...);
  • Graphen (DFS/BFS, MST, Dijkstra, Eulerpfad...);
  • Sequenzen (Edit-Distance, LCS...);
  • Punktwolken (Sweeplinealgorithmen...).

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. Es sind keine speziellen Kenntnisse im Bereich der Algorithmik vorausgesetzt.

Literatur

Der absolute Klassiker unter der Algorithmenliteratur: 

  • Cormen, Leiserson, Rivest und Stein, Algorithmen - Eine Einführung.

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. Dabei werden Elemente der traditionellen Lehrformen "Vorlesung", "Übung" sowie "Sprechstunde" vermischt. Daher gibt es bei den beiden Terminen auch keine Unterscheidung zwischen Vorlesung und Übung.

Da Lehrelemente mit einseitigem Informationsfluss keine Treffen von Studierenden mit dem Dozenten benötigen, werden alle solche Elemente in Heimarbeit erledigt (vom Dozenten vorbereitet und den Studierenden konsumiert).

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 (plus Bonuspunkte aus den Übungen).

Termine

Wöchentlich dienstags und donnerstags um 11:00 im Raum A-1.2. Beginn in der ersten Vorlesungswoche. Die Klausur findet am 9.2.2016 ab 14:00 in Hörsaal 1 statt.