Programare competitivă - Competitive programming

Petr Mitrichev (stânga) și Gennady Korotkevich (dreapta), doi programatori competitivi proeminenți în timpul unui concurs.

Programarea competitivă este un sport mental desfășurat de obicei prin Internet sau o rețea locală , implicând participanții care încearcă să programeze conform specificațiilor furnizate. Concurenții sunt numiți programatori de sport . Programarea competitivă este recunoscută și susținută de mai multe companii multinaționale de software și Internet, precum Google și Facebook .

Un concurs de programare presupune, în general, prezentarea de către gazdă a unui set de probleme logice sau matematice , cunoscute și sub denumirea de puzzle-uri , concurenților (care pot varia ca număr de la zeci la câteva mii), iar concurenții trebuie să scrie programe de calculator capabile să rezolve fiecare problemă. . Judecarea se bazează în principal pe numărul de probleme rezolvate și pe timpul petrecut pentru scrierea soluțiilor de succes, dar poate include și alți factori (calitatea rezultatelor produse, timpul de execuție, dimensiunea programului etc.)

Istorie

Unul dintre cele mai vechi concursuri cunoscute este ICPC , care a apărut în anii 1970 și a crescut pentru a include 88 de țări în ediția sa din 2011.

Din 1990 până în 1994, Owen Astrachan , Vivek Khera și David Kotz au organizat unul dintre primele concursuri de programare distribuite, bazate pe internet, inspirate de ICPC.

Interesul pentru programarea competitivă a crescut considerabil începând cu anul 2000 și este strâns legat de creșterea internetului, ceea ce facilitează organizarea online de concursuri internaționale, eliminând problemele geografice.

Prezentare generală

Scopul programării competitive este de a scrie codul sursă al programelor de calculator care sunt capabile să rezolve problemele date. Marea majoritate a problemelor care apar în concursurile de programare sunt de natură matematică sau logică. Astfel de sarcini tipice aparțin uneia dintre următoarele categorii: combinatorie , teoria numerelor , teoria grafurilor , teoria jocurilor algoritmice , geometrie computațională , analiza șirurilor și structurile de date . Problemele legate de programarea cu constrângeri și inteligența artificială sunt, de asemenea, populare în anumite competiții.

Indiferent de categoria problemei, procesul de rezolvare a unei probleme poate fi împărțit în două etape mari: construirea unui algoritm eficient și implementarea algoritmului într-un limbaj de programare adecvat (setul de limbaje de programare permis variază de la concurs la concurs). Acestea sunt cele două abilități testate cel mai frecvent în competițiile de programare.

În majoritatea concursurilor, jurizarea se face automat de către mașini gazdă, cunoscute în mod obișnuit ca arbitri. Fiecare soluție prezentată de un concurent este aplicată judecătorului împotriva unui set de cazuri de testare (de obicei secrete). În mod normal, problemele de concurs au un sistem de notare „tot sau nimic”, ceea ce înseamnă că o soluție este „Acceptată” numai dacă produce rezultate satisfăcătoare în toate cazurile de testare conduse de judecător și respinsă în caz contrar. Cu toate acestea, unele probleme ale concursului pot permite punctaj parțial, în funcție de numărul de cazuri de testare trecute, de calitatea rezultatelor sau de alte criterii specificate. Unele alte concursuri necesită doar ca concurentul să trimită rezultatul corespunzătoare datelor de intrare date, caz în care judecătorul trebuie să analizeze doar datele de ieșire transmise.

Judecătorii online sunt medii online în care au loc testarea. Judecătorii online au liste de clasare care arată utilizatorii cu cel mai mare număr de soluții acceptate și/sau cel mai scurt timp de execuție pentru o anumită problemă.

Competiții notabile

Există două tipuri de formate de competiție: pe termen scurt și pe termen lung. Fiecare rundă de competiție pe termen scurt durează de la 1 la 5 ore. Competițiile pe termen lung pot dura de la câteva zile până la câteva luni.

Termen scurt

• International Collegiate Programming Contest (ICPC) – una dintre cele mai vechi competiții, pentru studenții universităților în grupuri de câte 3 persoane fiecare
• Olimpiada Internațională de Informatică (IOI) – una dintre cele mai vechi competiții, pentru elevii de liceu
• American Computer Science League (ACSL) – competiție de informatică cu porțiuni scrise și de programare, pentru elevii de gimnaziu/liceu
• CodeChef – competiție desfășurată din 2009, există trei concursuri organizate în fiecare lună și o competiție anuală numită CodeChef SnackDown
• Runda Codeforces – de obicei, concurs de două ore, desfășurat în fiecare săptămână
• Facebook Hacker Cup – competiție desfășurată din 2011, oferită și sponsorizată de Facebook
• HackerRank – competiții multiple
• Gridwars – patru competiții organizate între 2003 și 2004.
• Google Code Jam – competiție organizată din 2003, furnizată și sponsorizată de Google
• IEEEXtreme Programming Competition – competiție anuală pentru studenții IEEE, organizată din 2006 de IEEE .
• Topcoder Open (TCO) – Competiție de algoritmi organizată din 2001 de Topcoder

