Rekabetçi programlama - Competitive programming

Petr Mitrichev (solda) ve Gennady Korotkevich (sağda), bir yarışma sırasında önde gelen iki rekabetçi programcı.

Rekabetçi programlama , genellikle İnternet veya yerel bir ağ üzerinden gerçekleştirilen ve sağlanan özelliklere göre programlama yapmaya çalışan katılımcıları içeren bir zihin sporudur . Yarışmacılara spor programcısı denir . Rekabetçi programlama, Google ve Facebook gibi birçok çok uluslu yazılım ve İnternet şirketi tarafından tanınmakta ve desteklenmektedir .

Bir programlama yarışması genellikle yarışmacının yarışmacılara (sayıları on ile birkaç bin arasında değişebilen) bulmacalar olarak da bilinen bir dizi mantıksal veya matematiksel problem sunmasını içerir ve yarışmacıların her bir sorunu çözebilecek bilgisayar programları yazmaları gerekir. . Yargılama, çoğunlukla çözülen problemlerin sayısına ve başarılı çözümler yazmak için harcanan zamana dayanır, ancak diğer faktörleri de (üretilen çıktının kalitesi, yürütme süresi, program boyutu vb.)

Tarih

Bilinen en eski yarışmalardan biri , 1970'lerde ortaya çıkan ve 2011 baskısında 88 ülkeyi kapsayacak şekilde büyüyen ICPC'dir .

1990'dan 1994'e kadar Owen Astrachan, Vivek Khera ve David Kotz, ICPC'den ilham alan ilk dağıtılmış, internet tabanlı programlama yarışmalarından birini düzenledi.

Rekabetçi programlamaya olan ilgi 2000'den beri yoğun bir şekilde arttı ve coğrafi sorunları ortadan kaldırarak uluslararası yarışmaların çevrimiçi olarak düzenlenmesini kolaylaştıran İnternet'in büyümesiyle güçlü bir şekilde bağlantılı.

genel bakış

Rekabetçi programlamanın amacı, verilen problemleri çözebilen bilgisayar programlarının kaynak kodunu yazmaktır. Programlama yarışmalarında ortaya çıkan problemlerin büyük çoğunluğu, doğası gereği matematiksel veya mantıksaldır. Tipik bu tür görevler aşağıdaki kategorilerden birine aittir: kombinatorik , sayı teorisi , çizge teorisi , algoritmik oyun teorisi , hesaplamalı geometri , dizi analizi ve veri yapıları . Kısıt programlama ve yapay zeka ile ilgili problemler de belirli yarışmalarda popülerdir.

Problem kategorisinden bağımsız olarak, bir problemi çözme süreci iki geniş adıma ayrılabilir: verimli bir algoritma oluşturmak ve algoritmayı uygun bir programlama dilinde uygulamak (izin verilen programlama dilleri seti yarışmadan yarışmaya değişir). Bunlar, programlama yarışmalarında en sık test edilen iki beceridir.

Çoğu yarışmada, değerlendirme, genellikle jüri olarak bilinen ana makineler tarafından otomatik olarak yapılır. Bir yarışmacı tarafından sunulan her çözüm, bir dizi (genellikle gizli) test senaryosuna karşı yargıç üzerinde yürütülür. Normalde, yarışma problemlerinde ya hep ya hiç puanlama sistemi vardır, yani bir çözümün yalnızca yargıç tarafından yürütülen tüm test davalarında tatmin edici sonuçlar vermesi ve aksi takdirde reddedilmesi durumunda "Kabul Edildi" olduğu anlamına gelir. Bununla birlikte, bazı yarışma sorunları, geçilen test senaryolarının sayısına, sonuçların kalitesine veya diğer belirli kriterlere bağlı olarak kısmi puanlamaya izin verebilir. Diğer bazı yarışmalar, yalnızca yarışmacının verilen girdi verilerine karşılık gelen çıktıyı sunmasını gerektirir, bu durumda hakemin yalnızca gönderilen çıktı verilerini analiz etmesi gerekir.

