Zwei Männer sitzen an Schreibtischen, auf denen ein Computer und Papiere verstreut liegen.
Petr Mitrichev (links) und Gennady Korotkevich (rechts), zwei prominente Wettbewerbsprogrammierer während des Yandex Algorithm Cup 2013.

Wettbewerbsprogrammierung , auch Sportprogrammierung genannt, ist ein Denksport, bei dem die Teilnehmer versuchen, gemäß vorgegebener Spezifikationen zu programmieren . Die Wettbewerbe finden üblicherweise über das Internet oder ein lokales Netzwerk statt. Wettbewerbsprogrammierung wird von mehreren multinationalen Software- und Internetunternehmen wie Google [ 1 ] [ 2 ] und Meta [ 3 ] anerkannt und unterstützt .

Bei einem Programmierwettbewerb stellt der Veranstalter den Teilnehmern (deren Anzahl von einigen Dutzend oder sogar Hunderten bis hin zu mehreren Tausend variieren kann) eine Reihe logischer oder mathematischer Probleme , auch bekannt als Rätsel oder Herausforderungen, vor. Die Teilnehmer müssen Computerprogramme schreiben , die diese Probleme lösen können. Die Bewertung basiert hauptsächlich auf der Anzahl der gelösten Probleme und der für die Entwicklung erfolgreicher Lösungen benötigten Zeit, kann aber auch andere Faktoren (Qualität der Ausgabe, Ausführungszeit, Speichernutzung, Programmgröße usw.) berücksichtigen.

Geschichte

Einer der ältesten bekannten Wettbewerbe ist der International Collegiate Programming Contest (ICPC), der in den 1970er Jahren entstand [ 4 ] und in seiner Ausgabe von 2011 bereits 88 Länder umfasste.

Von 1990 bis 1994 veranstalteten Owen Astrachan , Vivek Khera und David Kotz einen der ersten verteilten, internetbasierten Programmierwettbewerbe, der vom ICPC inspiriert war. [ 5 ]

Das Interesse an Wettbewerbsprogrammierung ist seit dem Jahr 2000 enorm gestiegen und zählt mittlerweile Zehntausende von Teilnehmern (siehe Bekannte Wettbewerbe ). Es steht in engem Zusammenhang mit dem Wachstum des Internets, das die Durchführung internationaler Wettbewerbe online ermöglicht und geografische Probleme beseitigt.

Überblick

Ziel des Wettbewerbsprogrammierens ist es, Computerprogramme zu entwickeln, die vorgegebene Probleme lösen können. Die meisten Aufgaben in Programmierwettbewerben sind mathematischer oder logischer Natur. Typische Aufgaben dieser Art lassen sich einer der folgenden Kategorien zuordnen: Kombinatorik , Zahlentheorie , Graphentheorie , algorithmische Spieltheorie , algorithmische Geometrie , Stringanalyse , diskrete Mathematik und Datenstrukturen . [ 6 ] Auch Probleme aus den Bereichen Constraint-Programmierung und künstliche Intelligenz sind in bestimmten Wettbewerben beliebt.

Unabhängig von der Problemkategorie lässt sich der Lösungsprozess in zwei Hauptschritte unterteilen: die Entwicklung eines effizienten Algorithmus und dessen Implementierung in einer geeigneten Programmiersprache (die zulässigen Programmiersprachen variieren je nach Wettbewerb). Dies sind die beiden am häufigsten geprüften Fähigkeiten in Programmierwettbewerben.

In den meisten Wettbewerben erfolgt die Bewertung automatisch durch Host-Rechner, sogenannte „Judges“. Jede von einem Teilnehmer eingereichte Lösung wird auf dem Judge anhand einer Reihe (meist geheimer) Testfälle ausgeführt. Normalerweise verwenden Wettbewerbsaufgaben ein Alles-oder-Nichts-Bewertungssystem. Das bedeutet, dass eine Lösung nur dann akzeptiert wird, wenn sie bei allen vom Judge ausgeführten Testfällen zufriedenstellende Ergebnisse liefert; andernfalls wird sie abgelehnt. Einige Wettbewerbsaufgaben erlauben jedoch eine Teilwertung, abhängig von der Anzahl der bestandenen Testfälle, der Qualität der Ergebnisse oder anderen festgelegten Kriterien. Bei manchen Wettbewerben muss der Teilnehmer lediglich die Ausgabe zu den vorgegebenen Eingabedaten einreichen; in diesem Fall muss der Judge nur die eingereichten Ausgabedaten analysieren.

