Seminar

---

Readers

Torsten Grust • Denis Hirn • Tim Fischer • Louisa Lambrecht

⚠️ Die Anmeldung zu diesem Proseminar ist abgeschlossen.

Wir sind leider bereits voll belegt und können keine weiteren Studierenden zulassen.

In diesem Proseminar werden die TeilnehmerInnen mit jeweils einem ausgewählten Problem des seit 1970 alljährlich stattfindenden ACM Programming Contest konfrontiert. Diese Probleme zeichnen sich einerseits durch recht spassige und interessante Aufgabenstellungen aus, andererseits erlauben diese Aufgaben Lösungen, die oft sehr elegant und kompakt sind (der Kern umfasst typischerweise weniger als 50 Zeilen Programmcode) und fast immer mit “Aha!”-Effekten einhergehen.

Die SeminarteilnehmerInnen werden jeweils das Problem vorstellen, eine möglichst elegante Lösung—formuliert in der Lieblingsprogrammiersprache der Teilnehmerin—erarbeiten und diese während des Seminarvortrags präsentieren. (Falls es bei der Lösung des Problems “haken” sollte, ist das kein Show Stopper: wir geben dazu gerne Tipps — niemand muss deshalb dieses Seminar nicht bestehen.)

Seminartermine

Die genauen Termine der Vorträge selbst sprechen wir mit euch ab, sobald der genaue Kreis der Studierenden feststeht.

Alle Teilenehmer müssen an allen Terminen anwesend sein! Weitere interessierte Hörer sind herzlich willkommen.

Themen (ACM ICPC Problemstellungen) und Seminarablauf

Eine Einführung in das Seminar, ein Blick auf beispielhafte Problemstellungen und die Themenvergabe finden in einem ersten Treffen zu Beginn des Semesters statt.

Je zwei eurer Vorträge (Länge je ca. 25-30 Minuten, mit anschliessender kurzer Diskussion) werden zu den Seminarterminen stattfinden. Die Termine legen wir in Absprache mit euch fest.

Es besteht eine Verpflichtung zur Anwesenheit an allen Terminen — nicht zuletzt schon aus Fairness gegenüber euren Kommilitonen. Gebt uns ggf. Bescheid, falls ihr zu einem Termin begründet nicht erscheinen könnt.

Im Folgenden findet ihr einige ACM ICPC Problems als Beispiele für Probleme, die wir in diesem Seminar bearbeiten wollen:

ACM ICPC Problems:

• Solver

• Lazy Math Instructor

• Merging Maps

• Image is Everything

• Sisco’s Galaxy

• Black Box

• Booby Traps

• Fold-up Patterns

• Wiring Assistant

• Rush Hour

• Finding Seats

• Galou is Back

• Tree

• The Unsinkable Ship

• Turn All the Lights Off

• Biker

• Scanner

• Clock Breaking

• Oil

• Karel the Robot

• Triangles

• Go with the Flow

• Catch The Plane

• Directing Rainfall

Zu einigen der Probleme, die wir bearbeiten werden, findet ihr hier eine Möglichkeit die Ergebnisse zu eingegebenen Instanzen zu ermitteln. Unter Umständen findet ihr dort sogar Probleminstanzen vor, die Benutzer vor euch getestet haben.

Hinweise zu den Vorträgen

• Allgemeine Hinweise zu unseren Seminarvorträgen findet ihr hier.

• Wichtig: Auf einer Folie eures Vortrages sollet ihr möglichst genau begründen, warum ihr gerade die von euch gewählte Programmiersprache einsetzt. Falls ihr nur eine Programmiersprache beherrscht, verwendet diese Folie stattdessen darauf, 2–3 Features einer (fiktiven) Programmiersprache zu identifizieren, die euch bei der Formulierung der Lösung besonders hilfreich gewesen wären.

• Beachtet, dass beim ACM Programming Contest allgemein wohlgeformte Inputs vorausgesetzt werden dürfen. Eine explizite Behandlung illegaler Eingaben könnt ihr auch im Rahmen dieses Seminars ignorieren.

Hinweise zu den Ausarbeitungen

• Allgemeine Hinweise zu unseren Ausarbeitungen findet ihr hier.