Personal tools

ICPC-Proseminar

From Sccswiki

Jump to: navigation, search

Contents

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

Term
Summer 14
Advisor
Kristof Unterweger
Time and Place
Donnerstags, 10:30 - 12:00 Uhr, Raum 02.07.023
Audience
Informatik (Bachelor), Mathematik (Bachelor), Wirtschaftsinformatik (Bachelor); Modul IN0013 [1]
Semesterwochenstunden / ECTS Credits
4
TUMonline
https://campus.tum.de/tumonline/lv.detail?clvnr=950137395&sprache=1



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

Anmeldung & Vorbesprechung

Die Anmeldung läuft über TUMonline.

Die Vorbesprechung findet am 30.1. von 13:00 - 14:00 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 (20min ohne Fragen) 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

Hier findet sich eine Liste mit Vortragsthemen; eigene Themenvorschläge können aber immer noch eingereicht werden. Die in Klammern angegebenen Algorithmen sind als Vorschläge zu betrachten.

Die Themenwahl erfolgt nach der Anmeldung auf der Moodleseite des Kurses.

  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. Logik
  14. Künstliche Intelligenz / Spieltheorie
  15. Schnelle Fourier Transformation (DFT, FFT)
  16. Beweisverfahren
  17. Zahlentheorie 1 (Primzahltests, Primfaktorzerlegung, Modulo, GGT)
  18. Zahlentheorie 2 (chinesischer Restsatz, Potenzierung, RSA)
  19. Genetische Algorithmen
  20. Algorithmische Geometrie (Schnittberechnung, Konvexe Hülle, Closest Pair, Space-Trees, Punkt-in-Polygon, Satz von Pick)
  21. String Matching (Rabin Karp, Finite Automata, Knuth-Morris-Pratt)
  22. NP-Vollständigkeit und Approximations-Algorithmen (Backtracking)
  23. Wahrscheinlichkeitsrechnung (Permutationen, Binomialkoeffizienten etc.)
  24. Neuronale Netze
  25. Laufzeitabschätzungen (Komplexitätstheorie, Leitfaden für die maximale Komplexitätsklasse)
  26. Kombinierte Aufgaben (Probleme die mehrere Lösungsansätze vereinen)


Hinweise für die Präsentationen und Ausarbeitungen

Wichtige Hinweise zur Erstellung und Abhaltung der Präsentation gibt folgendes Paper: http://dl.acm.org/citation.cfm?id=346055&bnc=1

Allgemeine Hinweise zu Präsentation und Ausarbeitung

  • Aufbau:
    • Kurzzusammenfassung (Abstrakt)
    • Einleitung
    • Hauptteil (Algorithmen, Datenstrukturen, Anwendungsbeispiele, ...)
    • Zusammenfassung
    • Quellenangaben
  • Die Präsentation/Ausarbeitung ist nicht dazu gedacht ihren Kommilitonen/innen zu zeigen wie schlau sie sind. Das heißt aber auch nicht, dass sie schwierige Themen meiden sollten. Versuchen sie ihre Präsentation und Ausarbeitung so zu gestalten, dass man möglichst viel davon lernen kann.
  • Das Seminar ist auf praktische Gesichtspunkte ausgelegt. Herleitungen und Komplexitätsbeweise sind nicht im Vordergrund und sollten wenn möglich weggelassen werden. Stattdessen, zeigen sie wo ein Algorithmus oder eine Datenstruktur Anwendung findet um praktische Probleme zu lösen.
  • Benutzen sie eine konsistente Notation. D.h., wenn sie sich einmal für einen bestimmten Stil von Schriften, Grafiken, Formeln, Pseudocode, ..., entschieden haben, behalten sie diesen für die ganze Ausarbeitung/Präsentation bei.
  • Schematische Bilder/Grafiken sollten nach Möglichkeit selbst erstellt werden. Werden Bilder/Grafiken aus einer anderen Quelle verwendet, sind immer Quellenangaben erforderlich.

Hinweise zur Ausarbeitung

  • Schreiben sie die Ausarbeitung vor der Präsentation, dann haben sie sich schon genaue Ausformulierungen für komplexe Themeninhalte überlegt und können die Folien Stichpunktartig gestalten.
  • Benutzen sie eine gute automatische Rechtschreibprüfung NACH der letzten Änderung am Text.
  • Die Einleitung soll auf das bearbeitete Themengebiet hinlenken und aufzeigen in welchem größeren Kontext dieses eingebettet ist. Sie soll weiterhin einen Überblick über die behandelten Inhalte geben und wichtige Ergebnisse (wenn vorhanden) vorwegnehmen. Letzer Teil der Einleitung ist eine kurze Kapitelübersicht.
  • Die Zusammenfassung wiederholt die wichtigsten Erkenntnisse/Ergebnisse und gibt einen Ausblick auf weitere Themengebiete (wenn sinnvoll). Sie ist KEINE Wiederholung der Einleitung.
  • Eine typische Quellenangabe besteht aus:
    • Autor/en
    • Titel
    • Verlag
    • Veröffentlichungsjahr
    • Seiten
    • Band
  • Internet-Quellenangaben sind nach Möglichkeit zu vermeiden und durch wissenschaftliche Publikationen zu ersetzen. Falls unvermeidlich, muss neben der URL auch das Abrufdatum mit angegeben sein.
  • Kriterien zur Bewertung einer Ausarbeitung:
    • Sprache (Grammatik, Rechtschreibfehler, Formulierungen)
    • Inhalt (Struktur, ist alles Wesentliche vorhanden, sind Erklärungen gut, gibt es einen "roten Faden", sind Formeln/Algorithmen konsistent)
    • Darstellung (Übersichtlichkeit, Konsistenz, gute und genügend Bilder)
    • Länge (Richtige Schriftgröße, Format, Anzahl Seiten, Keine großen Lücken)

