ICPC-Proseminar

From Sccswiki
Revision as of 13:42, 6 February 2012 by Gatzhamm (talk | contribs)
Jump to navigation Jump to search

Geschickt Programmieren für den ICPC-Wettbewerb (Proseminar)

Term
Summer 12
Advisor
Bernhard Gatzhammer, M.Sc
Time and Place
in Arbeit
Audience
Informatik (Bachelor), Mathematik (Bachelor), Wirtschaftsinformatik (Bachelor); Modul IN0013 [1]
Semesterwochenstunden / ECTS Credits
4
TUMonline
{{{tumonline}}}



Hintergrund und Zielsetzung

Jedes Jahr veranstaltet die Association for Computing Machinery (ACM) [2] den International Collegiate Programming Contest (ICPC) [3]. In diesem Wettbewerb lösen Dreierteams an einem Computer Programmieraufgaben innerhalb einer vorgegebenen Zeitspanne.

Die meisten Aufgaben basieren auf Abwandlungen von Standardalgorithmen, wie man sie in den Einführungsvorlesungen zur Informatik kennenlernt. Um erfolgreich bei einem solchen Wettbewerb teilzunehmen ist es daher entscheidend, die wichtigsten Algorithmen zu kennen und zu verstehen, so dass man sie schnell an ein neues Problem anpassen kann.

Vor diesem Hintergrund formen sich zwei Ziele des Seminars. Zum einen stellen die Seminarteilnehmer in Einzelvorträgen und schriftlichen Ausarbeitungen verschiedene Standardalgorithmen vor und arbeiten die Grundidee dieser Algorithmen heraus. Zum anderen werden Aufgaben aus dem ICPC-Umfeld gestellt, von denen die Seminarteilnehmer eine bestimmte Anzahl erfolgreich bei der Online-Bewertungsplattform der ACM einreichen müssen.

Damit sollen sowohl die Grundlagen für erfolgreiches Programmieren als auch die Fähigkeiten geschaffen werden, bekannte Lösungen an neue Probleme anzupassen. Damit richtet sich das Seminar nicht nur an Studenten und Studentinnen, die am ICPC teilnehmen wollen sondern bietet für alle die Möglichkeit altbekannte und neue Algorithmen auf echte Probleme anzuwenden.

Die weiteren Ziele des Seminars sind das selbständige Erarbeiten eines Themengebiets, dessen Zusammenfassung und Erläuterung in Form einer Ausarbeitung, sowie das Erstellen und Abhalten einer Präsentation.

Zeitplan

Das Seminar beginnt mit einem Vorbereitungstreffen zum Semesterbeginn. Nach einer kurzen Vorbereitungszeit gibt es dann wöchentlich (~2) Vorträge und Programmieraufgaben.

Anmeldung & Vorbesprechung

Die Anmeldung läuft über TUMonline: https://campus.tum.de/tumonline/lv.detail?cperson_nr=84589&clvnr=950041043.

Die Vorbesprechung findet am 6.2. von 09:45 - 10:15 im Raum 02.07.023 statt.

Anforderungen

Die folgenden Aufgaben müssen von den Teilnehmern erfüllt werden um das Seminar erfolgreich abzuschließen:

  • Eine Ausarbeitung (5 Seiten, A4, 12pt) zum eigenen Thema schreiben.
  • Eine Präsentation (ca. 25min) zum eigenen Thema erstellen und halten.
  • Programmieraufgaben zu den gegebenen Themen erfolgreich lösen.
  • Teilnahme an den (meisten) Präsentationstreffen.

Während die Lösung der Programmieraufgaben und die Teilnahme an den Treffen eine Grundvoraussetzung für das erfolgreiche Bestehen des Seminars sind, wird die Endnote aus den Noten der Ausarbeitung und der Präsentation gebildet. Ein erfolgreiches Bestehen des Seminars ist 4 ECTS Credits wert.

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.

Themen

Methoden zum Entwurf von Algorithmen

Suchen

Sortieren

Kürzeste Pfade (Dijkstra, Bellman-Ford, Floyd-Warshall; Heaps)

Flussnetzwerke (Ford-Fulkerson, Matching)

Lineare Programmierung (Simplexalgorithmus)

Numerische Verfahren (iterative Verfahren, Intervallschachtelung, Newton- Verfahren, Fehlerverhalten, Auslöschung)

Wahrscheinlichkeitsrechnung (Permutationen, Binomialkoeffizienten etc.)

Zahlentheorie (Primzahltests, Primfaktorzerlegung, Modulo, GGT)

Geometrie 1 (Schnitte von Geraden/Ebenen, Satz von Pick, Space-Trees)

Geometrie 2 (Konvexe Hüllen, Punkt-in-Polygon, Closest Pair)

NP-Vollständigkeit (Backtracking)

Dynamische Programmierung (Longest Increasing Subsequence, Scheduling, Levenshteindistanz)

Patternmatching

Zusatzmaterial

Tutorials, eine Anleitung zum Finden der User-ID und die Übersicht über gelöste Aufgaben findet sich auf der Kursseite (in Arbeit).

Programmieraufgaben von 2011

Die ersten Programmieraufgaben für dieses Semester sind:

Sortieren

Kürzeste Pfade

Flussnetzwerke

Wahrscheinlichkeitsrechnung

Zahlentheorie

Geometrie 1

Geometrie 2

NP-Vollständigkeit

Dynamisches Programmieren