Конкурентное программирование - Competitive programming

Петр Митричев (слева) и Геннадий Короткевич (справа), два выдающихся программиста, соревнующихся во время конкурса.

Конкурентное программирование это умный спорт обычно проводится над Интернет или локальная сеть с участием участников, пытающихся программа согласно предоставленным спецификациям. Конкурсанты называются спортивные программисты. Конкурентное программирование признано и поддерживается несколькими международными компаниями, занимающимися разработкой программного обеспечения и Интернет, такими как Google[1][2] и Facebook.[3] Есть несколько организаций, которые регулярно проводят соревнования по программированию.

Соревнования по программированию обычно включают в себя ведущий, представляющий набор логичный или же математические задачи, также известный как загадки, конкурсантам (число которых может варьироваться от десятков до нескольких тысяч), и участники должны написать компьютерные программы способен решить любую проблему. Оценка основывается в основном на количестве решенных проблем и времени, затраченном на написание успешных решений, но может также включать другие факторы (качество полученного результата, время выполнения, размер программы и т. Д.)

История

Один из старейших известных конкурсов - это ICPC который зародился в 1970-х годах и расширился до 88 стран в его издании 2011 года.

С 1990 по 1994 гг. Оуэн Астрахан, Вивек Кхера и Дэвид Коц провели один из первых распределенных интернет-конкурсов по программированию, вдохновленных ICPC.[4]

Интерес к соревновательному программированию значительно вырос[количественно оценить ] с 2000 года и тесно связан с развитием Интернета, который способствует проведению международных конкурсов в режиме онлайн, устраняя географические проблемы.

Обзор

Цель соревновательного программирования - написать исходный код компьютерных программ, способных решать поставленные задачи. Подавляющее большинство задач, возникающих на олимпиадах по программированию, имеют математический или логический характер. Типичные такие задачи относятся к одной из следующих категорий: комбинаторика, теория чисел, теория графов, алгоритмическая теория игр, вычислительная геометрия, струнный анализ и структуры данных. Проблемы, связанные с искусственный интеллект также популярны на определенных соревнованиях.

Независимо от категории проблемы, процесс решения проблемы можно разделить на два основных этапа: построение эффективного алгоритм, и реализуя алгоритм в подходящем язык программирования (набор разрешенных языков программирования варьируется от конкурса к конкурсу). Это два наиболее часто проверяемых навыка на соревнованиях по программированию.

В большинстве соревнований судейство осуществляется автоматически хост-машинами, обычно известными как судьи. Каждое решение, представленное участником, оценивается судьей по набору (обычно секретных) тестовых примеров. Как правило, для задач конкурса используется система оценок «все или ничего», что означает, что решение считается «принятым» только в том случае, если оно дает удовлетворительные результаты во всех тестовых примерах, проведенных судьей, и отклоняется в противном случае. Однако некоторые задачи конкурса могут допускать частичную оценку, в зависимости от количества пройденных тестовых примеров, качества результатов или некоторых других заданных критериев. Некоторые другие конкурсы требуют только, чтобы участник представил выходные данные, соответствующие заданным входным данным, и в этом случае судье нужно только проанализировать предоставленные выходные данные.

Онлайн-судьи - это онлайн-среда, в которой проходит тестирование. Онлайн-судьи имеют рейтинговые списки, в которых показаны пользователи с наибольшим количеством принятых решений и / или наименьшим временем выполнения для конкретной проблемы.[5]

Известные соревнования

Есть два типа форматов соревнований: краткосрочные и долгосрочные. Каждый раунд краткосрочных соревнований длится от 1 до 5 часов. Длительные соревнования могут длиться от нескольких дней до нескольких месяцев.

В ближайщем будущем