Online-Richter sind Online-Umgebungen, in denen Tests stattfinden. Online-Richter führen Ranglisten, die die Benutzer mit der größten Anzahl akzeptierter Lösungen und/oder der kürzesten Ausführungszeit für ein bestimmtes Problem auflisten. [ 7 ]

Bemerkenswerte Wettbewerbe

Algorithmenwettbewerbe

Name des Wettbewerbs [ 8 ]Organisatoren Publikum Beschreibung Anzahl der Teilnehmer
Google Code Jam (GCJ) Googleoffen Jährlicher Wettbewerb, der von 2003 bis zu seiner Einstellung im Jahr 2023 von Google organisiert und gesponsert wurde . [ 9 ]32.702 (2022) [ 10 ]
Internationaler Hochschul-Programmierwettbewerb (ICPC) [ 11 ]ICPC-Stiftung Universitätsstudenten Der Teamwettbewerb für Universitätsstudenten besteht aus zahlreichen regionalen Runden, die in einem jährlich stattfindenden Weltfinale gipfeln. Die Teams setzen sich aus drei Studenten derselben Universität zusammen und dürfen nur einen Computer benutzen. [ 12 ]50.000+ (2022) [ 13 ]
Internationale Informatik-Olympiade (IOI) IOI Schüler vor dem Universitätsstudium Internationaler Wettbewerb für Schüler der Sekundarstufe. Findet seit 1989 jährlich statt. Jedes Land kann maximal 4 Teilnehmer entsenden. 349 aus 88 Ländern (2022) [ 14 ]
Meta Hacker Cup (ehemals Facebook Hacker Cup ) Meta-Plattformenoffen Jährlicher Wettbewerb, der seit 2011 stattfindet. Organisiert und gesponsert von Meta (ehemals Facebook ). 27.604 (2022) [ 15 ]
Topcoder Open (TCO) Topcoderoffen Jährlicher Algorithmenwettbewerb, der von 2001 bis zu seiner Einstellung im Jahr 2023 stattfand [ 16 ].

Die meisten der oben genannten Wettbewerbe sind in mehrere Runden unterteilt. Sie beginnen üblicherweise mit Online-Runden und enden mit dem Finale vor Ort. Die Besten bei IOI und ICPC erhalten Gold-, Silber- und Bronzemedaillen. Bei den anderen Wettbewerben werden Geldpreise an die Erstplatzierten vergeben. Die Wettbewerbe wecken zudem das Interesse von Personalverantwortlichen zahlreicher Software- und Internetunternehmen, die den Teilnehmern häufig potenzielle Stellenangebote unterbreiten.

Künstliche Intelligenz und maschinelles Lernen

  • Die Liste ist möglicherweise unvollständig.
Name Hauptorganisatoren Beschreibung Status
KaggleGoogle Plattform und Online-Community für Wettbewerbe in den Bereichen Data Science, maschinelles Lernen und mathematische Optimierung. Aktiv
KI-Herausforderung Universität von Waterloo Internationaler Programmierwettbewerb für künstliche Intelligenz, der von 2009 bis 2011 stattfand. Inaktiv
Halite KI-ProgrammierwettbewerbTwo Sigma, Cornell Tech Computerprogrammierwettbewerb, bei dem die Teilnehmer Bots in der gewünschten Programmiersprache bauen, um auf einem zweidimensionalen Schlachtfeld gegeneinander anzutreten. Unbekannt
Russischer KI-PokalMail.Ru-Gruppe, My.com Jährlicher Programmierwettbewerb für künstliche Intelligenz. Unbekannt

Wettbewerbe mit Schwerpunkt auf Open-Source-Technologien

  • Die Liste ist möglicherweise unvollständig.
Wettbewerbsname Hauptsponsor Beschreibung Läuft seit Übliche Zeit Nächster Antragszyklus Status
Multiagenten-ProgrammierwettbewerbTechnische Universität Clausthal in Verbindung mit agentenorientierten Workshops Jährlicher internationaler Programmierwettbewerb zur Förderung der Forschung im Bereich der Entwicklung und Programmierung von Multiagentensystemen . 2005 September September 2011 Aktiv
Google Summer of CodeGoogle Inc.Ein jährliches Programm, in dem Google Stipendien an Hunderte von Studenten vergibt, die im Sommer ein angefordertes freies Software-/Open-Source-Programmierprojekt erfolgreich abschließen. 2005 März-August 23. März – 3. April Aktiv
Google-Wettbewerb mit hoher OffenheitGoogle Inc. Ein von Google in den Jahren 2007–08 veranstalteter Wettbewerb, der sich an Schüler der Oberstufe richtete. Ziel des Wettbewerbs war es, Schüler der Oberstufe zur Teilnahme an Open-Source-Projekten zu animieren. 2007 Nov.-Feb. Unbekannt Unbekannt

