Pro­se­mi­nar Ef­fi­zi­en­te Al­go­rith­men

Dozent: Prof. Dr. Christian Scheideler

Zeit und Ort:TBA

Inhalt

Ziel des Proseminars ist es, zu lernen, wie die in der Vorlesung "Datenstrukturen und Algorithmen" vorgestellten Methoden verwendet und erweitert werden können, um algorithmische Probleme, die im renommierten International Collegiate Programming Contest (ICPC) erschienen sind, lösen zu können. Dazu wird es wöchentliche Treffen geben, in denen jeweils eine bestimmte Klasse von Problemen behandelt wird. Weiterhin werden einige dieser Probleme pro Treffen als Hausaufgabe aufgegeben, die von studentischen Teams bestehend aus bis zu 3 Leuten gelöst werden müssen. Darüber hinaus muss jeder Teilnehmer am Ende des Kurses zwei Probleme aus den ICPC Wettbewerben auswählen und die Lösungen in einem Bericht und einer Abschlusspräsentation vorstellen. 

Schein

Einen Schein bekommt, wer regelmäßig am Proseminar teilnimmt, mindestens 50% der Probleme korrekt gelöst hat, und am Ende die Ausarbeitung und Präsentation von zwei ausgewählten ICPC Problemen besteht. Die Endnote ergibt sich zu 60% aus der Ausarbeitung und zu 40% aus der Präsentation. 

Übersicht über die Themen

  • Einführung
  • Datenstrukturen
  • Zeichenketten
  • Sortieren, selektieren und suchen
  • Arithmetik und Kombinatorik
  • Zahlentheorie
  • Graphdurchlauf
  • Graphalgorithmen
  • Divide & Conquer und Dynamische Programmierung
  • Backtracking und Branch-and-Bound

ICPC Wettbewerbe

Einige Beispiele sind:

Alle Wettbewerbe können auf der Webseite https://icpc.global/worldfinals/past-problems gefunden werden. Klickt man auf einen Wettbewerb, wird auch mitgeteilt, wie schwer die Probleme sind, so dass das helfen sollte, einen geeigneten Wettbewerb auszuwählen.

Übungsaufgaben

  • Werden in PANDA bekannt gegeben.

Die Probleme können unter http://www.cs.uleth.ca/%7Echeng/contest/hints.html nachgeschlagen und über http://uva.onlinejudge.org/index.php eingereicht werden. Die Programme müssen zusammen mit der Bestätigung des Servers, dass sie akzeptiert worden sind, und den Namen der Gruppenmitglieder bis spätestens zum angegebenen Abgabetag per Email an den Dozenten geschickt werden (der Zeitstempel der Email zählt).

Hilfsmittel