În majoritatea competițiilor de mai sus, deoarece numărul concurenților este destul de mare, competițiile sunt de obicei organizate în mai multe runde. De obicei, necesită participarea online la toate rundele, cu excepția ultimei, care necesită participarea la fața locului. O excepție specială de la aceasta este IEEEXtreme, care este o competiție anuală de programare virtuală de 24 de ore. Performanții de top de la IOI și ICPC primesc medalii de aur, argint și bronz, în timp ce în celelalte concursuri, premii în bani sunt acordate primilor clasați. De asemenea, atingerea locurilor de top în tabelele de scor ale unor astfel de competiții poate atrage interesul recrutorilor de la companii de software și de internet.

Termen lung

• Săptămâna codului HackerRank
• Concurs de programare ICFP – competiție anuală de 3 zile desfășurată din 1998 de către Conferința Internațională de Programare Funcțională
• Topcoder Marathon Meciuri
• Codechef Long Challenges - desfășurate în fiecare lună - durează până la 10 zile

Inteligența artificială și învățarea automată

• Kaggle – competiții de învățare automată.
• CodeCup – competiție de IA pentru jocuri de masă care se desfășoară anual din 2003. Regulile jocului sunt publicate în septembrie, iar turneul final are loc în ianuarie.
• Google AI Challenge – competiții bianuale pentru studenți care au avut loc între 2009 și 2011
• Halite – O provocare de programare AI sponsorizată de Two Sigma, Cornell Tech și Google
• Concurs deschis de programare cu inteligență artificială Russian AI Cup

Concursuri axate pe tehnologii open source

• Lista poate fi incompletă

Concurs online și resurse de formare

Comunitatea de programare din întreaga lume a creat și întreținut mai multe resurse de internet dedicate programării competitive. Oferă concursuri independente cu sau fără premii minore. De asemenea, arhivele de probleme din trecut sunt o resursă populară pentru formarea în programarea competitivă. Există mai multe organizații care găzduiesc competiții de programare în mod regulat. Acestea includ:

Participanți de seamă

Următoarea listă este formată din concurenții care au obținut rezultate semnificative la concursurile de programare și, într-o oarecare măsură, în cariera lor respectivă. Rețineți că această listă exclude persoanele (de exemplu, Mark Zuckerberg ) care ar putea avea succes în cariera lor, dar nu au avut rezultate semnificative în programarea competitivă:

• Gennady Korotkevich (turist)
• Petr Mitrichev (Petr)
• Makoto Soejima (rng_58), unul dintre foștii administratori și scriitori de probleme Topcoder și membru fondator al Atcoder.
• Tiancheng Lou (ACRush), de două ori câștigător Google Code Jam (2008 și 2009), co-fondator al Pony.ai
• Adam D'Angelo , CTO al Facebook și fondator Quora .
• Scott Wu (scott_wu), CTO al Lunchclub .
• Matei Zaharia (Matei), profesor asistent la Universitatea Stanford și fondator Databricks .

Beneficii și critici

Participarea la concursuri de programare poate crește entuziasmul studenților pentru studiile de informatică . Abilitățile dobândite în cadrul concursurilor de programare asemănătoare ICPC îmbunătățesc și perspectivele de carieră, deoarece ajută la promovarea „interviurilor tehnice”, care necesită adesea candidaților să rezolve pe loc probleme complexe de programare și algoritm.

Au existat, de asemenea, critici la adresa programării competitive, în special din partea dezvoltatorilor de software profesioniști. Un punct critic este că multe concursuri de programare cu ritm rapid îi învață pe concurenți obiceiuri proaste de programare și stilul de cod (cum ar fi utilizarea inutilă a macrocomenzilor , lipsa abstractizării și comentariilor OOP, utilizarea numelor scurte de variabile etc.). De asemenea, oferind doar puzzle-uri algoritmice mici cu soluții relativ scurte, concursurile de programare precum ICPC și IOI nu învață neapărat abilități și practici bune de inginerie software, deoarece proiectele software reale au, de obicei, multe mii de linii de cod și sunt dezvoltate de echipe mari peste perioade lungi de timp. Peter Norvig a afirmat că, pe baza datelor disponibile, a fi câștigător al concursurilor de programare a corelat negativ cu performanța unui programator la locul de muncă la Google (chiar dacă câștigătorii concursului aveau șanse mai mari de a fi angajați). Norvig a declarat ulterior că această corelație a fost observată pe un set mic de date, dar că nu a putut fi confirmată după examinarea unui set mai mare de date.

Totuși, un alt sentiment este că, în loc să-și „irosească” timpul în concurența excesivă prin rezolvarea problemelor cu soluții cunoscute, programatorii de nivel înalt ar trebui să investească mai degrabă timpul lor în rezolvarea problemelor din lumea reală.

Literatură

• Halim, S., Halim, F. (2013). Programare competitivă 3: noua limită inferioară a concursurilor de programare . Lulu.
• Laaksonen, A. (2017). Ghid de programare competitivă (Subiecte de licență în informatică). Cham: Springer International Publishing.

Vezi si

• Categorie:Concursuri de informatică
• Cod golf
• Hackathon

Referințe

linkuri externe

Proiect open-source pentru derularea de concursuri

• Contest Management System Instrument open-source în Python pentru a rula și gestiona un concurs de programare pe un server IOI 2012 și IOI 2013 .