Konkurenční programování - Competitive programming

Petr Mitrichev (vlevo) a Gennadij Korotkevič (vpravo), dva prominentní konkurenční programátoři během soutěže.

Konkurenční programování je mysli sport obvykle držen nad Internet nebo a lokální síť, zahrnující účastníky, kteří se o to snaží program podle poskytnutých specifikací. Soutěžící jsou označováni jako sportovní programátoři. Konkurenční programování uznává a podporuje několik nadnárodních softwarových a internetových společností, například Google[1][2] a Facebook.[3] Existuje několik organizací, které pravidelně pořádají programátorské soutěže.

Soutěž v programování obvykle zahrnuje hostitele, který předloží soubor logický nebo matematické úlohy, také známý jako hádanky, soutěžícím (jejichž počet se může lišit od desítek do několika tisíc) a soutěžící jsou povinni psát počítačové programy schopný vyřešit každý problém. Posuzování je založeno hlavně na počtu vyřešených problémů a času stráveném psaní úspěšných řešení, ale může zahrnovat i další faktory (kvalita vytvořeného výstupu, doba provedení, velikost programu atd.)

Dějiny

Jedna z nejstarších známých soutěží je ICPC který vznikl v 70. letech a ve svém vydání z roku 2011 se rozrostl o 88 zemí.

Od roku 1990 do roku 1994 Owen Astrachan Vivek Khera a David Kotz uspořádali jednu z prvních distribuovaných internetových programovacích soutěží inspirovaných ICPC.[4]

Zájem o konkurenční programování značně vzrostl[vyčíslit ] od roku 2000 a je silně spojen s růstem internetu, který usnadňuje pořádání mezinárodních soutěží online a eliminuje geografické problémy.

Přehled

Cílem konkurenčního programování je psát zdrojový kód počítačových programů, které jsou schopné řešit dané problémy. Drtivá většina problémů vyskytujících se v programovacích soutěžích je matematické nebo logické povahy. Typické takové úkoly patří do jedné z následujících kategorií: kombinatorika, teorie čísel, teorie grafů, teorie algoritmických her, výpočetní geometrie, analýza řetězce a datové struktury. Problémy související s umělá inteligence jsou také populární v určitých soutěžích.

Bez ohledu na kategorii problému lze proces řešení problému rozdělit do dvou širokých kroků: vybudování efektivního algoritmus a implementaci algoritmu do vhodného programovací jazyk (sada povolených programovacích jazyků se liší od soutěže k soutěži). Toto jsou dvě nejčastěji testované dovednosti v programovacích soutěžích.

Ve většině soutěží se hodnocení provádí automaticky na hostitelských počítačích, běžně známých jako soudci. Každé řešení předložené soutěžícím je spuštěno na soudci proti souboru (obvykle tajných) testovacích případů. Za normálních okolností mají soutěžní problémy systém označování „vše nebo nikdo“, což znamená, že řešení je „přijato“ pouze v případě, že poskytuje uspokojivé výsledky ve všech testovacích případech prováděných soudcem a je odmítnuto jinak. Některé problémy se soutěžemi však mohou umožnit částečné bodování, v závislosti na počtu absolvovaných testovacích případů, kvalitě výsledků nebo některých dalších specifikovaných kritériích. Některé další soutěže vyžadují pouze to, aby soutěžící předložil výstup odpovídající zadaným vstupním údajům, v takovém případě musí soudce pouze analyzovat předložená výstupní data.

Online soudci jsou online prostředí, ve kterých probíhá testování. Online soudci mají seznamy, které ukazují uživatele s největším počtem přijatých řešení a / nebo s nejkratší dobou provedení pro konkrétní problém.[5]

Pozoruhodné soutěže

Existují dva typy soutěžních formátů: krátkodobé a dlouhodobé. Každé kolo krátkodobých soutěží trvá 1 až 5 hodin. Dlouhodobé soutěže mohou trvat několik dní až několik měsíců.

Krátkodobý