В большинстве вышеуказанных соревнований, поскольку количество участников довольно велико, соревнования обычно проводятся в несколько туров. Обычно они требуют онлайн-участия во всех раундах, кроме последнего, который требует участия на месте. Особым исключением из этого правила является IEEEXtreme, ежегодное 24-часовое соревнование по виртуальному программированию. Лучшие участники IOI и ACM-ICPC получают золотые, серебряные и бронзовые медали, а в других конкурсах денежные призы вручаются лучшим участникам. Также занятие первых мест в таблицах результатов таких конкурсов может заинтересовать рекрутеров из софтверных и интернет-компаний.

Долгосрочное

Искусственный интеллект и машинное обучение

  • Kaggle - соревнования по машинному обучению.
  • CodeCup - соревнование по искусственному интеллекту для настольных игр, которое проводится ежегодно с 2003 года. Правила игры публикуются в сентябре, а финальный турнир проводится в январе.[12][13][14]
  • Google AI Challenge - проводимые раз в два года олимпиады для студентов с 2009 по 2011 гг.
  • Галит[15] - Задача программирования искусственного интеллекта, спонсируемая Two Sigma, Cornell Tech,[16] и Google[17]
  • Кубок России по ИИ открытый конкурс по программированию искусственного интеллекта

Конкурсы на технологии с открытым исходным кодом

  • Список может быть неполным
Название конкурсаГлавный спонсорОписаниеЗапуск сОбычное времяСледующий цикл примененияПоложение дел
Соревнование по мультиагентному программированиюКлаустальский технологический университет в сочетании с агент-ориентированными семинарамиЕжегодные международные соревнования по программированию для стимулирования исследований в области многоагентная система развитие и программирование.2005СентябрьСентябрь 2011 г.Активный
Google Summer of CodeGoogle Inc.Ежегодная программа, в рамках которой Google предоставляет стипендии сотням студентов, которые летом успешно завершили запрошенный проект бесплатного программного обеспечения / программирования с открытым исходным кодом.2005Март-август23 марта - 3 апреляАктивный
Конкурс открытого участия GoogleGoogle Inc.Конкурс, проводимый Google в 2007–2008 годах для старшеклассников. Конкурс призван побудить старшеклассников участвовать в проектах с открытым кодом.2007Ноя-февНеизвестныйНеизвестный

Интернет-конкурсы и обучающие ресурсы

Сообщество программистов по всему миру создало и поддерживает несколько интернет-ресурсов, посвященных соревновательному программированию. Они предлагают отдельные конкурсы с небольшими призами или без них. Также прошлые архивы задач являются популярным ресурсом для обучения соревновательному программированию. К ним относятся:

