Kurse der Arbeitsgruppe Algorithm Engineering

Beschreibung

In der Vorlesung "Datenstrukturen, Algorithmen und Programmierung 2" (DAP2) beschäftigen wir uns mit Techniken für Entwurf und Analyse von Algorithmen und Datenstrukturen.

In dieser Veranstaltung lernen Sie:

• Grundlegende Algorithmen und Datenstrukturen beschreiben, an kleinen Beispielen anwenden und an neue Problemstellungen anpassen
• Eigenschaften wie die Laufzeit und die Korrektheit von Algorithmen ermitteln, vergleichen und mathematisch beweisen
• neue Algorithmen und Datenstrukturen mit Hilfe grundlegender Entwurfsmethoden entwickeln

Beispiele grundlegender Algorithmen:

• Algorithmen zum Sortieren von Zahlen wie MergeSort, InsertionSort, Quicksort, Heapsort, CountingSort und RadixSort und Algorithmen für das Auswahlproblem
• Algorithmen für grundlegende Optimierungsprobleme wie das Rucksackproblem
• Graphalgorithmen wie Breitensuche, Tiefensuche, Topologisches Sortieren, Minimale Spannbäume und kürzeste Pfade

Beispiele grundlegender Datenstrukturen:

• Heaps
• Hashtabellen
• Balancierte binäre Suchbäume wie Rot-Schwarzbäume
• Graphrepräsentationen wie Adjazenzlisten und Adjazenzmatrizen

Für viele algorithmische Probleme ist es notwendig, diese grundlegenden Algorithmen und Datenstrukturen anzupassen oder neue Algorithmen und Datenstrukturen zu entwurfen. Wir lernen in der Vorlesung Entwurfstechniken wie Teile-und-Herrsche, Inkrementelle Algorithmen, gierige Algorithmen und Dynamische Programmierung kennen.

Zur Analyse der Laufzeit von Algorithmen lernen wir die O-Notation kennen. Um die Laufzeit von rekursiven Algorithmen zu analysieren, muss die Rekurrenz für die Laufzeit bestimmt werden und mit Techniken wie Rekursionsbäumen oder dem Master-Theorem gelöst werden. Auch um die Korrektheit von Algorithmus zu zeigen lernen wir verschiedene Techniken wie zum Beispiel Schleifeninvarianten kennen.

Beschreibung

Die in DAP 2 eingeführten Basistechniken werden vertieft und auf komplexere Probleme angewendet, hinzu kommen ausgewählte Probleme mit großen Anwendungsbereichen, weitergehende Aspekte wie Approximation und weitergehende Entwurfsmethoden.

Topics include:

• Hashing Verfahren, String Matching
• Graphenalgorithmen, wie z.B. starker Zusammenhang in Graphen, Maximale Matchings, Netzwerkflussprobleme, Schnittprobleme (Min Cut und Max Cut), Traveling Salesman Problem, Vertex Cover, MaxSAT
• Fortgeschrittene Datenstrukturen, wie B-Bäume, Datenstrukturen für Disjunkte Mengen, Augmentierung von Datenstrukturen
• Analysetechniken, wie z.B. Amortisierte Analyse von Algorithmen, Analyse randomisierter Algorithmen
• Optimierungstechniken, wie z.B. Lineare Programmierung, Approximationsgüte und -schemata

Literatur

• Cormen, Leiserson, Rivest, Stein: Introduction to Algorithms (Das Buch ist auch in der Universitätsbibliothek als E-Book in englischer und deutscher Sprache "Algorithmen - Eine Einführung" verfügbar.)
• weitere Literaturhinweise und Skripte werden im Moodle bereitgestellt

Prüfungsleistung

• Studienleistung: erfolgreiche Teilnahme (50% der Punkte) an den wöchentlichen Moodle Quizzen
• Für die Bachelor-Studierenden der Informatik und der Angewandten Informatik: Klausur, 90 Minuten, 2 Termine
• Studierende anderer Fachrichtungen haben entweder mündliche Prüfungen oder auch Klausur. Die genauen Konditionen werden in der Vorlesung bekannt gegeben (s. Folien). Im Falle einer Klausur findet diese zeitgleich mit den obigen Klausuren statt. Bitte beachten Sie die Anmeldefristen für die Prüfungen beim Prüfungsamt, die für Klausuren sehr früh sind (i.d.R. 2 Wochen vorher).