Ve většině výše uvedených soutěží je počet soutěžících poměrně velký, a proto se soutěže obvykle organizují v několika kolech. Obvykle vyžadují online účast ve všech kolech kromě posledního, což vyžaduje účast na místě. Zvláštní výjimkou je IEEEXtreme, což je každoroční 24hodinová virtuální programovací soutěž. Nejlepší umělci IOI a ACM-ICPC dostávají zlaté, stříbrné a bronzové medaile, zatímco v ostatních soutěžích se nejlepším hráčům udělují peněžní ceny. Také zasažení nejlepších míst v bodovacích tabulkách takových soutěží může přilákat zájem náborářů ze softwarových a internetových společností.

Dlouhodobý

Umělá inteligence a strojové učení

  • Kaggle - soutěže strojového učení.
  • CodeCup - soutěž deskových her v oblasti umělé inteligence, která se koná každoročně od roku 2003. Pravidla hry budou zveřejněna v září a závěrečný turnaj se koná v lednu.[12][13][14]
  • Google AI výzva - dvouleté soutěže pro studenty, které proběhly v letech 2009 až 2011
  • Halit[15] - výzva k programování umělé inteligence sponzorovaná společností Two Sigma, Cornell Tech,[16] a Google[17]
  • Ruský pohár AI otevřená soutěž v programování umělé inteligence

Soutěže zaměřené na technologie open source

  • Seznam může být neúplný
Název soutěžeHlavní sponzorPopisOd té doby běžíObvyklý časDalší aplikační cyklusPostavení
Programovací soutěž pro více agentůClausthal University of Technology ve spolupráci s agenturně zaměřenými workshopyKaždoroční mezinárodní programovací soutěž na podporu výzkumu v oblasti multiagentní systém vývoj a programování.2005ZáříZáří 2011Aktivní
Google Summer of CodeGoogle Inc.Každoroční program, v němž ceny Google udělují stovkám studentů, kteří během léta úspěšně dokončí požadovaný projekt svobodného softwaru / kódování open-source.2005Březen-srpen23. března - 3. dubnaAktivní
Vysoce otevřená účastnická soutěž GoogleGoogle Inc.Soutěž pořádaná společností Google v letech 2007–8 zaměřená na studenty středních škol. Cílem soutěže je povzbudit studenty středních škol k účasti na projektech open source.2007Listopad-únorNeznámýNeznámý

Online soutěže a tréninkové zdroje

Programátorská komunita po celém světě vytvořila a udržovala několik internetových zdrojů věnovaných konkurenčnímu programování. Nabízejí samostatné soutěže s menšími cenami nebo bez nich. Také minulé archivy problémů jsou oblíbeným zdrojem pro školení v konkurenčním programování. Tyto zahrnují:

