„Hallo Welt!“ für Fortgeschrittene

„Hallo Welt!“ für Fortgeschrittene
Seminar im Sommersemester 2015
Tobias Werth, Daniel Brinkers
Informatik 2  Programmiersysteme  Martensstraße 3  91058 Erlangen
Menü




Überblick über Seminar und Programmierwettbewerb
Seminarvorträge im Allgemeinen und Besonderen
Einführung in Wiki, Forum und DomJudge
Verteilung der Vorträge
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 2
Um was geht‘s?
 Vertiefung der in AuD erlernten Programmierfähigkeiten
 Kennenlernen von weiterführenden Algorithmen
 Erkennen eines Problems und Anwendung des passenden
Algorithmus'
 Vorbereitung auf den ICPC-Programmierwettbewerb
 Erlernen von Präsentationstechniken: freier Vortrag vor
Publikum (ihr schult Euch gegenseitig)
 Kennenlernen, Ausprobieren und Einüben verschiedener
Teamstrategien
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 3
Was ist der ACM ICPC?
 ACM = Association for Computing Machinery
Älteste weltweite Gesellschaft für Informatik
 ICPC = International Collegiate Programming Contest
StudentInnen aus aller Welt messen sich in der Kunst des
Programmierens
 Vorausscheidungen an den Unis, um max. 3 Teams à 3
Personen zu bilden, in Erlangen im Sommersemester
 Regional Contest (NWERC) mit ca. 100 Teams aus
mehreren Ländern; die ersten zwei-drei Teams qualifizieren
sich für die World Finals
 World Finals mit den besten ca. 115 Teams aus aller Welt
 Seit 2002 nehmen wieder Teams aus Erlangen teil
http://icpc.cs.fau.de/
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 4
Was für Aufgaben werden gestellt?
 Kniffelige Probleme, die aber meist recht kurz
lösbar sind
 Wahl des passenden Algorithmus mit der passenden
Komplexität sehr wichtig
 Schema der Aufgaben
□ Kurze einleitende Geschichte
□ Beschreibung des Problems
□ Definition der Eingabedaten
□ Definition der Ausgabedaten
□ Kleine Beispiele
 Wahl der Programmiersprache (fast) frei:
C, C++11, Java, (bald Python)
zusätzlich Haskell im Online-Judge
weitere (sinnvolle) Sprachen auf Anfrage
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 5
Vorläufiger Zeitplan
1. Woche:
3. Woche:
4. Woche:
5. Woche:
6. Woche:
7. Woche:
8. Woche:
9. Woche:
10. Woche:
11. Woche:
12. Woche:
13. Woche:
ICPC in a nutshell
Parsen
Zeichenketten
Sortier- und Suchalgorithmen + Datenstrukturen
Dynamische Programmierung / Gierige Algorithmen
Graph-Algorithmen 1 / 2
Flüsse, Schnitte, bipartite Abbildungen
Zahlentheorie, Arithmetik und Algebra 1 / 2
Kombinatorik
Geometrie 1 / 2
Große Lösungsräume
Spieltheorie
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 6
Themen
 ICPC in a nutshell
C++ im Rahmen von ICPC, Komplexität, typische Fehler, Debuggen,
Teamstrategien, Training?
 Parsen
Grammatiken, Rekursiver Abstieg, Top-Down, Bottom-Up, CYK, Einlesen
und Ausgeben, Bibliotheksfunktionen...
 Zeichenketten
Suche in Zeichenketten, KMP, Boyer-Moore, Suffix-Tries, Algorithmus
von Manacher...
 Sortier- und Suchalgorithmen / Datenstrukturen
Quickselect, binäre Suche, ternäre Suche, Bibliotheksfunktionen, …
Binary Indexed Tree, Range Minimum Query, Segmentbäume...
 Graphalgorithmen 1+2
