Training für Programmierwettbewerbe (Sommersemester 2017)

Ankündigungen

  • Anmeldung zum GCPC am 01.07.2017 ist nun freigeschaltet: Registrierung
  • Das erste Treffen findet am 18.04.2017, 10:00 in Raum 32-411-PC statt.
  • Es stehen 30 Plätze zur Verfügung. Anmeldung über das KIS
  • Bei Interesse zur Anrechnung als Seminar, bitte zusätzlich eine Email an Annette Bieniusa

Inhalt

Programmierwettbewerbe wie der International Collegiate Programming Contest (ICPC) der Association for Computing Machinery (ACM) bieten die Möglichkeit, die eigenen Programmier- und Teamfähigkeiten auszutesten. Seit 1970 wird der ACM-ICPC von der ACM, der ältesten und größten weltweiten Vereinigung für Informatik, ausgetragen; in 2016 nahmen über 46.000 Studierende aus mehr als 100 Ländern an dem Wettbewerb teil. In verschiedenen regionalen Ausscheidungsverfahren können sich Teams für die Teilnahme an den World Finals qualifizieren

Da Studierende in Teams an dem Wettbewerb teilnehmen, ist neben der fachlichen Qualifikation die Teamstrategie oft entscheidend für den Erfolg der Gruppe.

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

Die Veranstaltung bereitet auf die Teilnahme am Programmierwettbewerb am German Collegiate Programming Contest (GCPC), einem Auswahlwettbewerb für den ICPC) vor, der voraussichtlich im Juni/Juli durchgeführt wird. Der Regionalwettbewerb für Nord-West-Europa wird in der Zeit von September bis Dezember 2017 stattfinden.

Der Abgabeserver TUKLJudge ist unter der Adresse https://softech.cs.uni-kl.de/domjudge/ erreichbar.

Themen

String-Algorithmen, Dynamische Programmierung, Graphalgorithmen, Zahlentheorie/Kombinatorik, Geometrie, Spieltheorie

Voraussetzungen

Programmierkenntnisse in Java oder C/C++, wie sie in SE1 vermittelt werden; Spaß am Programmieren und Knobeln

Prüfungsleistung

Bearbeitung von Übungen im Team

Hinweis Die Veranstaltung kann alternativ auch als Bachelor-Seminar eingebracht werden, wenn zusätzlich zu der Bearbeitung der Übungen eine Präsentation und Ausarbeitung zu einem der Themen erfolgt. Bei Interesse melden Sie sich bitte zusätzlich per Email an Annette Bieniusa

Zeitplan

Termin Themen Handout
18.04. Introduction, warm-up exercises for parsing input intro.pdf
25.04. Graph algorithms I : graphs representations, DF/BF search, reachability graph1.pdf
02.05. Graph algorithms II : shortest paths, minimum spanning trees graph2.pdf
09.05. Graph algorithms III: strongly connected components, topological order graph3.pdf
16.05. Number Theory: gcd, lcd, prime numbers, Chinese Remainder Theorem numbers.pdf
23.05. Geometry geometry.pdf
30.05. Dynamic programming I dp.pdf, Notizen
06.06. Dynamic programming II dp2.pdf, Notizen
13.06. String algorithms strings.pdf
20.06. Problem solving paradigms (simulation, brute force, divide and conquer) paradigms.pdf
27.06. Bit masks bitmask.pdf
04.07. Seminar talk: Gale-Shapely Stable marriage
11.07. Seminar talk: Union-find
18.07. Seminar talk: Suffix Trees

Literatur

Skiena/Revilla, Programming Challenges. The Programming Contest Training Manual. Springer 2003. Cormen/Leiserson/Rivest/Stein, Introduction to Algorithms. MIT Press 2001.

Personen

Das Projekt wird von Annette Bieniusa und Sebastian Wild betreut.

Material für Seminarausarbeitung

Latexvorlage