názevPopiswebová stránka
CodeChef[18][10]Každý měsíc pořádá soutěž o deset dní a několik krátkých soutěží (jeden IOI ve stylu Luchtime a druhý ACM ICPC ve stylu Cook-Off) a poskytuje vzdělávací platformu zdarma vzdělávacím institucím. První dva výherci dlouhé soutěže vyhrávají peněžní ceny, zatímco 10 nejlepších globálních získává tričko.www.codechef.com
CodeCupKaždoroční mezinárodní desková hra AI programovací soutěž pořádaná nizozemskou olympiádou v informatice od roku 2003.[13][14]kodér.nl
Codeforces[19][18]Ruský zdroj, udržovaný Univerzita ITMO, který většinou pořádá časté (až dvě za týden) krátké soutěže. Speciální funkce: všechna řešení jsou otevřený zdroj, schopnost kontrolovat správnost řešení ostatních soutěžících během „hackerské fáze“, virtuálních soutěží, školení atd.kodexy.com
CodinGameHádanky (rostoucí obtížnost), kód golf. Pořádá pravidelné online soutěže (AI výzvy, optimalizační problémy ).www.codingame.com
Hacker Země[18]Bangalore, Indie založená společnost poskytující online soutěže jako prostředí zaměřené na poskytování řešení hodnocení náboru.www.hackerearth.com
HackerRankHackerRank nabízí problémy s programováním v různých doménách informatiky. Také hostí každoroční Codesprints, které pomáhají propojit kodéry a startupy v Silicon Valley.hackerrank.com
Projekt Euler[10]Velká sbírka výpočetních matematických úloh (tj. Nesouvisí přímo s programováním, ale často vyžaduje řešení programovacích dovedností).projecteuler.síť
Topcoder[19][18]Zdroj a společnost v USA, která organizuje soutěže a také poskytuje průmyslové problémy jako druh práce na volné noze; každoročně nabízí desítky krátkých soutěží a několik dlouhých („maratonů“). Specifická vlastnost - účastníci mají možnost zkontrolovat správnost řešení ostatních soutěžících po fázi kódování a před závěrečným automatickým testováním (tzv. „Výzva fáze“).www.topcoder.com
UVa Online soudce[19][18]Obsahuje přes 4 500 problémů s procvičováním. Pořádá pravidelné online soutěže. Byl otevřen v roce 1995 a je to jeden z nejstarších takových webů.onlinejudge.org
SPOJ[18]polština online soudce systém, který pro trénink přináší mnoho problémů a poskytuje platformu pro další organizátory pro pořádání jejich programových soutěží.www.spoj.com
Otevřete KattisVeřejná verze systému pro správu soutěží Kattis s archivem více než 2600 problémů.[19] Kattis byl vyvinut za účelem podpory kurzů informatiky, ale také se používá k pořádání prestižních soutěží, jako je světové finále ICPC.[20]otevřeno.kattis.com
AtCoderSpolečnost AtCoder se sídlem v Japonsku nabízí týdenní online soutěže v programování. Soutěže jsou nabízeny v japonštině a angličtině.

Od roku 2020 je to jedna z nejpopulárnějších platforem svého druhu.[21]

kodér.jp
Karibik online soudceŠpanělský zdroj, udržovaný University of Information Science.[22] Obsahuje přes 3 000 problémů s procvičováním. Také pořádá pravidelné online soutěže.coj.uci.cu

Výhody a kritika

Účast v programovacích soutěžích může zvýšit nadšení studentů počítačová věda studie. Dovednosti získané v programovacích soutěžích podobných ICPC také zlepšují kariérní vyhlídky, protože pomáhají absolvovat „technické pohovory“, které od kandidátů často vyžadují řešení složitých programovacích a algoritmických problémů na místě.[19]

Vyskytla se také kritika konkurenčního programování, zejména od profesionálních vývojářů softwaru.[23] Jedním z kritických bodů je, že mnoho rychlých programovacích soutěží učí konkurenty špatným programovacím návykům a stylu kódu (jako je zbytečné používání maker, nedostatek abstrakce a komentářů OOP, používání krátkých názvů proměnných atd.).[24][23] Také tím, že programovací soutěže jako ICPC a IOI nemusí nabízet pouze malé algoritmické hádanky s relativně krátkými řešeními, nemusí nutně učit dobré dovednosti a postupy v oblasti softwarového inženýrství, protože skutečné softwarové projekty mají obvykle mnoho tisíc řádky kódu a jsou vyvíjeny velkými týmy po dlouhou dobu.[23] Peter Norvig uvedl, že na základě dostupných údajů je vítězem soutěží v programování negativně korelován s výkonem programátora v jeho práci v Google (i když vítězové soutěže měli vyšší šanci na přijetí).[25]

Dalším sentimentem je, že spíše než „plýtvat“ časem nadměrným soupeřením řešením problémů se známými řešeními, měli by vysoce postavení programátoři raději investovat svůj čas do řešení problémů v reálném světě.[23]

Literatura

  • Halim, S., Halim, F. (2013). Competitive Programming 3: The New Lower Bound of Programming Contests. Svůdná žena.
  • Laaksonen, A. (2017). Průvodce konkurenčním programováním (Bakalářská témata z informatiky). Cham: Springer International Publishing.