ИмяОписаниеИнтернет сайт
CodeChef[18][10]Поддерживаемый unacademy, он проводит 10-дневные соревнования и несколько коротких соревнований каждый месяц (один в стиле IOI под названием Luchtime и другой в стиле ACM ICPC под названием Cook-Off) и предоставляет образовательным учреждениям платформу для проведения соревнований бесплатно. Два лучших победителя длительного конкурса выиграют денежные призы, а 10 лучших игроков мира получат футболку.www.codechef.com
CodeCupЕжегодная международная настольная игра AI Соревнования по программированию, организованные Голландской олимпиадой по информатике с 2003 года.[13][14]кодекап.nl
Codeforces[19][18]Русский ресурс, поддерживаемый Университет ИТМО, который в основном предусматривает частые (до двух в неделю) короткие конкурсы. Особенности: все решения Открытый исходный код, возможность проверить правильность решений других участников во время «фазы взлома», виртуальных конкурсов, тренингов и т. д.codeforces.com
CodinGameЗагадки (возрастающая сложность), код гольф. Проводит регулярные онлайн-соревнования (AI проблемы, проблемы оптимизации ).www.codingame.com
ХакерЗемля[18]Бангалор, Индия базирующаяся компания, предоставляющая онлайн-конкурсы, подобные среде, с целью предоставления решений по оценке набора персонала.www.hackerearth.com
HackerRankHackerRank предлагает задачи программирования в различных областях компьютерных наук. На нем также размещаются ежегодные коды, которые помогают объединить программистов и стартапы Кремниевой долины.хакерранк.com
Проект Эйлер[10]Большой набор задач вычислительной математики (т.е. не связанных напрямую с программированием, но часто требующих навыков программирования для решения).проектировщик.сеть
Топкодер[19][18]Ресурс и компания США, которая организует конкурсы, а также предоставляет производственные проблемы как своего рода внештатную работу; Он предлагает десятки коротких конкурсов и несколько длинных («марафонов») каждый год. Особенность - участники имеют возможность проверить правильность решений других участников после этапа кодирования и перед финальным автоматическим тестированием (так называемая «фаза вызова»).www.topcoder.com
Судья UVa Online[19][18]Содержит более 4500 задач для практики. Проводит регулярные онлайн-соревнования. Открытый в 1995 году, он является одним из старейших подобных сайтов.онлайн-судья.org
SPOJ[18]Польский онлайн судья система, которая создает множество проблем для обучения и предоставляет платформу другим организаторам для проведения соревнований по программированию.www.spoj.com
Откройте КаттисПубличная версия системы управления контестами Kattis с архивом более 2600 задач.[19] Каттис был разработан, чтобы помочь курсам по информатике, но он также используется для проведения престижных соревнований, таких как финал ICPC World Finals.[20]открыто.kattis.com
AtCoderБазируясь в Японии, AtCoder еженедельно предлагает онлайн-конкурсы по программированию. Конкурсы проводятся на японском и английском языках.

По состоянию на 2020 год это одна из самых популярных платформ в своем роде.[21]

кодировщик.jp
Карибский онлайн-судьяИспанский ресурс, поддерживаемый Университет информатики.[22] Содержит более 3000 задач для практики. Также проводятся регулярные онлайн-соревнования.coj.uci.cu

Преимущества и критика

Участие в олимпиадах по программированию может повысить энтузиазм студентов Информатика исследования. Навыки, приобретенные в соревнованиях по программированию, подобных ICPC, также улучшают карьерные перспективы, поскольку помогают проходить «технические собеседования», которые часто требуют от кандидатов решения сложных программных и алгоритмических задач на месте.[19]

Также была критика конкурентного программирования, особенно со стороны профессиональных разработчиков программного обеспечения.[23] Одним из критических моментов является то, что многие быстро развивающиеся соревнования по программированию учат конкурентов плохим навыкам программирования и стилю кода (например, ненужное использование макросов, отсутствие абстракции и комментариев ООП, использование коротких имен переменных и т. Д.).[24][23] Кроме того, предлагая только небольшие алгоритмические головоломки с относительно короткими решениями, соревнования по программированию, такие как ICPC и IOI, не обязательно обучают хорошим навыкам и методам разработки программного обеспечения, поскольку в реальных проектах программного обеспечения обычно есть много тысяч строки кода и разрабатываются большими командами в течение длительных периодов времени.[23] Питер Норвиг заявил, что, исходя из имеющихся данных, победа в олимпиадах по программированию отрицательно коррелирует с результатами работы программиста в Google (хотя у победителей конкурса были более высокие шансы получить работу).[25]

Еще одно мнение состоит в том, что вместо того, чтобы «тратить» свое время на чрезмерную конкуренцию, решая проблемы с помощью известных решений, высокопоставленные программисты должны скорее вкладывать свое время в решение реальных проблем.[23]

Литература

  • Халим, С., Халим, Ф. (2013). Соревновательное программирование 3: новая нижняя граница соревнований по программированию. Лулу.
  • Лааксонен, А. (2017). Руководство по соревновательному программированию (Бакалавриат по информатике). Чам: Издательство Springer International.

Смотрите также