Online-Plattformen

Die weltweite Programmiergemeinschaft hat zahlreiche Internetressourcen für das Wettbewerbsprogrammieren entwickelt und pflegt diese. Sie bieten eigenständige Wettbewerbe mit oder ohne kleinere Preisgelder an. Die Teilnehmer erhalten in der Regel eine Bewertung basierend auf ihrer Leistung in diesen Wettbewerben. Die Archive vergangener Aufgaben sind beliebte Trainingsressourcen für das Wettbewerbsprogrammieren. Mehrere Organisationen veranstalten regelmäßig Programmierwettbewerbe. Dazu gehören:

Name Beschreibung
Aufkommen des CodesEin jährlicher Programmierwettbewerb findet während der Adventszeit statt . Bis einschließlich Weihnachten werden täglich zwei neue Rätsel veröffentlicht. Das zweite Rätsel eines jeden Tages ist erst nach Lösung des ersten Teils gesperrt und baut in der Regel logisch darauf auf. Es gibt sowohl globale als auch private Ranglisten für jedes Jahr, in denen die Platzierung davon abhängt, wer das Rätsel als Erster löst.
CodeChef [ 17 ] [ 18 ]Die von Unacademy betriebene Plattform bietet monatlich einen dreitägigen Wettbewerb sowie zwei kürzere Wettbewerbe (einen im IOI-Stil namens Lunchtime und einen im ICPC-Stil namens Cook-Off) an und stellt Bildungseinrichtungen kostenlos eine Plattform zur Verfügung. Die beiden Erstplatzierten des Hauptwettbewerbs gewinnen Geldpreise, die zehn Besten weltweit erhalten ein T-Shirt.
Codeforces [ 19 ] [ 17 ]Die von der ITMO-Universität betriebene russische Plattform bietet regelmäßig (bis zu zwei pro Woche) zwei- bis dreistündige Wettbewerbe (verfügbar in Englisch und Russisch). Nutzer können außerdem an Wettbewerben anderer Nutzer im Bereich „Gym“ teilnehmen, zusätzliche Testfälle einreichen, um die Lösungen anderer Teilnehmer zu „hacken“, Blogs zum Austausch von Techniken verfassen und den Quellcode der Lösungen anderer Nutzer einsehen. Teilnehmer mit einer ausreichend hohen Punktzahl erhalten zusätzliche Funktionen, wie das Hinzufügen von Tags zu Aufgaben und das Einreichen von Aufgabensätzen für offizielle Wettbewerbe.
CodinGameRätsel (steigender Schwierigkeitsgrad), Code-Golf . Veranstaltet regelmäßig Online-Wettbewerbe (Programmierspiele und Programmierherausforderungen).
CodewarsEine Community-basierte Plattform mit integrierter Online-Entwicklungsumgebung, auf der Nutzer Katas – kleine Programmieraufgaben – in verschiedensten Programmiersprachen lösen. Durch das Abschließen von Aufgaben und das Erstellen neuer Aufgaben sammeln die Nutzer Ränge und erhalten Auszeichnungen. Der Fokus liegt auf dem Lernen durch Übung und gegenseitiges Feedback. Lösungen und Diskussionen stehen nach jeder abgeschlossenen Aufgabe zur Verfügung.
HackerEarth [ 17 ]Ein in Bangalore , Indien, ansässiges Unternehmen, das eine wettbewerbsähnliche Online-Umgebung anbietet und Lösungen zur Personalbeurteilung bereitstellen möchte.
HackerRankHackerRank bietet Programmieraufgaben in verschiedenen Bereichen der Informatik an. Außerdem veranstaltet die Plattform jährlich Codesprints, die Programmierer und Startups aus dem Silicon Valley miteinander vernetzen.
LeetCodeLeetCode bietet über 2.300 Aufgaben zu vielen verschiedenen Programmierkonzepten und veranstaltet wöchentliche und zweiwöchentliche Wettbewerbe. Die Programmieraufgaben sind auf Englisch und Chinesisch verfügbar.
Projekt Euler [ 18 ]Eine große Sammlung von Rechenaufgaben (d. h. nicht direkt mit Programmierung verbunden, aber oft mit Programmierkenntnissen zur Lösung). Anders als bei anderen Online-Lösungsplattformen ist kein Quellcode erforderlich. Jede Aufgabe verlangt lediglich eine numerische Antwort (die in der Regel zu groß ist, um sie zu erraten oder manuell zu berechnen), sodass die Nutzer beliebige Lösungsmethoden verwenden können, einschließlich der Wahl einer Programmiersprache.
SPOJ [ 17 ]Das polnische Online-Bewertungssystem bietet viele Übungsaufgaben und dient anderen Organisatoren als Plattform für die Ausrichtung ihrer Programmierwettbewerbe.
Topcoder [ 19 ] [ 17 ]Ein US-amerikanisches Unternehmen und Ressourcenanbieter organisiert Wettbewerbe und vermittelt zudem industrielle Problemstellungen als eine Art Freelance-Auftrag. Jährlich veranstaltet es Dutzende von Kurzwettbewerben und mehrere Langzeitwettbewerbe („Marathons“). Besonderheit: Die Teilnehmer haben die Möglichkeit, die Lösungen der anderen nach der Programmierphase und vor dem finalen automatisierten Test (der sogenannten „Challenge-Phase“) zu überprüfen.
UVa Online Judge [ 19 ] [ 17 ]Enthält über 4.500 Übungsaufgaben. Veranstaltet regelmäßig Online-Wettbewerbe. Die Webseite wurde 1995 gegründet und ist damit eine der ältesten ihrer Art.

