Difference between revisions of "ICPC-Proseminar"
| Line 3: | Line 3: | ||
{{Seminar | {{Seminar | ||
| term = Summer 11 | | term = Summer 11 | ||
| − | | advisor = [[ | + | | advisor = [[Bernhard Gatzhammer, M.Sc]] |
| − | | timeplace = | + | | timeplace = in Arbeit |
| credits = 4 | | credits = 4 | ||
| − | | audience = Informatik (Bachelor), Mathematik (Bachelor), Wirtschaftsinformatik (Bachelor); Modul IN0013 | + | | audience = Informatik (Bachelor), Mathematik (Bachelor), Wirtschaftsinformatik (Bachelor); Modul IN0013 [https://drehscheibe.in.tum.de/myintum/kurs_verwaltung/cm.html?id=IN0013] |
}} | }} | ||
= Hintergrund = | = Hintergrund = | ||
| − | Jedes Jahr veranstaltet die Association for Computing Machinery (ACM) den International Collegiate Programming Contest (ICPC). In diesem Wettbewerb lösen Dreierteams an einem Computer Programmieraufgaben innerhalb einer vorgegebenen Zeitspanne. | + | Jedes Jahr veranstaltet die Association for Computing Machinery (ACM) [http://www.acm.org/] den International Collegiate Programming Contest (ICPC) [http://cm.baylor.edu/welcome.icpc]. 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. | 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. | ||
| Line 24: | Line 24: | ||
= Anmeldung & Vorbesprechung = | = Anmeldung & Vorbesprechung = | ||
| − | Die Anmeldung läuft inzwischen zentral über | + | Die Anmeldung läuft inzwischen zentral über TUMonline (in Arbeit). |
| − | + | Der Vorbesprechungstermin wird noch bekannt gegeben. | |
= Anforderungen = | = Anforderungen = | ||
| Line 38: | Line 38: | ||
= Themen = | = Themen = | ||
| + | |||
| + | Methoden zum Entwurf von Algorithmen | ||
Suchen (Nguyen) | Suchen (Nguyen) | ||
| Line 68: | Line 70: | ||
= Zusatzmaterial = | = Zusatzmaterial = | ||
| − | Tutorials, eine Anleitung zum Finden der User-ID und die Übersicht über gelöste Aufgaben findet sich auf der | + | Tutorials, eine Anleitung zum Finden der User-ID und die Übersicht über gelöste Aufgaben findet sich auf der Kursseite (in Arbeit). |
| − | = Programmieraufgaben = | + | = Programmieraufgaben von 2011 = |
Die ersten Programmieraufgaben für dieses Semester sind: | Die ersten Programmieraufgaben für dieses Semester sind: | ||
Revision as of 13:42, 20 January 2012
Contents
Geschickt Programmieren für den ICPC-Wettbewerb (Proseminar)
- Term
- Summer 11
- 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
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 hat dieses Seminar zwei Ziele. Zum einen stellen die Seminarteilnehmer in Einzelvorträgen 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 Onlinebewertungsplattform 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.
Zeitplan
Das Seminar findet, je nach Teilnehmerzahl, wöchentlich oder 14-tägig statt.
Anmeldung & Vorbesprechung
Die Anmeldung läuft inzwischen zentral über TUMonline (in Arbeit).
Der Vorbesprechungstermin wird noch bekannt gegeben.
Anforderungen
Jeder Teilnehmer hält einen Vortrag über ein Thema. Dabei geht es vor allem darum, die Funktionsweise des Algorithmus verständlich zu erklären. Über das Thema des Vortrags ist eine fünfseitige Ausarbeitung zu verfassen.
Zudem muss mindestens aus jedem Bereich eine Programmieraufgabe gelöst werden.
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 (Nguyen)
Sortieren (Sievers)
Kürzeste Pfade (Dijkstra, Bellman-Ford, Floyd-Warshall; Heaps) (Erlacher)
Flussnetzwerke (Ford-Fulkerson, Matching) (Kohl)
Lineare Programmierung (Simplexalgorithmus)
Numerische Verfahren (iterative Verfahren, Intervallschachtelung, Newton- Verfahren, Fehlerverhalten, Auslöschung)
Wahrscheinlichkeitsrechnung (Permutationen, Binomialkoeffizienten etc.)
Zahlentheorie (Primzahltests, Primfaktorzerlegung, Modulo, GGT) (Dürre)
Geometrie 1 (Schnitte von Geraden/Ebenen, Satz von Pick, Space-Trees) (Ihrke)
Geometrie 2 (Konvexe Hüllen, Punkt-in-Polygon, Closest Pair) (Kerscher)
NP-Vollständigkeit (Backtracking) (Fischer)
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
- Train Swapping (Problem 299)
- Ultra-QuickSort (Problem 10810)
Kürzeste Pfade
- Lift Hopping (Problem 10801)
- Wormholes (Problem 558)
Flussnetzwerke
- My T-shirt suits me (Problem 11045)
- Angry Programmer (Problem 11506)
Wahrscheinlichkeitsrechnung
- Binomial Showdown (Problem 530)
- What is the Probability? (Problem 10056)
- Urn-ball Probabilities! (Problem 10169)
Zahlentheorie
- Cantor Fractions (Problem 880)
- Fibonaccimal Base (Problem 948)
- Minimum Sum LCM (Problem 10791)
Geometrie 1
- Video Surveillance (Problem 588)
- The Silver Bullet (Problem 11227)
Geometrie 2
- SCUD Busters (Problem 109)
NP-Vollständigkeit
- Don't Get Rooked (Problem 639)
- e-Coins (Problem 10306)
Dynamisches Programmieren
- Travelling Salesman (Problem 10702)