Çevrimiçi yargıçlar, testlerin yapıldığı çevrimiçi ortamlardır. Çevrimiçi yargıçlar, belirli bir sorun için en fazla sayıda kabul edilen çözüme ve/veya en kısa yürütme süresine sahip kullanıcıları gösteren sıralama listelerine sahiptir.

Önemli yarışmalar

İki tür yarışma formatı vardır: kısa vadeli ve uzun vadeli. Kısa süreli yarışmanın her turu 1 ila 5 saat sürer. Uzun süreli yarışmalar birkaç günden birkaç aya kadar sürebilir.

Kısa vadeli

• Uluslararası Üniversite Programlama Yarışması (ICPC) - her biri 3 kişilik gruplar halinde üniversite öğrencileri için en eski yarışmalardan biri
• Uluslararası Bilişim Olimpiyatı (IOI) – ortaokul öğrencileri için en eski yarışmalardan biri
• American Computer Science League (ACSL) – orta/lise öğrencileri için yazılı ve programlama bölümleri olan bilgisayar bilimi yarışması
• CodeChef - 2009'dan itibaren düzenlenen yarışma, her ay düzenlenen üç yarışma ve CodeChef SnackDown adlı yıllık bir yarışma var.
• Codeforces Round - tipik olarak her hafta düzenlenen iki saatlik yarışma
• Facebook Hacker Cup – Facebook tarafından sağlanan ve sponsor olunan 2011 yılında düzenlenen yarışma
• HackerRank – çoklu yarışmalar
• Gridwars - 2003 ve 2004 yılları arasında düzenlenen dört yarışma.
• Google Code Jam – Google tarafından sağlanan ve sponsor olunan 2003 yılından beri düzenlenen yarışma
• IEEEXtreme Programlama Yarışması – 2006'dan beri IEEE tarafından düzenlenen IEEE Öğrenci Üyeleri için yıllık yarışma .
• Topcoder Open (TCO) – Topcoder tarafından 2001'den beri düzenlenen Algoritma yarışması

Yukarıdaki yarışmaların çoğunda, yarışmacı sayısı oldukça fazla olduğundan, yarışmalar genellikle birkaç turda düzenlenir. Genellikle, yerinde katılım gerektiren son tur hariç tüm turlarda çevrimiçi katılım gerektirirler. Bunun özel bir istisnası, her yıl 24 saatlik bir sanal programlama yarışması olan IEEEXtreme'dir. IOI ve ICPC'de en iyi performans gösterenler altın, gümüş ve bronz madalya alırken, diğer yarışmalarda en iyi dereceye girenlere nakit ödüller verilir. Ayrıca bu tür yarışmaların puan tablosunda en üst sıralarda yer almak, yazılım ve internet şirketlerinden işe alım uzmanlarının ilgisini çekebilir.

uzun vadeli

• HackerRank Kod Haftası
• ICFP Programlama Yarışması - Uluslararası Fonksiyonel Programlama Konferansı tarafından 1998'den beri düzenlenen yıllık 3 günlük yarışma
• Topcoder Maraton Maçları
• Codechef Uzun Mücadeleleri - her ay yapılır - 10 güne kadar sürer

Yapay zeka ve makine öğrenimi

• Kaggle – makine öğrenimi yarışmaları.
• CodeCup – 2003'ten beri her yıl düzenlenen masa oyunu AI yarışması. Oyun kuralları Eylül'de yayınlanır ve final turnuvası Ocak'ta yapılır.
• Google AI Challenge - 2009'dan 2011'e koşan öğrenciler için iki yılda bir yapılan yarışmalar
• Halite – Two Sigma, Cornell Tech ve Google tarafından desteklenen bir AI programlama mücadelesi
• Rusya AI Kupası açık yapay zeka programlama yarışması

Açık kaynak teknolojilerine odaklanan yarışmalar

• Liste eksik olabilir

Çevrimiçi yarışma ve eğitim kaynakları

Dünyanın dört bir yanındaki programlama topluluğu, rekabetçi programlamaya adanmış birkaç internet kaynağı oluşturmuş ve sürdürmüştür. Küçük ödüllü veya ödülsüz bağımsız yarışmalar sunarlar. Ayrıca geçmiş sorun arşivleri, rekabetçi programlama eğitimi için popüler bir kaynaktır. Programlama yarışmalarına düzenli olarak ev sahipliği yapan birkaç kuruluş vardır. Bunlar şunları içerir:

