Hallo Welt!“ für Fortgeschrittene ” Daniela Novac, Michael Baer Lehrstuhl für Informatik 2 (Programmiersysteme) Übersicht ICPC und das Seminar Themengebiete Vortrag Aufgaben Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 2 / 31 Übersicht ICPC und das Seminar Themengebiete Vortrag Aufgaben Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 3 / 31 Der ICPC Der ICPC - International Collegiate Programming Contest I 10 Probleme I 5 Stunden I 3 Studenten I 1 Computer Struktur 1. GCPC (Sommercontest) : besten 6 Teams (18 Studenten) 2. FAU interne Qualifikation : 10 Besten Teilnehmer bilden 3 Teams 3. NWERC : Besten 1-3 Teams 4. World Finals: 12 Medaillenplätze Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 4 / 31 ICPC - wichtige Termine Termine I 15. - 20. Mai 2016: World Finals in Phuket, Thailand I 4. Juni 2016: GCPC in Erlangen I Ende November 2016: NWERC I Mai 2017: World Finals Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 5 / 31 Seminar - Zielsetzung Lernen ... I ... einen Vortrag zu halten I ... von Algorithmen I ... den richtigen Algorithmus zu finden I ... Vorbereitung auf den ICPC Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 6 / 31 Seminar - Ablauf (1) I 5 ECTS I 45 - 60 Minuten Vortrag =⇒ Note I I Spätestens 1 Woche vorher Folien schicken Lösen von Aufgaben I mündliche Prüfung Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 7 / 31 Seminar - Ablauf (2) Bachelor I Anwesenheit I Prüfung über eigenen Vortrag (15 min) I 1 Aufgabe pro Themengebiet I 30 Aufgaben insgesamt ( ohne Warmup(WU) ) Master I Anwesenheit I Prüfung über eigenen Vortrag + 2 wählbare Themen (30 min) I 1 Aufgabe pro Themengebiet I 30 Aufgaben insgesamt ( ohne Warmup(WU) ) I davon 10 aus MASTER Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 8 / 31 Übersicht ICPC und das Seminar Themengebiete Vortrag Aufgaben Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 9 / 31 Parsen Parsen I Grammatiken (inkl. Reduktion) I Rekursiver Abstieg I CYK I Regex I In-/Output I Bibliotheksfunktionen Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 10 / 31 Zeichenketten Zeichenketten I Suche, KMP, Boyer-Moore, Rabin-Karp I (Suffix-)Tries I Manacher Algorithmus Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 11 / 31 Sortieren und Suchen Sortieren und Suchen I binäre Suche, ternäre Suche I Binary Indexed Tree (BIT) I Range Minimum Query (RMQ) I Segmentbäume I Bibliotheksfuntionen Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 12 / 31 Graphen Graphen I I Zusammenhangskomponenten I Brücken, Artikulationspunkte I Topologische Sortierung Graphen II I Spannbäume mit Union/Find I kürzeste Pfade I Euler Pfade Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 13 / 31 Flüsse, Schnitte, Bipartite Graphen FSB I I Ford-Fulkerson (+ Edmund-Karp) I Minimaler Schnitt I Reduktion I Konnektivität FSB II I Bipartites Matching mit Fluss I stabiles Heiraten I gewichtetes bipartites Matching (Ungarische Methode) Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 14 / 31 Dynamische Programmierung DP I LIS / LCS / Editierdistanz I Memoization (Top-Down, Bottom-Up) Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 15 / 31 Gierige Algorithmen Gierige Algorithmen I Greedy-Choice Property I Scheduling I Abgrenzung zu DP Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 16 / 31 Zahlentheorie Zahlentheorie I I Primzahlen (Faktorisierung, Pollard-Rho) I modulare Arithmetik (inkl. Fast-Exp) I erweiterter Euklid Zahlentheorie II I Chinesischer Restsatz I lineare diophantische Gleichungen I BigInt I lineare Rekurrenz I RSA Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 17 / 31 Kombinatorik Binomial-Koeffizienten I Eulersche Zahlen I Catalan-Zahlen I I Stirling Zahlen Permutationen I Integer-Partitionen Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 18 / 31 Geometrie Geometrie I I Grundlagen I CCW I I Polygone (Fläche, Punkt in P) Picks Theorem I Konvexe Hülle Geometrie II I Koordinatenkompression I Closest Pair I kD-Trees I Sweep-Line I Voronoi-Diagramme Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 19 / 31 Große Lösungsräume Große Lösungsräume I Backtracking I Branch und Bound I Pruning I Heuristiken (A*) Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 20 / 31 Spieltheorie Spieltheorie I Gefangenendilemma I Nim I Minimax-Theorem I Nash-Gleichgewicht I Alpha-Beta-Pruning Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 21 / 31 Übersicht ICPC und das Seminar Themengebiete Vortrag Aufgaben Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 22 / 31 Folien Fragen I Was will ich vermitteln? I Was ist wichtig? ⇒ ich muss alles verstanden haben ⇒ Stichpunkte, keep it simple I Wie kann ich das am besten vermitteln? ⇒ Bilder, Farben I Wie viel Zeit habe ich? I Vorlagen? ⇒ eine Folie pro Minute ⇒ LATEX, OpenOffice, PowerPoint Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 23 / 31 Presentation Hinweise I Frei sprechen, nicht vorlesen I Publikum in die Augen schauen I Ruhig bleiben I Kontext für die Stichpunkte erklären I Beispiele bereit haben I Andere Medien verwenden (z.B. Tafel) I Zusammenfassen am Anfang und am Ende I Fragen erst am Ende beantworten Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 24 / 31 Votragsthema Richtlinien I Mail mit weiteren Erklärungen und Quellen kommt I Vorwissen aus AuD ist vorrausgesetzt I Algorithmen selber testen I Aufgaben im Online Judge lösen I Zusätzliche Beispiele bereit haben I Mögliche Fragen voraussagen Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 25 / 31 Vorbereitung Vor dem Vortrag I Früh genug anfangen I Folien eine Woche davor einreichen I Probevortrag halten (Erklärungen, Beispiele, Zeit) Rechtzeitig da sein I I I I I Tafel wischen Raum kontrollieren Beamer testen Es wird alles bewertet Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 26 / 31 Übersicht ICPC und das Seminar Themengebiete Vortrag Aufgaben Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 27 / 31 Programmieraufgaben Online Judge I https://icpc.cs.fau.de/oj/ I Alte ICPC Probleme nach Themen sortiert (HW16 Tag) I Zugang mit EST-Login (Accounts verbinden) Mehrere Lösungseinreichungen möglich I Input/Output Beispiel Sample Input Sample Output 4 4 *... .... .*.. .... 3 5 **... ..... .*... 0 0 Field #1: *100 2210 1*10 1110 Hallo Welt!“ für Fortgeschrittene • Field #2: **100 33200 1*100 Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 28 / 31 Submissions Ergebnisse I Time Limit Exceeded (TLE): zu langsam I I I Wrong Answer (WA): falsche Antwort I I I I Segfault, Exception Zuviel Speicher Compiler Error: Falsche Syntax (Ausgabe verfügbar) I I I Normalerweise großzügige Checker Nicht überall vorhanden Run-Error: Programm ist abgestürtzt I I Richtiger Algorithmus? Presentation Error: Falsche Darstellung (Whitespaces) I I Falsche Komplexitätsklasse? Evtl in Biblioteksfunktion versteckt? Falsche Datei Falsche Sprache Correct (AC): Richtig Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 29 / 31 Vorbereitung Hilfe I IRC (im IRCnet, z.B. irc.uni-erlangen.de): #hallowelt I [email protected] I https://icpc.cs.fau.de/wiki/doku.php?id=start&do=register Templates Die Templates dürfen ausschließlich für HalloWelt oder bei lokalen Wettbewerben der FAU verwendet werden. Nicht online veröffentlichen. (z.B. TopCoder) Üben I TopCoder https://www.topcoder.com I Codeforces http://codeforces.com I Spoj http://www.spoj.com I UVa Onlinejudge https://uva.onlinejudge.org/ Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 30 / 31 Vielen Dank für Ihre Aufmerksamkeit! Hallo Welt!“ für Fortgeschrittene • Informatik 2 • 04.02.2016 • Daniela Novac, Michael Baer • Folie 31 / 31
© Copyright 2024 ExpyDoc