Beschreibung

Bei Programmierwettbewerben geht es darum, für konkrete Probleme algorithmische Lösungen zu entwickeln und in möglichst kurzer Zeit zu implementieren. In dieser Veranstaltung wird einerseits das Verständnis für grundlegende effiziente Algorithmen vertieft, andererseits das Anwenden der Algorithmen und Programmieren unter Zeitdruck geübt. Die Association for Computing Machinery (ACM) richtet seit 1970 jährlich den International Collegiate Programming Contest (ICPC) aus, an welchem wir uns orientieren werden.

In unserer Veranstaltung werden wichtige Algorithmen und Datenstrukturen zur Lösung von Problemen aus früheren Jahren des ICPCs in Vorträgen vorgestellt und Lösungsansätze gemeinsam diskutiert. Neben den Vorträgen werden Aufgaben in einer simulierten Wettbewerbssituation in 3er-Teams gelöst und programmiert.

Am Ende des Semester nehmen Sie am Winter Contest oder GCPC teil.

Zeitplan und Ablauf

Jeden Mittwoch von 12 bis 16 Uhr findet das Fachprojekt statt. In den ersten beiden Stunden werden spezifische Techniken zur Lösung von Wettbewerbsproblemen behandelt. Die letzten beiden Stunden sind der Bearbeitung von Übungsaufträgen gewidmet.

Programmiersprache: C, C++, Java oder Python (Hauptsache Sie finden zwei weitere Teilnehmer für ihre präferierte Sprache)

Kurssprache ist Deutsch, die Problembeschreibungen/Aufgabenstellungen werden jedoch auf Englisch sein!

Voraussetzungen

• Programmierkenntnisse (Praktika DAP 1 und 2)
• Datenstrukturen, Algorithmen und Programmierung 2
• Wir setzen Grundkennt niss e in den folgenden Bereichen voraus:
  • Algorithmenentwurfsmethoden: Greedy, Divide and Conquer, dynamisches Programmieren, Backtracking und Rekursion
  • Grundlegende Datenstrukturen: Arrays, Listen, Stacks, Queues, binäre Suchbäume, Heaps, Adjazenzlisten und -matrizen
  • Standardthemen der Algorithmik: O-Notation, Sortieren, Suchen, Hashing, einfache Graphenalgorithmen (z.B. Baumtraversierung, Breiten- und Tiefensuche)
• Grundkenntnisse über Matching- und Flussalgorithmen (EA) sind hilfreich, aber nicht notwendig

Prüfungsleistung

Alle Modulabschlussleistungen finden als 3er-Team statt

• 30 min Vortrag über eine Datenstruktur oder Programmierparadigma sowie das Anleiten des Kurses zur Lösung von dazugehörigen Aufgabentypen
• 3 von 5 der wöchentlich gestellten Probleme pro Aufgabentyp gelöst
• Erfolgreiche Teilnahme an der internen Programming Challenge

Materialien

• hackerearth.com (practice problems online)
• ICPC - problem archives
• PROGRAMMING CHALLENGES - The Programming Contest Training Manual (book)

Beschreibung

Beim Competitive Programming geht es darum, für konkrete Probleme algorithmische Lösungen zu entwickeln und in möglichst kurzer Zeit zu implementieren. Die Association for Computing Machinery (ACM) richtet seit 1970 jährlich den International Collegiate Programming Contest (ICPC) aus, an welchem wir uns orientieren werden.

In unserer Veranstaltung werden fortgeschrittene Algorithmen und Datenstrukturen zur Lösung von Problemen aus früheren Jahren des ICPCs  vorgestellt und Lösungsansätze diskutiert.

Voraussetzungen

Der Kurs knüpft an das Fachprojekt "Algorithmen für Programmierwettbewerbe" an. Vorkenntnisse aus diesem Kurs sind erwünscht, aber nicht notwendig. Sie können das Fachprojekt auch gleichzeitig belegen (Mittwoch vormittags: Proseminar, Mittwoch nachmittags: Fachprojekt) 

