Training für Programmierwettbewerbe (Sommersemester 2018)

Ankündigungen

  • Das erste Treffen findet am 10.04.2018, 10:00 in Raum 32-411-PC statt.
  • Es stehen 30 Plätze zur Verfügung. Anmeldung über das KIS

Ort und Zeit

  • Dienstags, 10:00 - 11:30 in Raum 32-411-PC

Dozent

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.

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 einzeln und im Team

Materialien

Termin Themen Handout Slides
10.04. Introduction, warm-up exercises for parsing input intro.pdf 01_slides.pdf
17.04. Number Theory: gcd, lcd, prime numbers, Chinese Remainder Theorem numbers.pdf
08.05. Graph algorithms I graphs.pdf
15.05. Graph algorithms II
22.05. Problem solving paradigms (simulation, brute force, divide and conquer) paradigms.pdf
29.05. Dynamic programming I dp.pdf
19.06. Geometry geometry.pdf
26.06. String algorithms strings.pdf
03.07. Bit masks bitmask.pdf

Literatur

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