Viz také

Reference

  1. ^ „Google Code Jam“. google.com. Citováno 2016-02-20.
  2. ^ „Sponzor TCO12: Google - TCO 12“. topcoder.com. Archivovány od originál 16. února 2012.
  3. ^ „Facebook Hacker Cup“. Facebook. Citováno 2016-02-20.
  4. ^ Khera, Vivek; Astrachan, Owen; Kotz, David (1993). „Soutěž o programování na internetu“ (PDF). Bulletin ACM SIGCSE. 25 (1): 48–52. doi:10.1145/169073.169105. ISSN  0097-8418.
  5. ^ Programovací výzvy (Skiena a Revilla) ISBN  0387001638, ISBN  978-0387001630
  6. ^ „CodeChef Měsíční soutěže“.
  7. ^ „Programátoři z celého světa soutěží na CodeChef SnackDown - ExchangeMedia“.
  8. ^ „Soutěže Codeforces“. Citováno 2018-10-12.
  9. ^ „Programovací problémy a soutěže :: HackerRank“. HackerRank. Citováno 2016-02-20.
  10. ^ A b C Combéfis, Sébastien; Wautelet, Jérémy (2014). „Programování školení a výuka informatiky prostřednictvím online soutěží“ (PDF). Olympiády v informatice. 8: 21–34.
  11. ^ „Programovací problémy a soutěže :: HackerRank“. HackerRank. Citováno 2016-02-20.
  12. ^ "CodeCup". www.codecup.nl.
  13. ^ A b Lasse Hakulinen. Průzkum v informatických soutěžích: Rozvíjení úkolů - Olympiads in Informatics, 2011, roč. 5, 12–25.
  14. ^ A b Wevers, Lesley (2014). „Hledání stromu Monte-Carlo pro Poly-Y“ (PDF). University of Twente. Archivovány od originál (PDF) dne 13. dubna 2017. Citováno 16. září 2018.
  15. ^ „Výzva k programování umělé inteligence Halite“. www.halite.io.
  16. ^ „Společnost Two Sigma ohlašuje veřejné spuštění Halite“. tech.cornell.edu.
  17. ^ „Halite pomáhá studentům a vývojářům soutěžit o lepší AI na Google Cloud Platform“.
  18. ^ A b C d E F Luigi, William Di; Farina, Gabriele; Laura, Luigi; Nanni, Umberto; Temperini, Marco; Versari, Luca (2016). „oii-web: interaktivní online programování oii-web: interaktivní online programovací soutěžní vzdělávací program“ (PDF). Olympiády v informatice. 10: 207–222.
  19. ^ A b C d E Bloomfield, Aaron; Sotomayor, Borja. „Průvodce strategií v soutěži o programování“ (PDF). SIGCSE '16: Proceedings of the 47th ACM Technical Symposium on Computing Science Education.
  20. ^ Enström, E .; Kreitz, G .; Niemelä, F .; Söderman, P .; Kann, V. (2011). „Pět let s Kattisem - používání automatizovaného systému hodnocení ve výuce“ (PDF). Konference IEEE Frontiers in Education.
  21. ^ Mirzayanov, Mike; Pavlova, Oksana; Mavrin, Pavel; Melnikov, Roman; Plotnikov, Andrew; Parfenov, Vladimir; Stankevich, Andrew (2020). „Codeforces jako vzdělávací platforma pro učení programování v digitalizaci“ (PDF). Olympiády v informatice. 14. ISSN  1822-7732.
  22. ^ „About | Caribbean Online Judge“. coj.uci.cu. Citováno 2020-06-18.
  23. ^ A b C d Smith, Duncan (2. prosince 2015). „Diskuse o konkurenčním programování“.
  24. ^ Halim, Steven. „CS3233 - konkurenční programování“. Škola výpočetní techniky NUS.
  25. ^ „Vítězství v programovacích soutěžích je negativním faktorem dobré práce“. 5. dubna 2015.

externí odkazy

Open-source projekt pro pořádání soutěží