Wir setzen Grundkenntnisse in Algorithmenentwurfsmethoden (u.a. dynamisches Programmieren, Backtracking),  Datenstrukturen (u.a. Queues, binäre Suchbäume, Heaps, Graphen) und Standardthemen der Algorithmik (O-Notation, Sortieren, Suchen, Hashing) voraus.

Beschreibung

Die Vorlesung "Algorithmen und Datenstrukturen" mit der begleitenden Übung gibt einerseits die Grundlagen für die meisten weiterführenden Spezialvorlesungen im Bereich algorithmische und formale Grundlagen, zum anderen behandelt sie weiterführende und komplexere Algorithmen und Datenstrukturen.

Schwerpunkte der Vorlesung sind Approximationsalgorithmen und Lineare Optimierung. Neben diesen Themen werden verschiedene fortgeschrittene, algorithmische Themen behandelt wie parametrisierte Algorithmen und fortgeschrittene Datenstrukturen.

Es gibt viele algorithmische Probleme, für die wir nicht erwarten können effiziente Algorithmen zu finden. Um trotzdem Lösungen für solche Probleme zu finden, sind Approximationsalgorithmen von zentraler Bedeutung. Approximationsalgorithmen berechnen eine Lösung, die zwar nicht notwendigerweise optimal ist, für die wir aber eine Gütegarantie geben können. Zum Beispiel berechnet Christofides Algorithmus für das Rundreiseproblem (TSP) eine Tour die im Worst-Case maximal 1,5 mal so lang ist wie die optimale Tour. Wir lernen verschiedene Approximationsalgorithmen und Techniken für den Entwurf von Approximationsalgorithmen kennen.

Mit lineare Optimierung zusammen mit ganzzahliger Optimierung lassen sich eine Vielzahl von Optimierungsfragestellungen lösen. Wir lernen die Grundlagen der linearen Optimierung kennen, die für die Informatik essentiell sind. Lineare Optimierung spielt insbesondere Approximationsalgorithmen eine wichtige Rolle und wir werden in der Vorlesung diese Anwendung der linearen Optimierung genauer betrachten.

Beschreibung

Geometrische Algorithmen umfasssen den Entwurf und die Analyse von Algorithmen und Datenstrukturen für geometrische Probleme. In der Vorlesung werden zunächst einige grundlegende Probleme betrachtet: Das Berechnen der konvexen Hülle einer Punktmenge, der Schnittpunkte einer Menge von Strecken, oder einer Triangulierung eines einfachen Polygons. Anschließend sehen wir Algorithmen zum Berechnen bekannter geometrische Strukturen, wie Voronoi-Diagramme, Delaunay-Triangulierungen und Arrangements. Ebenfalls betrachten wir Datenstrukturen für effiziente Anfragen auf geometrischen Daten, wie Range-trees, kd-Bäume und Quadtrees. Dabei kommen vor allem drei Arten von Algorithmen zum Einsatz: inkrementell, teile-und-herrsche, und sweep. Manche von diesen treten als randomisierte Algorithmen auf.

Voraussetzungen

Als Vorkenntnisse wird die Vorlesung “Algorithmen und Datenstrukturen” oder vergleichbare Kenntnisse erwartet.

Prüfung

• Studienleistung: aktive Teilnahme (inkl. Präsentation eigener Lösungen)
• mündliche Prüfung

Beschreibung

Im Seminar beschäftigen wir uns mit aktuellen Forschungsthemen der Arbeitsgruppe Algorithm Engineering, die anhand ausgewählter aktueller Veröffentlichungen im Bereich der Algorithmik behandelt werden. Die Arbeitsgruppe forscht zu einem breiten Spektrum algorithmischer Themen, insbesondere Algorithm Engineering, Geometrische Algorithmen und Datenstrukturen, Geometrische Netzwerke, Algorithmen für Geoinformationssysteme und Algorithmen zur Bewegungsplanung.

Voraussetzungen

Als Vorkenntnisse wird die Vorlesung “Algorithmen und Datenstrukturen” oder “Geometrische Algorithmen” oder vergleichbare Kenntnisse erwartet.