Konkurenční programování - Competitive programming

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

Soutěžní programování je myšlenkový sport, který se obvykle pořádá přes internet nebo místní síť a zahrnuje účastníky, kteří se snaží programovat podle poskytnutých specifikací. Soutěžící jsou označováni jako sportovní programátoři . Konkurenční programování je uznáváno a podporováno několika nadnárodními softwarovými a internetovými společnostmi, jako jsou Google a Facebook .

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

Dějiny

Jednou z nejstarších známých soutěží je ICPC , která vznikla v 70. letech a v roce 2011 se rozrostla na 88 zemí.

V letech 1990 až 1994 organizovali Owen Astrachan , Vivek Khera a David Kotz jednu z prvních distribuovaných, internetových programovacích soutěží inspirovaných ICPC.

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

Přehled

Cílem konkurenčního programování je napsat zdrojový kód počítačových programů, které jsou schopny řešit zadané problémy. Naprostá většina problémů, které se objevují v programátorských soutěžích, má matematický nebo logický charakter. Typické takové úlohy patří do jedné z následujících kategorií: kombinatorika , teorie čísel , teorie grafů , algoritmická teorie her , výpočetní geometrie , řetězcová analýza a datové struktury . Problémy související s omezovacím programováním a umělou inteligencí 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ů: sestavení efektivního algoritmu a implementace algoritmu ve vhodném programovacím jazyce (množina povolených programovacích jazyků se liší soutěž od soutěže). To jsou dvě nejčastěji testované dovednosti v programátorských soutěžích.

Ve většině soutěží je posuzování prováděno automaticky hostitelskými stroji, běžně známými jako rozhodčí. Každé řešení předložené soutěžícím je posuzováno soudcem proti souboru (obvykle tajných) testovacích případů. Normálně mají soutěžní problémy systém známkování všechno nebo žádné, 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 jinak je zamítnuto. Některé problémy se soutěžemi však mohou umožnit částečné bodování v závislosti na počtu úspěšných testovacích případů, kvalitě výsledků nebo některých dalších specifikovaných kritériích. Některé jiné soutěže vyžadují pouze to, aby soutěžící předložil výstup odpovídající daným vstupním datům, v takovém případě musí rozhodčí pouze analyzovat zaslaná výstupní data.

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

Pozoruhodné soutěže

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

Krátkodobý

• International Collegiate Programming Contest (ICPC) – jedna z nejstarších soutěží, pro studenty vysokých škol ve skupinách po 3 lidech
• Mezinárodní olympiáda v informatice (IOI) – jedna z nejstarších soutěží pro středoškolské studenty
• American Computer Science League (ACSL) – počítačová soutěž s písemnou a programovací částí, pro studenty středních a vysokých škol
• CodeChef – soutěž pořádaná od roku 2009, každý měsíc se konají tři soutěže a každoroční soutěž CodeChef SnackDown
• Codeforces Round – obvykle dvouhodinová soutěž, která se koná každý týden
• Facebook Hacker Cup – soutěž pořádaná od roku 2011, kterou zajišťuje a sponzoruje Facebook
• HackerRank – několik soutěží
• Gridwars – čtyři soutěže pořádané v letech 2003 až 2004.
• Google Code Jam – soutěž pořádaná od roku 2003, kterou poskytuje a sponzoruje Google
• Soutěž v programování IEEEXtreme – každoroční soutěž pro studenty IEEE, kterou pořádá od roku 2006 organizace IEEE .
• Topcoder Open (TCO) – Algoritmická soutěž pořádaná od roku 2001 společností Topcoder

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

Dlouhodobý

• HackerRank Week of Code
• ICFP Programming Contest – každoroční třídenní soutěž pořádaná od roku 1998 Mezinárodní konferencí funkčního programování
• Topcoder Marathon zápasy
• Codechef Long Challenges – pořádané každý měsíc – trvají až 10 dní

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

• Kaggle – soutěže ve strojovém učení.
• CodeCup – AI soutěž deskových her se koná každoročně od roku 2003. Pravidla hry jsou zveřejněna v září a finálový turnaj se koná v lednu.
• Google AI Challenge – dvouleté soutěže pro studenty, které probíhaly v letech 2009 až 2011
• Halite – Programovací výzva AI sponzorovaná společnostmi Two Sigma, Cornell Tech a Google
• Ruský AI Cup otevřená soutěž v programování umělé inteligence

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

• Seznam může být neúplný

Online zápas a zdroje školení

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

Pozoruhodní účastníci

Následující seznam obsahuje soutěžící, kteří dosáhli významných výsledků v programátorských soutěžích a do určité míry i ve své kariéře. Všimněte si, že tento seznam nezahrnuje lidi (například Mark Zuckerberg ), kteří by mohli být úspěšní ve své kariéře, ale neměli významné výsledky v konkurenčním programování:

• Gennady Korotkevich (turista)
• Petr Mitrichev (Petr)
• Makoto Soejima (rng_58), jeden z bývalých administrátorů a autorů problémů Topcoderu a zakládající člen Atcoderu.
• Tiancheng Lou (ACRush), dvojnásobný vítěz Google Code Jam (2008 a 2009), spoluzakladatel Pony.ai
• Adam D'Angelo , technický ředitel Facebooku a zakladatel společnosti Quora .
• Scott Wu (scott_wu), technický ředitel Lunchclubu .
• Matei Zaharia (Matei), odborný asistent na Stanfordské univerzitě a zakladatel Databricks .

Výhody a kritika

Účast v programovacích soutěžích může zvýšit nadšení studentů pro studium informatiky . 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é často vyžadují, aby kandidáti řešili složité programovací a algoritmické problémy přímo na místě.

Objevila se také kritika konkurenčního programování, zejména ze strany profesionálních softwarových vývojářů. Jedním kritickým bodem je, že mnoho rychlých programovacích soutěží učí konkurenty špatným programovacím návykům a stylu kódu (jako zbytečné používání maker , nedostatek OOP abstrakce a komentářů, používání krátkých názvů proměnných atd.). Programovací soutěže, jako je ICPC a IOI, také tím, že nabízejí pouze malé algoritmické hádanky s relativně krátkými řešeními, nemusí nutně učit dobré dovednosti a postupy softwarového inženýrství, protože skutečné softwarové projekty mají obvykle mnoho tisíc řádků kódu a jsou vyvíjeny velkými týmy. dlouhá časová období. Peter Norvig uvedl, že na základě dostupných údajů to, že se stal vítězem programátorských soutěží, negativně korelovalo s výkonem programátora v jeho práci ve společnosti Google (i když vítězové soutěže měli vyšší šance na získání zaměstnání). Norvig později uvedl, že tato korelace byla pozorována na malém souboru dat, ale že to nebylo možné potvrdit po prozkoumání většího souboru dat

Dalším názorem je, že než „ztrácet čas“ nadměrným soupeřením řešením problémů se známými řešeními, měli by významní programátoři raději investovat svůj čas do řešení skutečných problémů.

Literatura

• Halim, S., Halim, F. (2013). Soutěžní programování 3: Nová spodní hranice soutěží v programování . Svůdná žena.
• Laaksonen, A. (2017). Průvodce konkurenčním programováním (vysokoškolská témata informatiky). Cham: Springer International Publishing.

Viz také

• Kategorie:Počítačové soutěže
• Kód golfu
• Hackathon

Reference

externí odkazy

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

• Contest Management System Open source nástroj v Pythonu pro spouštění a správu programátorské soutěže na serveru IOI 2012 a IOI 2013 .