Рекомендации

  1. ^ "Google Code Jam". google.com. Получено 2016-02-20.
  2. ^ «Спонсор TCO12: Google - TCO 12». topcoder.com. Архивировано из оригинал 16 февраля 2012 г.
  3. ^ "Facebook Hacker Cup". Facebook. Получено 2016-02-20.
  4. ^ Кера, Вивек; Астрахан, Оуэн; Коц, Дэвид (1993). «Конкурс интернет-программирования» (PDF). Бюллетень ACM SIGCSE. 25 (1): 48–52. Дои:10.1145/169073.169105. ISSN  0097-8418.
  5. ^ Проблемы программирования (Skiena & Revilla) ISBN  0387001638, ISBN  978-0387001630
  6. ^ "Ежемесячные конкурсы CodeChef".
  7. ^ «Программисты со всего мира соревнуются на CodeChef SnackDown - ExchangeMedia».
  8. ^ "Соревнования Codeforces". Получено 2018-10-12.
  9. ^ "Проблемы программирования и соревнования :: HackerRank". HackerRank. Получено 2016-02-20.
  10. ^ а б c Комбефис, Себастьян; Wautelet, Джереми (2014). «Тренинги по программированию и обучение информатике через онлайн-конкурсы» (PDF). Олимпиады по информатике. 8: 21–34.
  11. ^ "Проблемы программирования и соревнования :: HackerRank". HackerRank. Получено 2016-02-20.
  12. ^ "CodeCup". www.codecup.nl.
  13. ^ а б Лассе Хакулинен. Опрос на олимпиадах по информатике: развивающие задачи - Олимпиады по информатике, 2011, т. 5, 12–25.
  14. ^ а б Уеверс, Лесли (2014). «Поиск дерева Монте-Карло для Poly-Y» (PDF). Университет Твенте. Архивировано из оригинал (PDF) 13 апреля 2017 г.. Получено 16 сентября 2018.
  15. ^ «Задача программирования искусственного интеллекта Halite». www.halite.io.
  16. ^ «Two Sigma объявляет об открытии публичного запуска Halite». tech.cornell.edu.
  17. ^ «Halite помогает студентам и разработчикам соревноваться за создание лучшего ИИ на платформе Google Cloud».
  18. ^ а б c d е ж Луиджи, Уильям Ди; Фарина, Габриэле; Лаура, Луиджи; Нанни, Умберто; Темперини, Марко; Версари, Лука (2016). "oii-web: интерактивное онлайн-программирование oii-web: интерактивная система обучения онлайн-программированию" (PDF). Олимпиады по информатике. 10: 207–222.
  19. ^ а б c d е Блумфилд, Аарон; Сотомайор, Борха. "Руководство по стратегии соревнований по программированию" (PDF). SIGCSE '16: Материалы 47-го технического симпозиума ACM по образованию в области информатики.
  20. ^ Enström, E .; Kreitz, G .; Niemelä, F .; Söderman, P .; Канн, В. (2011). «Пять лет с Каттис - использование автоматизированной системы оценивания в обучении» (PDF). Конференция IEEE Frontiers in Education.
  21. ^ Мирзаянов, Майк; Павлова, Оксана; Маврин, Павел; Мельников, Роман; Плотников, Андрей; Парфенов Владимир; Станкевич, Андрей (2020). «Codeforces как образовательная платформа для обучения программированию в условиях цифровизации» (PDF). Олимпиады по информатике. 14. ISSN  1822-7732.
  22. ^ "О судье | Caribbean Online Judge". coj.uci.cu. Получено 2020-06-18.
  23. ^ а б c d Смит, Дункан (2 декабря 2015 г.). «Дебаты по соревновательному программированию».
  24. ^ Халим, Стивен. «CS3233 - Соревновательное программирование». Школа вычислительной техники NUS.
  25. ^ «Победа на соревнованиях по программированию - негативный фактор для хорошей работы». 5 апреля 2015 года.

внешняя ссылка

Открытый проект для проведения конкурсов