ACM-ICPC

Der ACM International Collegiate Programming Contest, abgekürzt ACM-ICPC oder ICPC, ist ein jährlich stattfindender, weltweiter und mehrstufiger Programmierwettbewerb für Universitätsstudenten. Der Wettbewerb fordert und fördert das Können der teilnehmenden Dreierteams im Gebiet der Problemanalyse, Softwareentwicklung und Teamarbeit. Veranstaltet wird der Wettbewerb von der Association for Computing Machinery (ACM), der Hauptsponsor ist IBM. Die Organisationszentrale befindet sich an der Universität Baylor, während die einzelnen regionalen Vorbewerbe teilweise autonom organisiert und durchgeführt werden.

Geschichte

Die Geschichte des ICPC lässt sich bis auf einen 1970 an der Texas A&M University durchgeführten Programmierwettbewerb zurückverfolgen. Dieser wurde vom Alpha Chapter der Upsilon Pi Epsilon-Vereinigung organisiert. Bis 1977 blieb der Bewerb lokal beschränkt, in diesem Jahr fand er dann erstmals im Rahmen der ACM Computer Science Conference statt. Von 1977 bis 1989 nahmen praktisch nur Teams aus den Vereinigten Staaten und Kanada teil. Seit dem Jahr 1989 befindet sich die Organisationszentrale des Bewerbes an der Baylor University.

Mit der steigenden Anzahl an weltweit regional durchgeführten Vorbewerben (Regionalausscheidungen) stieg die Anzahl an Teilnehmern enorm an. Auch die finanzielle und personelle Unterstützung durch den Sponsor IBM seit 1997 trug zu diesem Anstieg bei. So nahmen im Jahr 1997 noch 840 Teams aus 560 Universitäten teil. Neun Jahre später, beim Bewerb des Jahres 2006, nahmen 6099 Teams von 1756 Universitäten in 82 Nationen teil^[1]. Jährlich steigen die Teilnehmerzahlen zwischen 10 und 20 %.

Regeln des Bewerbes

Der ICPC ist ein Teambewerb. Ein Team besteht aus drei Studenten, die weniger als 5 Jahre an universitärer Ausbildung erhalten haben müssen. Eine Qualifikation in das Finale ist höchstens zweimal möglich.

Während des Wettbewerbes müssen innerhalb von fünf Stunden zwischen acht und zehn Programmieraufgaben gelöst werden. Als Programmiersprachen stehen C, C++ und Java zur Auswahl. Die erstellten Programme werden von den Teilnehmern an einen Server gesandt, der mit speziell entwickelten Testdaten die Funktion der Programme prüft. Die Teams werden über den Ausgang des Tests innerhalb von Minuten über Korrektheit oder Fehler des Programms benachrichtigt.

Gewinner ist das Team mit den meisten gelösten Aufgabenstellungen. Haben mehrere Teams die gleiche Anzahl gelöst, werden diese Teams nach der Geschwindigkeit der Problemlösung gereiht. Dafür werden für jedes Team die Zeitdauern zwischen dem Beginn des Bewerbes und dem Einsenden der korrekten Lösung addiert. Für jedes fehlerhafte Einsenden des Programms werden 20 "Strafminuten" vergeben. Diese werden allerdings nur berücksichtigt, wenn das Problem bis zum Ende des Bewerbes auch tatsächlich gelöst werden kann.^[2]

Die genannten Regeln gelten in dieser Form insbesondere für den Finalbewerb. Die Regeln der regionalen Vorausscheidungen orientieren sich weitgehend an diesen, können im Detail allerdings abweichen.

Im Vergleich zu ähnlichen Programmierwettbewerben, etwa der Internationalen Informatik-Olympiade müssen beim ICPC in kurzer Zeit (fünf Stunden) vergleichsweise viele Beispiele (acht bis zehn) gelöst werden. Zwar arbeiten beim ICPC nicht einzelne Personen, sondern Dreierteams, an der Lösung, diesen wird aber lediglich ein Rechner zur Verfügung gestellt. Um erfolgreich zu sein sind neben den Algorithmen- und Programmierkenntnissen auch Teamfähigkeit gefragt, sowie wie Fähigkeit, unter Zeitdruck exakt arbeiten zu können.

Regionale Ausscheidungen und Weltfinale

Der Wettbewerb wird in mehreren Phasen durchgeführt:

