Difference between revisions of "ICPC-Proseminar"

From Sccswiki
Jump to navigation Jump to search
Line 44: Line 44:
 
= Themen =
 
= Themen =
  
Die Liste der Themen ist derzeit noch im Wachstum begriffen und wird demnächst aktualisiert. Eigene Themenvorschläge sind gerne willkommen. Sobald die Liste vollständig ist werden die Themen vergeben. Hierzu schickt jeder eine Email
+
Die Themen sind jetzt vollständig, eigene Themenvorschläge können aber immer noch eingereicht werden. Die meisten Themen können auf zwei (oder drei) Personen aufgeteilt werden. Die in Klammern angegebenen Algorithmen sind als Vorschläge zu betrachten.  
 +
 
 +
Zur Themenwahl schickt jeder Teilnehmer eine Email
 
mit seinen drei Favoriten (geordnet nach 1.-3.). Es wird versucht jedem seinen bestmöglichen Favoriten zuzuordnen.  
 
mit seinen drei Favoriten (geordnet nach 1.-3.). Es wird versucht jedem seinen bestmöglichen Favoriten zuzuordnen.  
 
Eigene Themenvorschläge (solange nur von einer Person vorgeschlagen) werden für diese Person reserviert.
 
Eigene Themenvorschläge (solange nur von einer Person vorgeschlagen) werden für diese Person reserviert.
  
# Suchen
+
# Elementare Datenstrukturen (Stacks, Warteschlange, Listen, Bäume, Graphen, Hashtabellen)
# Sortieren
+
# Sortieren (Insertion sort, Merge sort, Heapsort, Quicksort, Sortieren in linearer Zeit, Median und Ordnungsstatistik)
# Kürzeste Pfade (Dijkstra, Bellman-Ford, Floyd-Warshall; Heaps)
+
# Suchen (Binäre Surce, Binärbäume, Red-Black Bäume, Fortgeschrittene Bäume)
 +
# Erweitern von Datenstrukturen (Dynamische Ordnungsstatistik, Leitfaden zum Erweitern, Intervall-Bäume)
 +
# Dynamische Programmierung (Rod cutting, Matrix chain multiplication, Longest common subsequence, Scheduling, Levenshteindistanz, CYK-Algorithmus)
 +
# Greedy Algorithmen (Activity selection, Huffmann codes)
 +
# Elementare Graph-Algorithmen (BFS, DFS, Topological sort, Strongly connected components)
 +
# Minimum spanning tree (Kruskal und Prim)
 +
# Kürzeste Pfade (Single-Source und All-Pairs Algorithmen, wie z.B. Dijkstra, Bellman-Ford, A*, Floyd-Warshall, Johnson)
 
# Flussnetzwerke (Ford-Fulkerson, Matching)
 
# Flussnetzwerke (Ford-Fulkerson, Matching)
 +
# Numerische Verfahren (Matrix-Operationen, iterative Verfahren, Intervallschachtelung, Newton-Verfahren, Fehlerverhalten, Auslöschung)
 
# Lineare Programmierung (Simplexalgorithmus)
 
# Lineare Programmierung (Simplexalgorithmus)
# Numerische Verfahren (iterative Verfahren, Intervallschachtelung, Newton-Verfahren, Fehlerverhalten, Auslöschung)
+
# Schnelle Fourier Transformation (DFT, FFT)
 +
# Zahlentheorie (Primzahltests, Primfaktorzerlegung, Modulo, GGT)
 +
# Algorithmische Geometrie (Schnittberechnung, Konvexe Hülle, Closest Pair, Space-Trees, Punkt-in-Polygon, Satz von Pick)
 +
# String Matching (Rabin Karp, Finite Automata, Knuth-Morris-Pratt)
 +
# NP-Vollständigkeit und Approximations-Algorithmen (Backtracking)
 
# Wahrscheinlichkeitsrechnung (Permutationen, Binomialkoeffizienten etc.)
 
