Kompetitives Programmieren

Im Verlauf des Semesters werden Algorithmen und Datenstrukturen vorgestellt, die aufgrund ihrer Effizienz und vergleichsweise kurzen Implementierung Anwendung in Programmierwettbewerben finden.

Der Schwerpunkt der Veranstaltung liegt in der praktischen Umsetzung der kennengelernten Algorithmen, um mit ihnen gestellte Programmieraufgaben unter den gegebenen Bedingungen (Zeit- und Speicherbeschränkungen) lösen zu können. Dabei werden die aus anderen Vorlesungen (z.B. Einführung in die Informatik, Algorithmen und Datenstrukturen, etc.) bekannten Algorithmen vertieft, ggf. abgewandelt, kombiniert und (auch in untypischen Situationen) zur Anwendung gebracht. Am Ende der Veranstaltung sollen die Studierenden eine breite Erfahrung in der praktischen Anwendung von Algorithmen und deren Design für zuvor unbekannte Probleme haben.

Die Herausforderung beim Lösen der Probleme liegt oft nicht in der Implementierung, sondern vielmehr darin, einen korrekten und ausreichend schnellen Algorithmus zu finden.

 U.A. folgende Themen werden behandelt:

• Datenstrukturen und einfache Algorithmen (z.B. Binäre/Ternäre Suche, schnelles Potenzieren)
• Effiziente Baumstrukturen (Fenwick-Trees, Segment-Trees, Quad-Trees)
• Greedy-Algorithmen
• Einfache Graphen-Algorithmen (Kürzeste Wege, Minimale Spannbäume, Topologische Sortierung, Starke Zusammenhangskomponenten, Artikulationsknoten/Brücken, 2-SAT)
• Netzwerkflüsse und Anwendungen (Edmonds-Karp & Push-Relable, Min-Cost/Max-Flow, Bipartites Matching, Modellierung von Problemen als Flüsse)
• Dynamische Programmierung (grundlegende Prinzipien, klassische Verfahren, nicht-klassische Beispiele, komplexere Dynamische Programmierung in mehreren Dimensionen)
• Exponentielle Algorithmen für NP-vollständige Probleme (TSP, Longest Path)
• Mathematische Problemstellungen (Zahlentheorie: Modulo-Arithmetik, Primzahlen, Chinesischer Restsatz; Kombinatorik: Grundkonzepte, Catalanzahlen)
• Geometrie (2D- und 3D-Geometrie: CCW-Test, Punkte, Liniensegmente und Polygone und deren Schnitte, konvexe Hüllen; Geometrie ohne Gleitkommazahlen; Geometrie auf Kugeln)
• String-Verarbeitung (Suffix Arrays, Aho-Corasick)
• Kombination mehrerer Algorithmen
   

• Gute praktische Programmierkenntnisse in C++, Java, Python oder Haskell
• Elementare Algorithmik, wie z.B. aus Vorlesung Algorithmen und Datenstrukturen bekannt

Die Modulnote berechnet sich aus den während des Semesters erbrachten Leistungen (d.h. wöchtenliche Aufgaben, die direkt bewertet werden). Eine gesonderte Prüfung am Ende des Semesters findet nicht statt.
Details werden in der ersten Vorlesung bekanntgegeben.