Topic outline

  • Seminar: Algorithmen für Programmierwettbewerbe

    Umfang: 5 ECTS, 2 SWS
    Zeit & Ort: Mi 16-18 Uhr, online
    Voraussetzung:
    • Algorithmen und Datenstrukturen (notwendig)
    • Algorithmische Graphentheorie (dringend empfohlen)
    Zielgruppe: Bachelor Informatik, Bachelor Luft- und Raumfahrt-Informatik, Master Informatik
    Modul: Bei erfolgreicher Teilnahme wird die Leistung als (benotetes) Seminar eingetragen.
    Dozenten: Thomas van Dijk, Jonathan Klawitter

    Thema und Ziele

    In diesem Seminar sollen die Techniken aus den Vorlesungen ADS und AGT vertieft und angewendet werden. Dazu nutzen wir Aufgaben aus vergangenen Programmierwettbewerben. Fähigkeiten, die im Speziellen in diesem Seminar vermittelt werden:

    • Programmierprobleme mit Hilfe der Techniken aus ADS und AGT lösen
    • Vergleich/Abwägen von verschiedenen Lösungsansätzen
    • Implementierung gängiger Programmiertechniken einüben
    • Recherche und Präsentation verschiedener Lösungsansätze

    Die Teilnehmenden lernen, sich intensiv in ein abgegrenztes Thema aus dem Themengebiet einzuarbeiten, dieses didaktisch aufzubereiten und den anderen Kursteilnehmenden in einem Vortrag zu vermitteln. Dieses Thema und die zugrundeliegende Literatur sollen sie selbstständig finden und vorschlagen.

    Anmeldung

    Wenn du am Seminar teilnehmen möchten, melden dich hier in WueCampus an. Die Teilnahme erfolgt in 2er-Teams! Gibt uns daher nach der Anmeldung bitte bescheid, ob du noch ein Teammitglied benötigst oder aber mit wem ihr ein Team bildst. In der ersten Semesterwoche werden wir dann entscheiden welche Teams einen Platz bekommen. Gleichzeitig wird in dieser Woche dann die Themenvergabe erfolgen.

    Wenn ihr einen Platz im Seminar bekommen habt, dann meldet euch in WueStudy für das Seminar an. Dies ist nur im November möglich und wenn diese Anmeldung verpasst wird, kann keine Note verbucht werden.

    Ablauf

    In diesem Seminar verbinden wir die Vorträge mit praktischen Übungen. Jedes Team wird einen Votrag (~15 Minuten) online als Aufnahme zu einer Programmieraufgabe präsentieren. Die anderen Teams implementieren anschließend selbstständig eine Lösung für die Aufgabe. Das jeweils vortragende Team steht im Chat für Fragen und Hilfestellungen bereit.

    Vor dem eigenen Vortrag, trifft sich jedes Team zwei mal mit einem der Dozenten. Bis spätestens zwei Wochen davor muss der Lösungsansatz des eigenen Problems und bis spätestens eine Woche davor müssen die (bis dahein bereits erstellten) Folien für den Vortrag besprechen werden.

    Evaluierung

    Zum Bestehen des Seminars muss ihre Gruppe ein Vortrage online als Aufnahme präsentieren, wobei ein Nichteinhalten einer Fristen für Besprechungen als Nichtbestehen bewertet werden kann und wobei der Vortrag zu gleichen Teilen unter den Mitgliedern aufgeteilt wird. Außerdem müssen die meisten Probleme in DOMjudge gelöst werden. Hierfür gelten die folgenden Bedingungen:

    • Jedes Team muss vier der ersten fünf Seminarprobleme lösen (also alle bis auf eines aus B bis F).
    • Jedes Team muss fünf der verbleibenden sechs  Seminarprobleme lösen (also alle bis auf eines aus G bis N).
    • Zusätzlich darf jedes Team noch ein Problem auslassen.
    • Zeitplan & Vorträge

      Termin Thema
       Material
      04.11.2020
      Einführung, Gruppeneinteilung, Themenvergabe, X
      TvD
       
      11.11.2020 Problem Y: ProblemVideo                 
      TvD
      Folien
      18.11.2020 GCPC Test Session

      25.11.2020 Problem B: Avast
      SH+MN Folien
      02.12.2020
      Problem C: Teamwork
      KG+TS Folien
      09.12.2020 Problem D: Toving Liles
      JS+RB Folien
      16.12.2020 Problem E: Problem of packing
      ML+LL Folien
      23.12.2020 Problem F: Telephone a Taxi
      SW+YP Folien
      13.01.2021 Problem G: Patent claims
      DW+MB Folien
      20.01.2021 Problem H: Single lane serpentine
      TF+BM
      27.01.2021 Problem K: Flipping out
      SF+BM
      03.02.2021  Problem L: Molvanian castles
      BH+MH
      10.02.2021 Problem M: Inconspicuous hacking
      TG+MM
      17.02.2021 Problem N: Around the track
      AS+SD


      • Themen

        Die Themen wurde all in der ersten Semesterwoche vergeben.

        Jeder Teilnehmer sollte über DOMjudge (siehe unten) einen Account erstellen und Problem X lösen.

      • Einreichungssystem DOMjudge

        Lösungen werden eingereicht mit DOMjudge; der Server ist Uni-Intern und über VPN verfügbar unter: http://domjudge.informatik.uni-wuerzburg.de

        Sehen Sie unsere Videoanleitung. Erstellen Sie ein Account und lösen Sie das Problem X.

        Der Server kompiliert und führt Ihren Code aus. Es gibt Sicherheitsmaßnahmen, die versuchen, Sie daran zu hindern, zu den geheimen Instanzen zu gelangen, aber hier ist die eigentliche Sicherheitsmaßnahme (genau wie bei echten Wettbewerbe): Wenn Sie versuchen, uns zu hacken, werden Sie disqualifiziert.
        Zeit- oder Speicherüberlauf sollte von DOMjudge aufgefangen werden, also machen Sie sich darüber keine Sorgen. Aber eine Fork-Bombe (z.B.) wird den Server wahrscheinlich umbringen. Machen Sie es einfach nicht.

        • Vorträge / Videos