ACM Programming Contest Praktikum (SS 2006)

Der ACM International Collegiate Programming Contest (ICPC) ist ein jährlich stattfindender weltweiter Programmierwettbewerb, in dem Universitätsteams von je 3 Studenten in einem mehrstündigen Härtetest möglichst viele Programmieraufgaben korrekt lösen müssen. Zunächst werden auf regionaler Ebene die besten Teams ermittelt, und diese treten dann im Weltfinale gegeneinander an. Das Bild oben zeigt das Finale 2004 in Prag.

Das Ziel des Praktikums ist es, schlagkräftige Teams zu formen, die bei zukünftigen ICPC Wettbewerben die TU München erfolgreich repräsentieren können. Aber so wie bei der Olympiade gilt natürlich auch hier: dabei sein ist alles! Es ist einfach ein fantastisches Erlebnis, bei diesen Wettbewerben mitzumachen und Studenten aus aller Welt zu treffen!
Dozent:
Prof. Dr. Christian Scheideler
Ankündigungen:
Voranmeldungen bitte bis zum 3. Februar 2006 an scheideler@in.tum.de.
Das erste Treffen findet am Mittwoch, den 26. April statt.
Bereich:
3 SWS Programmierpraktikum im Grundstudium bzw.
6 SWS Praktikum im Bereich Informatik III (Theoretische Informatik)
Zeit und Ort:
Mittwoch, 16:15 - 17:45, MI 03.11.018
Schein:
Einen Übungsschein erhält, wer die Programmieraufgaben im Praktikum erfolgreich löst.
Prüfungen:
Wöchentliche Programmieraufgaben in Teams zu je 2 bis 3 Personen.
Hörerkreis:
Studierende im Bachelor/Grundstudium der Informatik
Studierende im Hauptstudium der Informatik
Studierende mit Nebenfach Informatik
Voraussetzungen:
Beherrschung der Programmiersprache Java oder C++.
Empfehlenswert für:
Erweiterte Kenntnisse im Bereich Programmierung und effizienter Algorithmen und Datenstrukturen.
Inhalt:
Das Praktikum wird sich mit den folgenden Themen beschäftigen:
- Einführung in den ACM Contest, Ein-/Ausgabe, Datenstrukturen
- Kombinatorische Probleme
- Dynamische Programmierung
- Stringprobleme
- Zahlentheorie (Primzahlen, GGT, ExpMod, Rechnen mit großen Zahlen)
- Graphen: BFS und DFS
- Union-find, minimum spanning tree
- Kürzeste Wege (Dijkstra, Floyd-Warshall)
- Backtracking und Branch-and-bound
- Trickkiste
Folien:
Übungsaufgaben: Bitte einreichen bei http://acm.uva.es/p/ und per email an scheideler@in.tum.de.
- Übung 1: Mindestens 2 Aufgaben aus UVa #10189 (Minesweeper), 10137 (The Trip), 706 (LCD Display) und 10267 (Graphical Editor) bis Mittwoch, 3. Mai
- Übung 2: UVa #10038 (Jolly Jumpers) und UVa #10258 (Contest Scorecard)
- Übung 3: UVa #10010 (Where's Waldorf) und UVa #10150 (Doublets)
- Übung 4: UVa #10037 (Bridge) und UVa #10026 (Shoemaker's Problem)
- Übung 5: UVa #10018 (Reverse and Add) und UVa #701 (The Archeologist's Dilemma)
- Übung 6: UVa #10183 (How Many Fibs?) und UVa #10213 (How Many Pieces of Land?)
- Übung 7: UVa #861 (Little Bishops) und UVa #10181 (15-Puzzle Problem)
- Übung 8: UVa #10099 (The Tourist Guide) und UVa #10029 (Edit Step Ladders)
- Übung 9: UVa #10278 (Fire Station) und UVa #10199 (Tourist Guide)
- Übung 10: UVa #10069 (Distinct Subsequences) und UVa #10261 (Ferry Loading)
- Übung 11: UVa #10182 (Bee Maja) und UVa #10180 (Rope Crisis in Ropeland!)
- Übung 12: UVa #10195 (The Knights of the Round Table) und UVa #10012 (How Big Is It?)
Weiterführende bzw. verwandte Vorlesungen:
Effiziente Algorithmen und Datenstrukturen I und II.
Literatur:
- Steven S. Skiena and Miguel A. Revilla.
  Programming Challenges: The Programming Contest Training Manual.
  Springer-Verlag, New York, 2003.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest and Clifford Stein.
  Introduction to Algorithms, Second Edition.
  The MIT Press, 2001.
Sprechstunde:
siehe hier

Letzte Änderung: Christian Scheideler am 23.01.2006