Proseminar: Geschickt Programmieren für den ICPC-Wettbewerb
Zusammenfassung
Im International Collegiate Programming Contest (ICPC) messen sich jährlich weltweit Studenten in ihren Fähigkeiten, Probleme zu analysieren und schnell in Form eines Programms zu lösen. Teams aus je drei Studenten müssen sich hierzu einen Computer über fünf Stunden teilen, um möglichst viele von 9-11 Aufgaben zu lösen. Mehr Informationen zum Wettbewerb und der ICPC-Gruppe in München gibt es unter http://icpc.in.tum.de.
Die Aufgaben im ICPC sind dabei in der Regel Variationen von grundlegenden Algorithmen aus Bereichen wie Graph- und Netzwerkalgorithmen, Suchen und Sortieren, aber auch Algebra und Geometrie. In diesem Seminar sollen die Studenten die Umsetzung von Algorithmen üben und auf den ICPC vorbereitet werden. Jeder Teilnehmer wird einen Vortrag über ein für den ICPC typisches Themengebiet halten. Der Fokus liegt auf der (möglichst einfachen, aber effizienten) Implementierung, welche idealerweise auch anhand einer Beispielaufgabe erläutert wird. Dabei wird auch auf die geschickte Verwendung einfacher Datenstrukturen und Abschätzungen von Laufzeiten und Speicherbedarf eingegangen. Neben einer kurzen schriftlichen Ausarbeitung des Vortrags (ca. 5 Seiten) wird das Lösen von 11 Aufgaben aus verschiedenen Themengebieten (eine Aufgabe pro Themengebiet) erwartet.
Themenliste
| (1.) | --- | Patternmatching (Knuth-Morris-Pratt, Boyer-Moore, Karp-Rabin, Suffix-Trees/-Tries/-Arrays) | --- | |
| (2.) | --- | Suchen und Sortiern (Quicksort, Mergesort, Bucketsort, Heapsort, Radixsort, lineare vs. binäre Suche, Quickselect) | --- | |
| 3. | 11.05.2010 | Dynamische Programmierung (Top-Down vs. Bottom-Up, Rucksack, Levenshtein Distance, Longest Common Subsequence) | Armin Krupp | Vortrag |
| 4. | 18.05.2010 | Graphalgorithmen I (Graphrepräsentationen, Tiefen-/Breitensuche, starke Zusammenhangskomponenten, Artikulationspunkte, Brücken, Euler-Pfade) | Felix Weissenberger | Vortrag |
| 5. | 01.06.2010 | Graphalgorithmen II (Union/Find, kürzeste Wege, Spannbäume) | Korbinian Breu | Vortrag |
| 6. | 08.06.2010 | Flüsse, Schnitte, bipartite Graphen (Maximum Flow, Maximum Matching) | Vlad Popa | Vortrag (PDF, PPTX) |
| 7. | 15.06.2010 | Kombinatorik und Stochastik (Permutationen, Binomialkoeffizienten, Stirling-Zahlen, Catalan-Zahlen, Einführung in den Wahrscheinlichkeitsbegriff) | Christian Fuchs | Vortrag |
| 8. | 22.06.2010 | Zahlentheorie, Arithmetik und Algebra (Primzahltests, Primfaktorzerlegung, Modulo-Arithmetik, Chinesischer Restesatz, Eulers Phi-Funktion) | Tomas Prerovsky | Vortrag |
| 9. | 28.06.2010 | Geometrie I (Schnitte von Geraden/Ebenen, Orientierung in 2D/3D, Pick's Theoreom, Polygone, kd-Bäume) | Martin Keßler | |
| 10. | 06.07.2010 | Geometrie II (konvexe Hülle, Punkt-in-Polygon, Closest Pair) | Max Halsbeck | |
| (11.) | --- | Münzwechsel- und Schedulingprobleme, Longest Increasing Subsequence (z.B. SWERC 2006, UVA 11269, UVA 11729, UVA 10037, UVA 10026) | --- | |
Programmieraufgaben
Jeder Teilnehmer muss 11 Aufgaben aus unterschiedlichen Themengebieten lösen. Die Aufgaben stammen aus dem Onlinejudge UVA, wo man die Möglichkeit hat, die Lösungen auf ihre Korrektheit zu testen (vorher einloggen!).
Diese Aufgaben sollen natürlich nicht als Beispiele in den Vorträgen benutzt werden.
- Patternmatching
- Suchen und Sortiern
- Dynamische Programmierung
- Graphalgorithmen I
- Graphalgorithmen II
- Flüsse, Schnitte, bipartite Graphen
- Kombinatorik und Stochastik
- Zahlentheorie, Arithmetik und Algebra
- Geometrie I
- Geometrie II
- Münzwechsel- und Schedulingprobleme, Longest Increasing Subsequence
Vorkenntnisse
Die Aufgaben müssen in C, C++ oder Java gelöst werden. Deshalb müssen Teilnehmer mindestens eine der Sprachen beherrschen. Zur Verfügung stehen die C-Math-Library, die Standard Template Library für C++ bzw. die Java-Standard-Bibliothek. Deren Verwendung kann vorteilhaft sein, insbesondere in Hinblick auf erweiterte Datenstrukturen wie Priorityqueues und Hashmaps. Andere Bibliotheken können nicht verwendet werden.
Anmeldung
Falls Ihr Interesse habt, meldet euch bitte kurz bei
Riko Jacob und teilt eure erste und zweite Themenpräferenz mit.
Termine
Bei Interesse an der Teilnahme schickt bitte eine Email an Riko Jacob.
Das Proseminar findet Dienstags von 16:15 Uhr bis 17:45 Uhr int Raum 01.06.011 statt. Die genauen Termine stehen in der Themenliste.
Die Ausarbeitung und die Programmieraufgaben müssen bis zum 13.08.2010 abgegeben werden.
Hinweise
Jeder Teilnehmer wählt ein Thema und bereitet einen Vortag vor. Die Aufgabe besteht darin,
- die Algorithmen zu verstehen und
- die Algorithmen als Vorbereitung selbst zu implementieren.
Im Vortrag soll man
- die Algorithmen verständlich erklären
- auf Probleme bei der Implementierung hinweisen und
- ggf. mit dem Publikum Beispielaufgaben diskutieren.
Als Orientierung können die Vorträge unter
http://www2.informatik.uni-erlangen.de/teaching/SS2009/HalloWelt/index.html dienen. Diese dürfen aber nicht 1-zu-1 kopiert werden. Sowohl bei der Auswahl des dargestellten Inhalts als auch bei der Darstellung soll Eigenleistung erkennbar sein.
Außerdem muss man eine fünfseitige Ausarbeitung schreiben und aus jedem Themengebiet eine Aufgabe lösen.
Ausarbeitung
Alle Ausarbeitungen sollen vorzugsweise mit dem Textsatzsystem LaTeX erstellt werden. Hierzu sind folgende Richtlinien zu beachten:
- Der folgende Rahmen ist zu verwenden (seminararbeit.tex). Dabei dürfen die Seitengröße und der Font nicht verändert werden. Die Datei llncs.cls ist zum übersetzen nötig.
- Ein Beispiel kann in der Datei example.tex gefunden werden (das Bild example.eps wird eingebunden).
- Die Ausarbeitung soll auf die verwendete Literatur verweisen. Diese Literatur ist mit BibTeX zu verwalten und in einer eigenen Datei zu speichern (hier die zum Beispiel gehörende Datei: example.bib).
- Bei Fragen zu LaTeX können die folgenden Links hilfreich sein:
Der Betreuer des Proseminars kann ebenfalls um Hilfestellungen bzw. Literaturangaben gebeten werden.
