Im November 2002 findet der ACM Northwestern European Regional Programming Contest in Delft statt, an dem Universitäten aus Deutschland, Dänemark, Finnland, Schweden, Norwegen, Island, Großbritannien, Irland, Belgien, Luxemburg und den Niederlanden teilnehmen werden. Ebenfalls im November 2002 findet der ACM Southwestern European Regional Programming Contest in Porto statt, mit Universitäten aus Deutschland, Frankreich, Italien, Österreich, Portugal, der Schweiz und Spanien.
Die Uni Ulm, die sich seit 1996 siebenmal hintereinander fuer die WM qualifizierte, sucht auch dieses Jahr wieder 12 Top-Programmierer, aus denen dann unsere drei Teams für einen der beiden Regionals gebildet werden. Deswegen wird am Freitag, den 05. Juli 2002 ein universitätsinterner Programmierwettbewerb stattfinden.
Teilnehmen können alle Studenten der Universität Ulm, die das Diplom noch nicht abgeschlossen haben und noch bis Ende 2002 in Ulm bleiben werden.
Insbesondere sind Studenten der ersten beiden Semester eingeladen, am Wettbewerb teilzunehmen (es kostet nichts - ist aber nicht umsonst, traut Euch :-)
| Austragungsort | O 27, Linux-Pool |
| Datum und Uhrzeit | Freitag, 05. Juli 2002, 13:15 Uhr |
| Wettbewerbsdauer | 5 Stunden |
| Betriebssystem | Linux |
| erlaubte Programmiersprachen | ANSI C, C++, Java, (Free) Pascal, Haskell |
| verwendete Compiler | gcc, g++, javac, ppc386, ghc |
| verwendbare Texteditoren | textedit, emacs, xemacs, nedit, joe oder vi (je nach Wunsch) |
| erlaubte Hilfsmittel | Bücher, Skripte, Listings, Man Pages (man, xman) |
| verbotene Hilfsmittel | Taschenrechner, Disketten, Laptop, Handy, FTP, Telnet, WWW, E-Mail |
Wir werden drei Teams bilden, wobei ein Team aus drei Programmierern und einer Reserve besteht.
Das Team 3 ist grundsätzlich für Studenten aus dem 1.-3. Semester reserviert, während die Teams 1 und 2 für Studenten bis zum 9. Semester offen sind.
(Letzteres ist eine Vorgabe für den Regionalwettbewerb - hier in Ulm dürfen auch Studenten aus höheren Semestern teilnehmen.)
Der Coach stellt die Teams im Einvernehmen mit den Bestplazieren des Lokalwettbewerbs auf.
Bis auf die eben erwähnten Beschränkungen sieht das üblicherweise so aus:
Plätze 1-3 => Team 1
Plätze 4-6 => Team 2
Plätze 7-9 => Team 3
Plätze 10-12 => Ersatzleute für Team 1, 2 und 3
| Bereich | Beispielprobleme |
|---|---|
| Backtracking | 8-Damen-Problem Springertour auf Schachbrett |
| Graphenprobleme | Kürzeste Route zwischen 2 Städten finden,
wobei eine Landkarte gegeben ist
Testen, ob ein gegebener gerichteter Graph einen Zyklus enthält |
| Computational Geometry | Bestimmen, ob sich zwei gegebene Strecken schneiden oder nicht
Konvexe Hülle eines Polygons bestimmen |
| Dynamisches Programmieren | Optimale Klammerung einer Kette von Matrixmultiplikationen A1 * A2 * ... * An, so dass die Anzahl der elementaren Multiplikationen minimiert wird |
| Zahlentheorie | Summe aller echten Teiler einer gegebenen Zahl berechnen
Alle Primzahlen p mit a <= p <= b ausgeben |
| Parser/Compilerbau | Eingabe: ein arithmetischer Ausdruck als String Ausgabe: das Resultat dieses Ausdrucks Beispiel: Eingabe: "4+3*(7-2)", Ausgabe: 19 |
Schaut Euch am besten mal die Aufgaben vom letzten Jahr an.
| Meldung | Bedeutung |
|---|---|
| Accepted | Programm ist als korrekt akzeptiert. Gratuliere. |
| Wrong Answer | Programm liefert falsche Antwort |
| Presentation Error | Algorithmus ist im Prinzip richtig, aber Ausgabe entspricht nicht der gegebenen Spezifikation |
| Time-Limit exceeded | Algorithmus ist zu langsam, d.h. Ausführungszeit für Beispieleingabe >> 60 sec |
| Run-Time Error | Programm stürzt ab |
| Compile-Time Error | Programm läßt sich nicht compilieren |
Man hat beliebig viele Versuche, bis man eine "Accepted"-Meldung erhält. Allerdings bekommt man für jeden Fehlversuch 20 Strafminuten zur benötigten Programmierzeit addiert. Achtung: Das heißt nicht, das man dann nach 4:40 h aufhören muss. Man darf auf jeden Fall 5 Stunden lang programmieren. Es wird dann aber so gewertet, als hätte man 5:20 h gebraucht.
Alle Teilnehmer, die mindestens ein Problem lösen, erhalten eine Urkunde,
für die drei Bestplazierten gibt es Medaillen.
Der Sieger erhält außerdem einen Pokal.
Hier sind ein paar Seiten, die Euch als Implementation für häufig vorkommende Algorithmen dienen können:
Rivest, Leiserson, Cormen:
"Introduction to Algorithms"
Skripte zu den Vorlesungen "Algorithmen" und "Algorithmen 2"
von Prof. Dr. Uwe Schöning. (erhältlich im Sekretariat für Theoretische
Informatik)
Sedgewick, R.: "Algorithmen"
Handbücher des RRZN Hannover für C, C++, Java, Pascal
(erhältlich im Universitätsrechenzentrum, O 26 für je 5-8 DM)
Bronstein, Semendjajew, et al.: "Taschenbuch der Mathematik" (oder andere Formelsammlungen)
05. Juli 2002
Walter Guttmann