Vorteile und Kritik

Die Teilnahme an Programmierwettbewerben kann die Begeisterung von Studierenden für ein Informatikstudium steigern . Die in Wettbewerben wie dem ICPC erworbenen Fähigkeiten verbessern zudem die Karrierechancen, da sie beim Bestehen der technischen Vorstellungsgespräche helfen, in denen Kandidaten häufig komplexe Programmier- und Algorithmenprobleme spontan lösen müssen. [ 19 ] [ 20 ]

Es gab auch Kritik am Wettbewerbsprogrammieren, insbesondere von professionellen Softwareentwicklern . [ 21 ] Ein kritischer Punkt ist, dass viele schnelllebige Programmierwettbewerbe den Teilnehmern schlechte Programmiergewohnheiten und einen ungeeigneten Codestil vermitteln (wie den unnötigen Einsatz von Makros , fehlende OOP- Abstraktion und Kommentare, die Verwendung kurzer Variablennamen usw.). [ 22 ] [ 21 ] Da Programmierwettbewerbe wie ICPC und IOI nur kleine algorithmische Aufgaben mit relativ kurzen Lösungen bieten, vermitteln sie nicht unbedingt gute Softwareentwicklungskenntnisse und -praktiken, da reale Softwareprojekte typischerweise viele Tausend Codezeilen umfassen und von großen Teams über lange Zeiträume entwickelt werden. [ 21 ] Peter Norvig stellte fest, dass die verfügbaren Daten darauf hindeuten, dass der Gewinn von Programmierwettbewerben negativ mit der Leistung eines Programmierers bei Google korreliert (obwohl Wettbewerbsgewinner höhere Chancen auf eine Anstellung hatten). [ 23 ] Norvig gab später an, dass diese Korrelation bei einem kleinen Datensatz beobachtet wurde , aber nach der Untersuchung eines größeren Datensatzes nicht bestätigt werden konnte. [ 24 ]

Eine andere Ansicht besagt, dass hochkarätige Programmierer ihre Zeit nicht mit übermäßigem Wettbewerb durch das Lösen von Problemen mit bekannten Lösungen verschwenden, sondern stattdessen in die Lösung realer Probleme investieren sollten. [ 21 ]

Literatur

  • Halim, S., Halim, F. (2013). Competitive Programming 3: The New Lower Bound of Programming Contests . Lulu.
  • Laaksonen, A. (2017). Leitfaden zum Wettbewerbsprogrammieren (Grundlagen der Informatik). Cham: Springer International Publishing.
  • Xu, X. (2020) Die Entwicklung, der Aufstieg und der Niedergang von Olympic in Informatics . Online veröffentlicht .
  • Kostka, B. (2021). Sportprogrammierung in der Praxis. Universität Breslau.

Siehe auch