# Wahrscheinlichkeitsrechnung (Permutationen, Binomialkoeffizienten etc.)
# Zahlentheorie (Primzahltests, Primfaktorzerlegung, Modulo, GGT)
+
# [reserviert] Neuronale Netze
# 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 =
 
= Zusatzmaterial =

Revision as of 12:25, 17 February 2012

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 formt sich das thematische Ziel des Seminars. Das Kennenlernen von Standardalgorithmen und deren Übertragung und Anpassung auf individuelle Problemstellungen. Dies geschieht zum einen durch Einzelvorträge und schriftlicher Ausarbeitungen und zum anderen durch Bearbeitung von Programmieraufgaben aus dem ICPC-Umfeld.

Die weiteren Ziele des Seminars liegen im Erlernen von typischen Soft Skills: der selbständigen Erarbeitung eines Themengebiets, dessen Zusammenfassung und Erläuterung in Form einer Ausarbeitung, sowie der Erstellung und Abhaltung einer Präsentation.

Das Seminar richtet sich dabei nicht nur an Studenten/innen, die am ICPC-Wettbewerb teilnehmen wollen, sondern bietet für alle die Möglichkeit die eigenen Programmierfähigkeiten im Hinblick auf konkrete algorithmische Problemstellungen zu verbessern und Übung im Schreiben sowie Präsentieren zu erhalten.

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

Die Themen sind jetzt vollständig, eigene Themenvorschläge können aber immer noch eingereicht werden. Die meisten Themen können auf zwei (oder drei) Personen aufgeteilt werden. Die in Klammern angegebenen Algorithmen sind als Vorschläge zu betrachten.

Zur Themenwahl schickt jeder Teilnehmer eine Email mit seinen drei Favoriten (geordnet nach 1.-3.). Es wird versucht jedem seinen bestmöglichen Favoriten zuzuordnen. Eigene Themenvorschläge (solange nur von einer Person vorgeschlagen) werden für diese Person reserviert.

  1. Elementare Datenstrukturen (Stacks, Warteschlange, Listen, Bäume, Graphen, Hashtabellen)
  2. Sortieren (Insertion sort, Merge sort, Heapsort, Quicksort, Sortieren in linearer Zeit, Median und Ordnungsstatistik)
  3. Suchen (Binäre Surce, Binärbäume, Red-Black Bäume, Fortgeschrittene Bäume)
  4. Erweitern von Datenstrukturen (Dynamische Ordnungsstatistik, Leitfaden zum Erweitern, Intervall-Bäume)
  5. Dynamische Programmierung (Rod cutting, Matrix chain multiplication, Longest common subsequence, Scheduling, Levenshteindistanz, CYK-Algorithmus)
  6. Greedy Algorithmen (Activity selection, Huffmann codes)
  7. Elementare Graph-Algorithmen (BFS, DFS, Topological sort, Strongly connected components)
  8. Minimum spanning tree (Kruskal und Prim)
  9. Kürzeste Pfade (Single-Source und All-Pairs Algorithmen, wie z.B. Dijkstra, Bellman-Ford, A*, Floyd-Warshall, Johnson)
  10. Flussnetzwerke (Ford-Fulkerson, Matching)
  11. Numerische Verfahren (Matrix-Operationen, iterative Verfahren, Intervallschachtelung, Newton-Verfahren, Fehlerverhalten, Auslöschung)
  12. Lineare Programmierung (Simplexalgorithmus)
  13. Schnelle Fourier Transformation (DFT, FFT)
  14. Zahlentheorie (Primzahltests, Primfaktorzerlegung, Modulo, GGT)
  15. Algorithmische Geometrie (Schnittberechnung, Konvexe Hülle, Closest Pair, Space-Trees, Punkt-in-Polygon, Satz von Pick)
  16. String Matching (Rabin Karp, Finite Automata, Knuth-Morris-Pratt)
  17. NP-Vollständigkeit und Approximations-Algorithmen (Backtracking)
  18. Wahrscheinlichkeitsrechnung (Permutationen, Binomialkoeffizienten etc.)
  19. [reserviert] Neuronale Netze

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