1. Viele Universitäten organisieren lokale Ausscheidungen, um die von ihr entsandte Teilnehmer zu bestimmen.
2. Die erste offizielle Phase sind die regionalen Vorausscheidungen (engl. Regionals). Je nach Regionalbewerb dürften zwei bis maximal drei Teams einer Universität teilnehmen, für das Finale kann sich aber höchstens ein Team pro Universität qualifizieren. Die erstplatzierten Teams aller Regionals qualifizieren sich für den Finalbewerb. Diese Bewerbe finden zu unterschiedlichen Zeitpunkten im Spätherbst statt.
3. Das Weltfinale wird jedes Jahr in einem anderen Land im Frühjahr abgehalten. Zum Finale des Bewerbes 2006, das im März 2007 stattfand, wurden 88 Teams eingeladen.

Einige größere Regionen haben in den letzten Jahren auch sogenannte Superregionals organisiert. Dies sind inoffizielle Zwischenstufen zwischen den Regionals und dem Finale, zu dem die bestplatzierten Teams mehrerer geographisch zusammengehöriger Regionen eingeladen werden. Ein derartiger Bewerb ist für die Zukunft auch für Europa geplant.

Finale 2005

Eröffnungszeremonie 2005

Das Weltfinale 2005 fand am 6. April 2005 im Pudong Shangri-La Hotel in Shanghai, China statt. Es wurde von der Jiaotong-Universität Shanghai organisiert. 4109 Teams von 1582 Universitäten aus 71 Ländern nahmen an den Vorrunden teil, 78 davon wurden zum Finale eingeladen. Das Team der Jiaotong Universität konnte im "Heimspiel" mit acht von zehn gelösten Beispielen auch den Titel erringen, den zweiten dieser Universität.

Finale 2006

Das Finale im Jahr 2006 wurde in San Antonio, Texas veranstaltet und von der Baylor University organisiert. 5606 Teams von 1733 Universitäten in 84 Nationen nahmen an den Vorrunden teil, 83 dieser Teams wurden zum Finale eingeladen. Den Titel konnte das Team der Saratov State University aus Russland erringen, das sechs von acht Beispielen löste.

Finale 2007

Das Weltfinale 2007 wurde vom 12.-16. März 2007 im Hilton Tokio Bay, Tokio, Japan abgehalten. 6099 Teams hatten an den Regionals teilgenommen, 88 davon wurden in das Finale eingeladen. Den Bewerb gewonnen hat die Universität Warschau mit acht von zehn gelösten Aufgaben.

Gewinner

Die Gewinner (World Champions) der Bewerbe seit 1977 sind:

• 2007: Universität Warschau, Polen
• 2006: Staatliche Universität Saratow, Russland
• 2005: Jiaotong-Universität Shanghai, Volksrepublik China
• 2004: St. Petersburg Institute of Fine Mechanics and Optics, Russland
• 2003: Universität Warschau, Polen
• 2002: Jiaotong-Universität Shanghai, China
• 2001: Staatliche Universität Sankt Petersburg, Russland
• 2000: Staatliche Universität Sankt Petersburg, Russland
• 1999: University of Waterloo, Kanada
• 1998: Charles University, Tschechien
• 1997: Harvey Mudd College, Vereinigte Staaten
• 1996: University of California, Berkeley, Vereinigte Staaten
• 1995: Albert-Ludwigs-Universität Freiburg, Deutschland
• 1994: University of Waterloo, Kanada
• 1993: Harvard University, Vereinigte Staaten
• 1992: University of Melbourne, Australien
• 1991: Stanford University, Vereinigte Staaten
• 1990: University of Otago, Neuseeland
• 1989: University of California, Los Angeles, Vereinigte Staaten
• 1988: California Institute of Technology, Vereinigte Staaten
• 1987: Stanford University, Vereinigte Staaten
• 1986: California Institute of Technology, Vereinigte Staaten
• 1985: Stanford University, Vereinigte Staaten
• 1984: Johns Hopkins University, Vereinigte Staaten
• 1983: University of Nebraska, Vereinigte Staaten
• 1982: Baylor University, Vereinigte Staaten
• 1981: University of Missouri–Rolla, Vereinigte Staaten
• 1980: Washington University in St. Louis, Vereinigte Staaten
• 1979: Washington University in St. Louis, Vereinigte Staaten
• 1978: Massachusetts Institute of Technology, Vereinigte Staaten
• 1977: Michigan State University, Vereinigte Staaten

Quellen

1. ↑ ICPC-Factsheet 2006
2. ↑ The Rules of the 2008 ACM-ICPC World Finals

Weblinks

• Offizielle Homepage des ACM-ICPC (engl.)