Referenzen

  1. ^ „Google Code Jam“ . google.com . Archiviert vom Original am 31. Mai 2023. Abgerufen am 20. Februar 2016 .
  2. ^ „TCO12 Sponsor: Google - TCO 12“ . topcoder.com . Archiviert vom Original am 16. Februar 2012.
  3. ^ „Facebook Hacker Cup“ . Facebook . Abgerufen am 20. Februar 2016 .
  4. ^ Li, Yujia; Choi, David; Chung, Junyoung; Kushman, Nate; Schrittwieser, Julian; Leblond, Rémi; Eccles, Tom; Keeling, James; Gimeno, Felix; Lago, Agustin Dal; Hubert, Thomas; Choy, Peter; d'Autume, Cyprien de Masson; Babuschkin, Igor; Chen, Xinyun (9. Dezember 2022). „Wettbewerbsfähige Codegenerierung mit AlphaCode“. Science . 378 (6624): 1092–1097 . arXiv : 2203.07814 . Bibcode : 2022Sci...378.1092L . doi : 10.1126/science.abq1158 . ISSN 0036-8075 . PMID 36480631 .  
  5. ^ Khera, Vivek; Astrachan, Owen; Kotz, David (1993). „The internet programming contest“ (PDF) . ACM SIGCSE Bulletin . 25 (1): 48–52 . doi : 10.1145/169073.169105 . ISSN 0097-8418 . Archiviert vom Original (PDF) am 8. August 2017. Abgerufen am 10. März 2020 . 
  6. ^ Pak, Igor. „Algorithmen“ . Math 182. University of California, Los Angeles . Abgerufen am 31. März 2024 .
  7. ^ Programmierherausforderungen (Skiena & Revilla) ISBN 0387001638ISBN​ 978-0387001630
  8. ^ Kostka, Bartosz (2021). Sportprogrammierung in der Praxis (PDF) . Universität Breslau.
  9. ^ „Feiern Sie Googles Programmierwettbewerbe mit einer finalen Runde voller Programmierspaß“ . Google Developers Blog . Google . Abgerufen am 28. Februar 2023 .
  10. ^ „Code Jam – Googles Programmierwettbewerbe“ . Programmierwettbewerbe . Archiviert vom Original am 27. Juni 2023. Abgerufen am 26. Februar 2023 .
  11. ^ "ICPC" . icpc.global . Abgerufen am 26. Februar 2023 .
  12. ^ „Programmierumgebung – ICPC-Dokumente“ . Abgerufen am 15. Februar 2024 .
  13. ^ "ICPC" . icpc.global . Abgerufen am 26. Februar 2023 .
  14. ^ „Olympiade“ . stats.ioinformatics.org . Abgerufen am 26. Februar 2023 .
  15. ^ „Meta Hacker Cup – 2022 – Qualifikationsrunde“ . www.facebook.com . Abgerufen am 26. Februar 2023 .
  16. ^ „FAQ – Topcoder Community Town Hall mit Doug Hanson, CEO von Topcoder“ . Topcoder . Abgerufen am 28. Februar 2023 .
  17. ^ a b c d e f Luigi, William Di; Farina, Gabriele; Laura, Luigi; Nanni, Umberto; Temperini, Marco; Versari, Luca (2016). „oii-web: ein interaktives Online-Programmierungssystem oii-web: ein interaktives Online-Programmierwettbewerb-Trainingssystem“ (PDF) . Olympiaden in der Informatik . 10 : 207–222 . doi : 10.15388/ioi.2016.13 . S2CID 6877554 . 
  18. ^ a b Combéfis, Sébastien; Wautelet, Jérémy (2014). „Programmiertraining und Informatikunterricht durch Online-Wettbewerbe“ (PDF) . Informatik-Olympiaden . 8 : 21–34 .
  19. ^ a b c d Bloomfield, Aaron; Sotomayor, Borja. „A Programming Contest Strategy Guide“ (PDF) . SIGCSE '16: Proceedings of the 47th ACM Technical Symposium on Computing Science Education .
  20. ^ Jackson, Dean (1. Dezember 2013). „Das technische Vorstellungsgespräch bei Google. Wie Sie Ihren Traumjob bekommen“ (PDF) . XRDS: Crossroads, das ACM-Magazin für Studenten . 20 (2): 12–14 . doi : 10.1145/2539270 . S2CID 27549057 . 
  21. ^ a b c d Smith, Duncan (2. Dezember 2015). "Die Debatte um kompetitives Programmieren" .
  22. ^ Halim, Steven. „CS3233 - Competitive Programming“ . NUS School of Computing .
  23. ^ „Gewinnen bei Programmierwettbewerben wirkt sich negativ auf die berufliche Leistung aus . “ YouTube . 5. April 2015.
  24. ^ „HN-Diskussion über den Zusammenhang zwischen Arbeitsleistung und Wettbewerbsprogrammierung“ . Dezember 2020.