Hinweise für die Präsentation

  • Halten sie sich an die 5 +- 2 Regel. D.h. pro Folie werden nicht mehr als 3-7 Punkte gezeigt/erläutert.
  • Benutzen sie nur Stichpunkte auf den Folien, keine ganzen Sätze. Nutzen sie die Stichwörter um eine Erklärung mit eigenen Worten zu geben. Dadurch wird die Aufmerksamkeit der Zuhörer nicht zwischen ihrer Erklärung und der auf ihren Folien geteilt. Eine Ausnahme sind z.B. Definition o.ä., die sie Wort für Wort durchgehen wollen.
  • Die Schrift soll sich maximal vom Hintergrund absetzen. Normalerweise heißt das dunkle Schrift und heller (weißer) Hintergrund.
  • Benutzen sie möglichst viele Bilder um schwierige Sachverhalte zu erklären und um reine Textfolien aufzulockern.
  • Achten sie bei Bildern und insbesondere Graphen darauf, dass die Beschriftung auch bei der kleineren Auflösung eines Beamers noch lesbar sind. Einzelne Messkurven sollten sich nicht nur farblich unterscheiden (weil die Farben eines Beamers typischerweise bei ihrer Präsentation nicht funktionieren), sondern auch in der Liniendarstellung (z.B. punktiert, gestrichelt, ...).
  • Zum Aufbau einer Präsentation: dieser ist ähnlich wie bei der Ausarbeitung. Es gibt eine sehr kurze Zusammenfassung des gesamten Vortrags am Anfang (typischerweise wenn sie über das Inhaltsverzeichnis gehen). Diese Sollte kein "Zuerst kommt die Einleitung, dann der Hauptteil, dann gebe ich eine Zusammenfassung" sein, sondern schon erwähnen was sie konkret einleiten und was konkret im Hauptteil kommt. Wenn sie den Teilen ihres Vortrags konkrete Namen geben, wird ihnen dies auch einfach fallen. Sie können die Zuhörer immer wieder orientieren, indem sie kurze Zwischen-Zusammenfassungen geben (z.B. nach der Hälfte des Vortrags) und das Inhaltsverzeichnis wiederholt zeigen.
  • Zur Sprache: sprechen sie klar, laut (genug) und eher langsam (aber nicht übertrieben). Machen sie kurze Pausen. Modulieren sie ihre Stimme (schnell-langsam, laut-leise, hoch-tief) um mehr Dynamik in den Vortrag zu bringen. Achten sie darauf keine Endlossätze mit "uuuund", "ähhhhm" oder anderen Füllwörtern zu konstruieren. Während dem Vortrag werden sie es kaum schaffen auf mehr als eines der genannten Dinge zu achten. Üben sie den Vortrag deshalb im voraus!
  • Sprechen sie wann immer möglich zum Publikum und nicht zur Wand - oder wie machen sie das in einem normalen Gespräch?
  • Seien sie ehrlich zu sich selber mit der Anzahl der Folien. Machen sie einen Probevortrag um den Zeitrahmen besser einschätzen zu können. Lieber weniger Inhalt, diesen aber richtig und gut erklärt.
  • Kriterien zur Bewertung eines Vortrags:
    • Sprache (Geschwindigkeit, Modulation, Klarheit, ...)
    • Inhalt (Passt die Struktur der Kapitel, Gibt es eine gute Einleitung/Zusammenfassung, ist alles Wesentliche enthalten, sind Erklärungen gut, gibt es einen "roten Faden", wird konsistent erklärt)
    • Darstellung (Übersichtlichkeit, Farbwahl, Schriftwahl, genügend Bilder, gute Bilder)
    • Zeitrahmen (zu lang oder zu kurz)
    • Zuhörer-Fragen richtig und ausreichend beantwortet

Referenzen

  • Introduction to Algorithms, Cormen, Leiserson, Rivest, Stein, MIT Press
  • Algorithmen - Eine Einführung, Cormen, Leiserson, Rivest, Stein, MIT Press