fortgeschrittene Grundlagen, Zusammenhangskomponenten, Brücken,
Artikulationspunkte...
Union/Find, Spannbäume, kürzeste Pfade, Euler Pfade, Färbbarkeit...
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 7
Themen
 Flüsse, Schnitte und bipartite Abbildungen
Ford-Fulkerson, Preflow-Push, Zweifärbbarkeit, ...
 Dynamische Programmierung
Wiederverwendung von Zwischenergebnissen, LIS/LCS,
Inklusion/Exklusion, Memoization...
 Gierige Algorithmen
Greedy-Choice Property, Scheduling, Abgrenzung zu DP,…
 Zahlentheorie, Arithmetik und Algebra 1+2
Primzahlen, Faktorisieren, modulare Arithmetik, Euklidischer Algorithmus,
Lemma von Bezout...
Chinesischer Restesatz, lineare diophantische Gleichungen, große
Zahlen,lineare Rekurrenzen, Gauss-Algorithmus, RSA...
 Kombinatorik
Binomial-Koeffizienten, Eulersche Zahlen, Catalan-Zahlen, StirlingZahlen, Permutationen, Integer-Partitionen,...
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 8
Themen
 Geometrie 1+2
Grundlagen, CCW, konvexe Hülle, Picks Theorem,
Koordinatenkompression…
closest pair, Histogramme, Bereichssuche, kD-Trees, Sweep-Line,
Voronoi-Diagramme...
 Suche im großen Lösungsraum
Backtracking, Branch und Bound, Pruning, Heuristiken, A*,...
 Spieltheorie
Nim, Josephus, Nash-Gleichgewicht, Gefangendilemma, MinimaxTheorem, Alpha-Beta-Pruning...
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 9
Literatur: die gängigen Algorithmenbücher
 Competitive Programming
Steven Halim, https://sites.google.com/site/stevenhalim/
 Introduction to Algorithms
Thomas H. Cormen, u. a. The MIT Press, 2001
 Algorithms in Java
Robert Sedgewick Addison-Wesley Professional, 2003
 Grundlegende Algorithmen
Volker Heun, Vieweg, 2003
 The Design and Analysis of Algorithms
Anany Levitin, Pearson International Edition, 2007
 …
 TopCoder Algorithm Tutorials
 Training: Codeforces, TopCoder SRM/Practice Rooms, SPOJ, Uva
Online Judge
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 10
Was wir bieten und was es kostet - Bachelor
5 ECTS Seminarschein (auch für „erfahrene Frühstudenten“):
 45-60 Minuten Vortrag zum jeweiligen Thema → Note
 Spätestens eine Woche vor Termin „Statusbericht“
 (Algorithmen-Templates)
 Zu jedem Thema werden Aufgaben gestellt,
□ Davon ist mindestens eine zu lösen, 1 Ausnahme, insgesamt 30
Aufgaben
□ Abgabe über FAU Online Judge (später mehr)
□ (Bearbeitungszeitraum von zwei Wochen)
□ (Bei 15 Aufgaben: 2,5 ECTS)
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 13
Was wir bieten und was es kostet – Bachelor 2
Schlüsselqualifikation:
 45-60 Minuten Vortrag zum jeweiligen Thema
 Spätestens eine Woche vor Termin „Statusbericht“
 Algorithmen-Templates
 Nur möglich, falls Informatik kein Haupt/Nebenfach
 Zu jedem Thema werden Aufgaben gestellt,
□ Davon ist mindestens eine zu lösen
□ Insgesamt aber 30
□ Abgabe über FAU Online Judge (später mehr)
□ (Bearbeitungszeitraum von zwei Wochen)
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 14
Ziele des Seminarvortrags





Wissen vermitteln
Lösung ICPC-Aufgaben
„Hallo Welt“  Algorithmik  Theoretische Informatik
Unterhaltungsfaktor
Der Vortragende und das Publikum sollen Spaß haben
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 15
Inhaltsbestimmung