Önemli katılımcılar

Aşağıdaki liste, programlama yarışmalarında ve bir dereceye kadar kendi kariyerlerinde önemli sonuçlar elde eden yarışmacılardan oluşmaktadır. Bu listenin , kariyerlerinde başarılı olabilecek ancak rekabetçi programlamada önemli sonuçları olmayan kişileri (örneğin Mark Zuckerberg ) hariç tuttuğunu unutmayın:

• Gennady Korotkevich (turist)
• Petr Mitrichev (Petr)
• Makoto Soejima (rng_58), Topcoder'ın eski yönetici ve sorun yazarlarından biri ve Atcoder'ın kurucu üyesi.
• Tiancheng Lou (ACRush), 2 kez Google Code Jam kazananı (2008 ve 2009), Pony.ai'nin kurucu ortağı
• Adam D'Angelo , Facebook'un CTO'su ve Quora'nın kurucusu .
• Scott Wu (scott_wu), Lunchclub'ın CTO'su .
• Matei Zaharia (Matei), Stanford Üniversitesi'nde yardımcı doçent ve Databricks'in kurucusu .

Faydalar ve eleştiri

Programlama yarışmalarına katılım, öğrencilerin bilgisayar bilimleri çalışmalarına yönelik hevesini artırabilir . ICPC benzeri programlama yarışmalarında kazanılan beceriler, genellikle adayların karmaşık programlama ve algoritmik sorunları anında çözmelerini gerektiren "teknik mülakatları" geçmeye yardımcı olduğu için kariyer beklentilerini de geliştirir.

Ayrıca, özellikle profesyonel yazılım geliştiricilerinden, rekabetçi programlamaya yönelik eleştiriler de olmuştur. Kritik bir nokta, birçok hızlı tempolu programlama yarışmasının rakiplere kötü programlama alışkanlıklarını ve kod stilini öğretmesidir (gereksiz makro kullanımı , OOP soyutlama ve yorum eksikliği, kısa değişken adlarının kullanımı vb.). Ayrıca, ICPC ve IOI gibi programlama yarışmaları, yalnızca nispeten kısa çözümler içeren küçük algoritmik bulmacalar sunarak, gerçek yazılım projelerinin tipik olarak binlerce kod satırına sahip olması ve büyük ekipler tarafından geliştirilmesi nedeniyle iyi yazılım mühendisliği becerileri ve uygulamaları öğretmez . uzun zaman dilimleri. Peter Norvig , mevcut verilere dayanarak, programlama yarışmalarının galibi olmanın, bir programcının Google'daki işindeki performansıyla (yarışma kazananlarının işe alınma şansı daha yüksek olmasına rağmen) negatif korelasyon gösterdiğini belirtti. Norvig daha sonra bu ilişkinin küçük bir veri setinde gözlemlendiğini, ancak daha büyük bir veri seti incelendikten sonra teyit edilemediğini belirtti.

Bir başka düşünce de, yüksek profilli programcıların, bilinen çözümlerle sorunları çözerek aşırı rekabetle zamanlarını boşa harcamak yerine, zamanlarını gerçek dünya sorunlarını çözmeye ayırmaları gerektiğidir.

Edebiyat

• Halim, S., Halim, F. (2013). Rekabetçi Programlama 3: Programlama Yarışmalarının Yeni Alt Sınırı . Lulu.
• Laaksonen, A. (2017). Rekabetçi Programlama Kılavuzu (Bilgisayar Bilimlerinde Lisans Konuları). Cham: Springer Uluslararası Yayıncılık.

Ayrıca bakınız

• Kategori:Bilgisayar bilimi yarışmaları
• kod golf
• Hackathon

Referanslar

Dış bağlantılar

Yarışmalar yürütmek için açık kaynaklı proje

• Yarışma Yönetim Sistemi Python'da bir sunucu IOI 2012 ve IOI 2013'te bir programlama yarışması yürütmek ve yönetmek için açık kaynak aracı .