To path indicator To navigation To quick access To footer with other services
To content
Algorithm Engineering
Fakultät für Informatik
Students in summer on north campus, red gears in background. © Roland Baege​/​TU Dortmund

Courses given by Algorithm Engineering

Overview

Unsere Arbeitsgruppe bietet üblicherweise die folgenden Kurse an:

Bachelor:

  • Datenstrukturen, Algorithmen und Programmierung 2 (DAP 2)*
  • Effiziente Algorithmen (EA)*
  • Fachprojekt: Algorithmen für Programmierwettbewerbe
  • Proseminare zu verschiedenen algorithmischen Themen

Master:

  • Algorithmen und Datenstrukturen (AuD)*
  • Algorithmische Geometrie
  • Seminar der Arbeitsgruppe Algorithm Engineering
  • Algorithm Engineering**
  • Ausgewählte Kapitel der Algorithmik**

* Im Wechsel mit der Arbeitsgruppe Effiziente Algorithmen und Komplexitätstheorie
** nicht regelmäßig angeboten

Winter 2023/2024

Inhalte:

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.

Algorithm Engineering vereint theoretische und experimentelle Ansätze zur Algorithmenentwicklung: Entwurf, Analyse, Implementierung und experimentelle Bewertung von Algorithmen stehen im Algorithm Engineering gleichberechtigt nebeneinander. Dementsprechend setzen sich die dem Seminar zugrundeliegenden Forschungsarbeiten theoretisch und/oder experimentell mit Algorithmen auseinander.

Voraussetzungen:

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

Inhalte:

  • komplexe Datenstrukturen
  • Lineare und Ganzzahlige Optimierung
  • Approximationsalgorithmen
  • Parametrisierte Algorithmen
  • Geometrische Algorithmen (Ausblick)

Inhalte:

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.

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.

Zeitplan: Mittwochs 13-16Uhr
Zu Beginn des Semesters wird in diesem Zeitraum Vorbesprechungen und der Präsentationskurs stattfinden. Nach den Weihnachtsferien werden in diesem Zeitraum die Präsentationen stattfinden.

Inhalte:

Das Packungsproblem (packing problem) ist ein geometrisches Optimierungsproblem, in dem es darum geht von einer gegebenen Menge von (zwei-dimensionalen) geometrischen Objekten möglichst viele in einem gegebenen (zwei-dimensionalen) Container zu plazieren. In diesem Proseminar befassen wir uns mit effizienten Algorithmen um polygonale Objekte zu packen.

Der Fokus des Proseminars wird auf praktischen Algorithmen liegen. Für eher mathematisch-interessierte Studierende gibt es aber auch theoretische Themen zur Komplexität des Packungsproblem.

Voraussetzungen:

Kenntnisse über Algorithmen für Optimierungsprobleme (z.B. Bin-Packing, ILPs), wie sie in der Vorlesung "Effiziente Algorithmen" behandelt werden, sind wünschenswert, aber nicht notwendig.

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.

Geplanter Veranstaltungszeitraum: Mittwochs 9-12Uhr
Zu Beginn des Semesters wird in diesem Zeitraum Vorbesprechungen und der Präsentationskurs stattfinden. Nach den Weihnachtsferien werden in diesem Zeitraum die Präsentationen stattfinden.

  • Veranstalter: Mart Hagedoorn
  • Modul: Fachprojekt - Bachelor Informatik/Angewandte Informatik
  • Veranstaltungsart: 4SWS Fachprojekt
  • Moodle: tba

Beschreibung

Beim Competitive Programming 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 Semesters wird am das Winter Contest 2024 (Link zum WC 2023) teilgenommen.

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 am internen Programming Challenge

Materialien

Sommer 2023

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.

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

Weitere Informationen zum Kurs finden Sie im Moodle und LSF.

Prüfungen

  • 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).

Materialien

  • Alle Materialien sind im Moodle-Raum zu finden

Thematische Zusammenfassung

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.

Die Themen lauten u.a.:

  • 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

Course page.

Competitive Programming is about developing algorithmic solutions for concrete problems and implementing them in the shortest possible time. In this course, students deepen their understanding of basic efficient algorithms on the one hand, and practice applying the algorithms and programming under time pressure on the other. The Association for Computing Machinery (ACM) has been organizing the International Collegiate Programming Contest (ICPC) annually since 1970, which we will follow.

In our event, important algorithms and data structures for solving problems from previous years of the ICPC will be presented in talks and solution approaches will be discussed together. In addition to the lectures, tasks will be solved and programmed in a simulated competitive situation in teams of 3. At the end of the semester there is the possibility to participate in the German Winter Contest.

Winter 2022/2023

Course page.

Competitive Programming is about developing algorithmic solutions for concrete problems and implementing them in the shortest possible time. In this course, students deepen their understanding of basic efficient algorithms on the one hand, and practice applying the algorithms and programming under time pressure on the other. The Association for Computing Machinery (ACM) has been organizing the International Collegiate Programming Contest (ICPC) annually since 1970, which we will follow.

In our event, important algorithms and data structures for solving problems from previous years of the ICPC will be presented in talks and solution approaches will be discussed together. In addition to the lectures, tasks will be solved and programmed in a simulated competitive situation in teams of 3. At the end of the semester there is the possibility to participate in the German Winter Contest.

Course page.

An assignment problem seeks an assignment from some set to another that satisfies certain properties. In most assignment problems, so-called agents give preferences about who they want to be assigned to. According to these specifications, the assignment takes place under various optimality criteria, e.g., stability, envy-free, or Pareto optimality (fair matchings). An assignment problem is one-sided or multi-sided depending on how many groups give preferences over the others. The hospital-residents problem is two-sided because both physicians give preferences over hospitals and hospitals give preferences over physicians. In a one-sided assignment problem, a set of agents gives preferences over a set of divisible or indivisible and homogeneous or heterogeneous goods (fair division).

Example: Cut & Choose

  •     Player A divides the bun.
  •     Player B chooses one piece.
  •     Player A gets the other piece.

This algorithm is fair under the criteria of envy-free and proportionality, since both players have equal influence on the outcome.

Course page.

In this seminar we will deal with current research topics of the Algorithm Engineering working group based on selected recent publications in the field of algorithms. The group conducts research on a wide range of algorithmic topics, in particular Algorithm Engineering, Geometric Algorithms and Data Structures, Geometric Networks, Algorithms for Geoinformation Systems, and Algorithms for Motion Planning.

Algorithm Engineering combines theoretical and experimental approaches to algorithm development: design, analysis, implementation, and experimental evaluation of algorithms are equally important in Algorithm Engineering. Accordingly, the research papers on which the seminar is based deal with algorithms theoretically and/or experimentally.

To top of page