Literatur sichten und lesen
Basisalgorithmen selber programmieren
Aufgaben zum eigenen Vortragsthema lösen
Langjährige ICPC-ler befragen
Vorwissen der Zuhörer beachten
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 16
Vorbereitung
 Beobachtet andere Vortragende
 Mindestens drei Wochen vorher beginnen
 Mindestens eine Woche vorher zur Besprechung mit
vollständigem Foliensatz
 Folien Korrektur lesen lassen
□ Tisch Bein
□ Grösse
□ Denglish
 Probevortrag halten
□ Lieblingswörter
□ ähhhh, öhhh,
□ ganze Sätze
 Kritik annehmen
 Schriftgröße, Farben am Beamer und mit Ausdruck testen
 Pünktlich zum eigenen Vortrag erscheinen
□ Laptop aufbauen
□ Tafel wischen
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 17
Präsentation




Sich auf das Wesentliche beschränken
Mit eigenen Worten wiedergeben
Keine Plagiate
Alle Quellen angeben
 Folienerstellung
□ Latex (beamer package)
□ Powerpoint, OpenOffice
□ PDF
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 18
Präsentation
 Ein Gedankengang pro Folie
 Stichwörter, keine ganzen Sätze




Schriftgröße: 20-28pt (hier: 24)
(Bunte) Bilder
Nicht zu viele Stilelemente
Animationen maßvoll einsetzen
 Pi mal Daumen: 1 –2 Minuten pro Folie sprechen
 Dem Zuhörer Zeit lassen, eine Folie zu lesen
 Auf den Inhalt einer Folie beim Sprechen eingehen
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 19
Aufnahmebereitschaft der Zuhörer
 (Fast) kein Mensch kann 60 Minuten nonstop
konzentriert zuhören
 Aufmerksamkeitsspanne: 20 Minuten
 Zuhörer aufwecken, wach halten
□
□
□
□
□
Themenwechsel
„Leichte Kost“, z.B. Messungen
Passendes Zitat einbauen
Übergangsfolien
Wechsel des Mediums: Tafel benutzen
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 20
ICPC Trainings-Wiki
Ziel: Sammlung von Algorithmen-Templates für Wettbewerbe
https://icpc.informatik.uni-erlangen.de/wiki/doku.php?
id=start&do=register
WICHTIG:
Die Templates duerfen ausschließlich in Hallo-Welt (mit Quellenangabe), in lokalen
Wettbewerben der Uni Erlangen oder von FAU-Teams beim ACM ICPC verwendet
werden! (Also nicht bei TopCoder, USACO...)
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 23
Forum & IRC-Channel + hallowelt@i2
Zur Diskussion von Aufgaben, Algorithmen und möglichen Lösungen:
IRC-Channel (im IRCnet, z.B. irc.uni-erlangen.de):
#hallowelt
Forum bei der FSI:
http://fsi.informatik.uni-erlangen.de/forum/forum/87
Pfad: Community › Coding › ACM ICPC
Bitte keine vollständigen Lösungen posten!
Als Thema sollte der Aufgabenname/ID verwendet werden.
Falls ihr nicht weiterkommt: [email protected]
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 24
FAU Online Judge
https://icpc.informatik.uni-erlangen.de/oj/
 Jeder hat sein eigenes Login (aus EST)
 Aufgabensammlung aus alten Erlanger Wettbewerben, Aufgaben sind einzelnen
Seminarthemen zugeordnet
 Gegeben: Aufgabenstellungen, Beispiel-Eingabe, Beispielausgabe
 Eingabe über stdin, Ausgabe über stdout
 Abgabe Eurer Lösungen über Domjudge
 Antwort: Time Limit Exceeded, Wrong Answer, Presentation Error, Memory Limit
Exceeded, Correct, ...
„Hallo Welt!“ für Fortgeschrittene – T.Werth, D. Brinkers  Sommersemester 2015  Folie 25

Download Report