Соревновательное программирование
Соревновательное программирование или спортивное программирование — это интеллектуальный вид спорта, в котором участники пытаются программировать в соответствии с предоставленными спецификациями. Конкурсы обычно проводятся через Интернет или локальную сеть . Конкурсное программирование признается и поддерживается несколькими транснациональными компаниями-разработчиками программного обеспечения и Интернет- компаниями, такими как Google. [1] [2] и Мета . [3]
Соревнования по программированию обычно включают в себя, что ведущий представляет участникам набор логических или математических задач , также известных как головоломки или задачи (количество которых может варьироваться от десятков или даже сотен до нескольких тысяч). Конкурсанты должны написать компьютерные программы, способные решить эти задачи. Оценка основывается в основном на количестве решенных задач и времени, затраченном на написание успешных решений, но может также включать и другие факторы (качество результатов, время выполнения, использование памяти, размер программы и т. д.).
История
[ редактировать ]Одним из старейших известных соревнований является Международное студенческое соревнование по программированию (ICPC), которое зародилось в 1970-х годах. [4] и в издание 2011 года включило 88 стран.
С 1990 по 1994 год Оуэн Астрачан , Вивек Кера и Дэвид Коц провели одни из первых распределенных интернет-соревнований по программированию, вдохновленных ICPC. [5]
Интерес к соревновательному программированию значительно вырос с 2000 года до десятков тысяч участников (см. «Известные соревнования ») и тесно связан с развитием Интернета, который облегчает проведение международных соревнований онлайн, устраняя географические проблемы.
Обзор
[ редактировать ]Целью соревновательного программирования является написание исходного кода компьютерных программ, способных решать заданные задачи. Подавляющее большинство задач, возникающих на соревнованиях по программированию, носят математический или логический характер. Типичные такие задачи относятся к одной из следующих категорий: комбинаторика , теория чисел , теория графов , алгоритмическая теория игр , вычислительная геометрия , струнный анализ , дискретная математика и структуры данных . [6] задачи, связанные с программированием в ограничениях и искусственным интеллектом В некоторых соревнованиях также популярны .
Независимо от категории проблемы, процесс решения проблемы можно разделить на два больших этапа: построение эффективного алгоритма и реализация алгоритма на подходящем языке программирования (набор разрешенных языков программирования варьируется от конкурса к конкурсу). Это два наиболее часто проверяемых навыка на соревнованиях по программированию.
В большинстве соревнований судейство осуществляется автоматически с помощью хост-машин, обычно называемых судьями. Каждое решение, представленное участником, проверяется судьей на основе набора (обычно секретных) тестовых примеров. Обычно задачи конкурса имеют систему оценок «все или ничего», что означает, что решение считается «принятым» только в том случае, если оно дает удовлетворительные результаты во всех тестовых случаях, проводимых судьей, и отклоняется в противном случае. Однако некоторые задачи конкурса могут допускать частичную оценку в зависимости от количества пройденных тестовых случаев, качества результатов или некоторых других указанных критериев. Некоторые другие конкурсы требуют, чтобы участник представил только выходные данные, соответствующие заданным входным данным, и в этом случае судье нужно только проанализировать представленные выходные данные.
Онлайн-судьи — это онлайн-среда, в которой происходит тестирование. У онлайн-судей есть рейтинговые списки, показывающие пользователей с наибольшим количеством принятых решений и/или самым коротким временем выполнения конкретной задачи. [7]
Известные соревнования
[ редактировать ]Алгоритмические соревнования
[ редактировать ]| Название конкурса [8] | Организаторы | Аудитория | Описание | Количество участников |
|---|---|---|---|---|
| Google Code Jam (GCJ) | открыть | Ежегодный конкурс, организованный и спонсируемый Google с 2003 года до его отмены в 2023 году. [9] | 32,702 (2022) [10] | |
| Международные студенческие соревнования по программированию (ICPC) [11] | Фонд ICPC | студенты университета | Командные соревнования для студентов университетов. Конкурс состоит из множества региональных туров, которые завершаются мировым финалом, организуемым ежегодно. Команды состоят из трёх студентов одного университета и им разрешается использовать только один компьютер. [12] | 50,000+ (2022) [13] |
| Международная олимпиада по информатике (IOI) | ИОИ | ученики средней школы | Международный конкурс среди школьников. Организуется ежегодно с 1989 года. Каждая страна может отправить на соревнование не более 4 участников. | 349 из 88 стран (2022 г.) [14] |
| Meta Hacker Cup (ранее Facebook Hacker Cup ) | Мета-платформы | открыть | Ежегодный конкурс проводится с 2011 года. Организатор и спонсор Meta (ранее Facebook ). | 27,604 (2022) [15] |
| Топкодер открытый (TCO) | Топкодер | открыть | Ежегодный конкурс алгоритмов, проводимый с 2001 года до его отмены в 2023 году. [16] |
В большинстве вышеперечисленных соревнований соревнования обычно проводятся в несколько туров. Обычно они начинаются с онлайн-раундов, которые завершаются финальным раундом на месте. Лучшие участники IOI и ICPC получают золотые, серебряные и бронзовые медали. В остальных конкурсах лучшим участникам вручаются денежные призы. Конкурсы также привлекают интерес рекрутеров из множества компаний, занимающихся программным обеспечением и Интернетом, которые часто обращаются к конкурентам с потенциальными предложениями о работе.
Искусственный интеллект и машинное обучение
[ редактировать ]- Список может быть неполным
| Имя | Главные организаторы | Описание | Статус |
|---|---|---|---|
| Каггл | Платформа для соревнований по науке о данных, машинном обучении и математической оптимизации и онлайн-сообщество. | Активный | |
| Вызов искусственного интеллекта | Университет Ватерлоо | Международный конкурс по программированию искусственного интеллекта, проходивший с 2009 по 2011 год. | Неактивный |
| Конкурс Halite по программированию искусственного интеллекта | Две Сигмы, Корнеллский технологический институт | Конкурс компьютерного программирования, в котором участники создают ботов на желаемом языке программирования, чтобы соревноваться на двумерном поле битвы. | Неизвестный |
| Кубок России по искусственному интеллекту | Mail.Ru Group, My.com | Ежегодный конкурс по программированию искусственного интеллекта. | Неизвестный |
Конкурсы по технологиям с открытым исходным кодом
[ редактировать ]- Список может быть неполным
| Название конкурса | Главный спонсор | Описание | Работает с | Обычное время | Следующий цикл применения | Статус |
|---|---|---|---|---|---|---|
| Конкурс мультиагентного программирования | Технологический университет Клаусталь совместно с агентно-ориентированными семинарами | Ежегодный международный конкурс по программированию для стимулирования исследований в области мультиагентных систем разработки и программирования . | 2005 | сентябрь | Сентябрь 2011 г. | Активный |
| Google Лето кода | Гугл Инк. | Ежегодная программа, в рамках которой Google присуждает стипендии сотням студентов, успешно завершивших запрошенный проект по программированию бесплатного программного обеспечения/с открытым исходным кодом в течение лета. | 2005 | март-август | 23 марта – 3 апреля | Активный |
| Конкурс Google с открытым участием | Гугл Инк. | Конкурс, проведенный Google в 2007–2008 годах, был ориентирован на старшеклассников. Конкурс призван побудить старшеклассников к участию в open-source проектах. | 2007 | ноябрь-февраль | Неизвестный | Неизвестный |
Онлайн-платформы
[ редактировать ]Сообщество программистов по всему миру создало и поддерживает несколько интернет-ресурсов, посвященных соревновательному программированию. Они предлагают отдельные конкурсы с небольшими призами или без них. Пользователям обычно присваивается рейтинг на основе их результатов в указанных конкурсах. Архивы прошлых задач — популярные ресурсы для обучения соревновательному программированию. Есть несколько организаций, которые регулярно проводят соревнования по программированию. К ним относятся:
| Имя | Описание |
|---|---|
| Появление кода | Ежегодное соревнование по программированию, проводимое во время Адвента , с новой парой головоломок, выпускаемых каждый день, вплоть до Рождества. Вторая задача каждого дня блокируется до завершения первой части и обычно логически вытекает из нее. Каждый год существуют как глобальные, так и частные таблицы лидеров, где рейтинги основаны на том, кто первым решит задачу. |
| КодШеф [17] [18] | Поддерживаемый Unacademy, он ежемесячно проводит трехдневные соревнования и несколько коротких конкурсов (один в стиле IOI под названием Lunchtime, а другой в стиле ICPC под названием Cook-Off), а также бесплатно предоставляет образовательным учреждениям платформу для проведения конкурсов. Два лучших победителя длинного конкурса получат денежные призы, а 10 лучших в мире получат футболки. |
| Кодфорс [19] [17] | Российская платформа, поддерживаемая Университетом ИТМО , на которой часто (до двух в неделю) проводятся 2-3-часовые конкурсы (доступны на английском и русском языках). Пользователи также могут участвовать в конкурсах, опубликованных другими пользователями в разделе «Тренажерный зал», отправлять дополнительные тестовые примеры для «взлома» материалов других участников во время конкурсов, вести блоги, чтобы делиться друг с другом методами и просматривать исходный код решений других. пользователи. Участникам, получившим достаточно высокий рейтинг, могут быть предоставлены дополнительные функции, такие как возможность добавлять теги к задачам и предлагать наборы задач для официальных конкурсов. |
| КодинИгра | Пазлы (возрастающей сложности), код гольфа . Проводит регулярные онлайн-соревнования (игры по программированию и задачи по программированию). |
| ХакерЗемля [17] | Компания из Бангалора , Индия, проводит онлайн-конкурсы, подобные среде, с целью предоставления решений по оценке персонала. |
| ХакерРанк | HackerRank предлагает задачи программирования в различных областях информатики. Здесь также проводятся ежегодные конференции Codesprint, которые помогают связать программистов и стартапы Кремниевой долины . |
| ЛитКод | LeetCode содержит более 2300 вопросов, охватывающих множество различных концепций программирования, и предлагает еженедельные и двухнедельные конкурсы. Задачи по программированию предлагаются на английском и китайском языках. |
| Проект Эйлера [18] | Большая коллекция задач вычислительной математики (т.е. не связанных напрямую с программированием, но для решения часто требующих навыков программирования). В отличие от других онлайн-судей, для отправки решений не требуется исходный код. Вместо этого каждая задача требует просто числового ответа (который обычно слишком велик, чтобы его можно было угадать или вычислить вручную), что позволяет пользователям использовать любые методы, которые они считают подходящими для решения задач, включая выбор или отказ от выбора языка программирования. |
| СЛОЖНЫЙ [17] | Польская онлайн-судейская система, которая доставляет массу проблем при обучении и предоставляет другим организаторам платформу для проведения своих соревнований по программированию. |
| Топкодер [19] [17] | Американский ресурс и компания, которая занимается организацией конкурсов, а также занимается промышленными задачами в качестве своего рода внештатной работы; Ежегодно он предлагает десятки коротких соревнований и несколько длинных («марафонов»). Особенность - участники имеют возможность проверить правильность решений других участников после этапа кодирования и перед финальным автоматическим тестированием (так называемая «фаза вызова»). |
| Онлайн-судья UVa [19] [17] | Содержит более 4500 задач для тренировки. Регулярно проводятся онлайн-соревнования. Открытый в 1995 году, это один из старейших подобных сайтов. |
Преимущества и критика
[ редактировать ]Участие в соревнованиях по программированию может повысить интерес учащихся к изучению информатики . Навыки, приобретенные на конкурсах по программированию типа ICPC, также улучшают перспективы карьерного роста, поскольку помогают пройти «технические собеседования», которые часто требуют от кандидатов решения сложных программных и алгоритмических задач на месте. [19] [20]
Конкурсное программирование также подвергалось критике, особенно со стороны профессиональных разработчиков программного обеспечения . [21] Одним из критических моментов является то, что многие быстро развивающиеся соревнования по программированию учат конкурентов плохим привычкам программирования и стилю кода (например, ненужному использованию макросов , отсутствию ООП- абстракции и комментариев, использованию коротких имен переменных и т. д.). [22] [21] Кроме того, конкурсы по программированию, такие как ICPC и IOI, предлагая только небольшие алгоритмические головоломки с относительно короткими решениями, не обязательно обучают хорошим навыкам и практикам разработки программного обеспечения, поскольку реальные программные проекты обычно состоят из многих тысяч строк кода и разрабатываются большими командами в течение длительного времени. периоды времени. [21] Питер Норвиг заявил, что, согласно имеющимся данным, победа в конкурсах по программированию отрицательно коррелирует с производительностью программиста на работе в Google (хотя у победителей конкурсов были более высокие шансы получить работу). [23] Позже Норвиг заявил, что эта корреляция наблюдалась на небольшом наборе данных, но не могла быть подтверждена после изучения более крупного набора данных. [24] [ ненадежный источник? ]
Еще одно мнение заключается в том, что вместо того, чтобы «тратить» свое время на чрезмерную конкуренцию путем решения проблем с помощью известных решений, высококлассные программисты должны скорее инвестировать свое время в решение реальных проблем. [21]
Литература
[ редактировать ]- Халим С., Халим Ф. (2013). Соревновательное программирование 3: Новая нижняя граница соревнований по программированию . Лулу.
- Лааксонен, А. (2017). Руководство по конкурентному программированию (темы бакалавриата по информатике). Чам: Международное издательство Springer.
- Сюй, X. (2020) Развитие, процветание и упадок олимпиады по информатике . Опубликовано в Интернете.
- Костка, Б. (2021). Спортивное программирование на практике. Университет Вроцлава.
См. также
[ редактировать ]Ссылки
[ редактировать ]- ^ «Google Код Джем» . гугл.com . Архивировано из оригинала 31 мая 2023 года . Проверено 20 февраля 2016 г.
- ^ «Спонсор TCO12: Google — TCO 12» . topcoder.com . Архивировано из оригинала 16 февраля 2012 года.
- ^ «Кубок хакеров Facebook» . Фейсбук . Проверено 20 февраля 2016 г.
- ^ Ли, Юцзя; Чой, Дэвид; Чунг, Джунён; Кушман, Нейт; Шритвизер, Джулиан; Леблон, Реми; Экклс, Том; Килинг, Джеймс; Гимено, Феликс; Лаго, Агустин Даль; Юбер, Томас; Чой, Питер; д'Отем, Сиприен де Массон; Бабушкин Игорь; Чен, Синьюнь (9 декабря 2022 г.). «Генерация кода уровня соревнований с помощью AlphaCode». Наука . 378 (6624): 1092–1097. arXiv : 2203.07814 . дои : 10.1126/science.abq1158 . ISSN 0036-8075 .
- ^ Кера, Вивек; Астрахан, Оуэн; Коц, Дэвид (1993). «Конкурс интернет-программирования» (PDF) . Бюллетень ACM SIGCSE . 25 (1): 48–52. дои : 10.1145/169073.169105 . ISSN 0097-8418 . Архивировано из оригинала (PDF) 8 августа 2017 года . Проверено 10 марта 2020 г.
- ^ Пак, Игорь. «Алгоритмы» . Математика 182 . Калифорнийский университет, Лос-Анджелес . Проверено 31 марта 2024 г.
- ^ Проблемы программирования (Скиена и Ревилла) ISBN 0387001638 , ISBN 978-0387001630
- ^ Костка, Бартош (2021). Спортивное программирование на практике (PDF) . Университет Вроцлава.
- ^ «Отпразднуйте соревнования Google по программированию финальным раундом веселья по программированию» . Блог разработчиков Google . Google . Проверено 28 февраля 2023 г.
- ^ «Code Jam — соревнования Google по программированию» . Соревнования по кодированию . Архивировано из оригинала 27 июня 2023 года . Проверено 26 февраля 2023 г.
- ^ «ИКПК» . icpc.global . Проверено 26 февраля 2023 г.
- ^ «Среда программирования – Документы ICPC» . Проверено 15 февраля 2024 г.
- ^ «ИКПК» . icpc.global . Проверено 26 февраля 2023 г.
- ^ «Олимпиады» . stats.ioinformatics.org . Проверено 26 февраля 2023 г.
- ^ «Meta Hacker Cup — 2022 — Отборочный раунд» . www.facebook.com . Проверено 26 февраля 2023 г.
- ^ «Часто задаваемые вопросы — Ратуша сообщества Topcoder с Дугом Хэнсоном, генеральным директором Topcoder» . Топкодер . Проверено 28 февраля 2023 г.
- ^ Jump up to: а б с д и ж Луиджи, Уильям Ди; Фарина, Габриэле; Лаура, Луиджи; Нанни, Умберто; Темперини, Марко; Версари, Лука (2016). «oii-web: интерактивное онлайн-программирование oii-web: интерактивная онлайн-система обучения для соревнований по программированию» (PDF) . Олимпиады по информатике . 10 : 207–222. дои : 10.15388/ioi.2016.13 . S2CID 6877554 .
- ^ Jump up to: а б Комбефис, Себастьян; Вотеле, Жереми (2014). «Тренинги по программированию и преподавание информатики посредством онлайн-конкурсов» (PDF) . Олимпиады по информатике . 8 : 21–34.
- ^ Jump up to: а б с д Блумфилд, Аарон; Сотомайор, Борха. «Руководство по стратегии соревнований по программированию» (PDF) . SIGCSE '16: Материалы 47-го технического симпозиума ACM по образованию в области компьютерных наук .
- ^ Джексон, Дин (1 декабря 2013 г.). «Техническое интервью Google. Как получить работу своей мечты» (PDF) . XRDS: Crossroads, журнал ACM для студентов . 20 (2): 12–14. дои : 10.1145/2539270 . S2CID 27549057 .
- ^ Jump up to: а б с д Смит, Дункан (2 декабря 2015 г.). «Дебаты о соревновательном программировании» .
- ^ Халим, Стивен. «CS3233 — Соревновательное программирование» . Школа вычислительной техники НУС .
- ^ «Победа на соревнованиях по программированию является негативным фактором для хорошей работы» . Ютуб . 5 апреля 2015 г.
- ^ «Дискуссия HN о корреляции между производительностью труда и конкурентным программированием» . декабрь 2020.