Соревновательное программирование или спортивное программирование — это интеллектуальный вид спорта, в котором участники пытаются программировать в соответствии с предоставленными спецификациями. Соревнования обычно проводятся через Интернет или локальную сеть . Соревновательное программирование признано и поддерживается несколькими многонациональными программными и интернет -компаниями, такими как Google , [1] [2] и Meta . [3]
Соревнование по программированию обычно включает в себя представление ведущим набора логических или математических задач , также известных как головоломки или задачи, участникам (число которых может варьироваться от десятков или даже сотен до нескольких тысяч). Участники должны написать компьютерные программы, способные решать эти задачи. Судейство в основном основывается на количестве решенных задач и времени, потраченном на написание успешных решений, но может также включать другие факторы (качество полученного вывода, время выполнения, использование памяти, размер программы и т. д.).
Одним из старейших известных соревнований является Международный студенческий чемпионат по программированию (ICPC), который возник в 1970-х годах [4] и расширился до 88 стран в своем выпуске 2011 года.
С 1990 по 1994 год Оуэн Астрахан , Вивек Кхера и Дэвид Коц провели одно из первых распределенных интернет-соревнований по программированию, вдохновленное ICPC. [5]
Интерес к спортивному программированию значительно вырос с 2000 года и достиг десятков тысяч участников (см. Известные соревнования), и тесно связан с развитием Интернета, который позволяет проводить международные соревнования в режиме онлайн, устраняя географические проблемы.
Целью соревновательного программирования является написание исходного кода компьютерных программ, которые способны решать заданные задачи. Подавляющее большинство задач, появляющихся на соревнованиях по программированию, имеют математический или логический характер. Обычно такие задачи относятся к одной из следующих категорий: комбинаторика , теория чисел , теория графов , алгоритмическая теория игр , вычислительная геометрия , анализ строк , дискретная математика и структуры данных . [6] Задачи, связанные с программированием в ограничениях и искусственным интеллектом, также популярны на некоторых соревнованиях.
Независимо от категории проблемы, процесс решения проблемы можно разделить на два основных этапа: построение эффективного алгоритма и реализация алгоритма на подходящем языке программирования (набор допустимых языков программирования варьируется от конкурса к конкурсу). Это два наиболее часто проверяемых навыка на соревнованиях по программированию.
В большинстве конкурсов оценка производится автоматически хост-машинами, обычно называемыми судьями. Каждое решение, представленное участником, запускается на судье против набора (обычно секретных) тестовых случаев. Обычно конкурсные задачи имеют систему оценок «все или ничего», что означает, что решение «принимается», только если оно дает удовлетворительные результаты во всех тестовых случаях, запущенных судьей, и отклоняется в противном случае. Однако некоторые конкурсные задачи могут допускать частичную оценку, в зависимости от количества пройденных тестовых случаев, качества результатов или некоторых других указанных критериев. В некоторых других конкурсах требуется, чтобы участник только предоставил выходные данные, соответствующие заданным входным данным, и в этом случае судья должен проанализировать только предоставленные выходные данные.
Онлайн-судьи — это онлайн-среды, в которых происходит тестирование. Онлайн-судьи имеют списки рангов, показывающие пользователей с наибольшим количеством принятых решений и/или наименьшим временем выполнения для конкретной проблемы. [7]
В большинстве из вышеперечисленных конкурсов соревнования обычно организуются в несколько туров. Обычно они начинаются с онлайн-раундов, которые завершаются финальным туром на месте. Лучшие участники IOI и ICPC получают золотые, серебряные и бронзовые медали. В других конкурсах лучшим участникам вручаются денежные призы. Конкурсы также привлекают интерес рекрутеров из многочисленных компаний, занимающихся разработкой программного обеспечения и Интернета, которые часто обращаются к конкурентам с потенциальными предложениями о работе.
Сообщество программистов по всему миру создало и поддерживает несколько интернет-ресурсов, посвященных спортивному программированию. Они предлагают отдельные конкурсы с небольшими призами или без них. Пользователям обычно присваивается рейтинг на основе их результатов в указанных конкурсах. Архивы прошлых задач являются популярными ресурсами для обучения спортивному программированию. Существует несколько организаций, которые регулярно проводят соревнования по программированию. К ним относятся:
Участие в соревнованиях по программированию может повысить энтузиазм студентов к изучению компьютерных наук . Навыки, приобретенные в соревнованиях по программированию, подобных ICPC, также улучшают карьерные перспективы, поскольку они помогают пройти «технические собеседования», которые часто требуют от кандидатов решения сложных программных и алгоритмических задач на месте. [19] [20]
Также имело место критика соревновательного программирования, особенно со стороны профессиональных разработчиков программного обеспечения . [21] Одним из критических моментов является то, что многие быстро развивающиеся соревнования по программированию прививают участникам плохие привычки программирования и стиль кода (например, ненужное использование макросов , отсутствие абстракции ООП и комментариев, использование коротких имен переменных и т. д.). [22] [21] Кроме того, предлагая только небольшие алгоритмические головоломки с относительно короткими решениями, соревнования по программированию, такие как ICPC и IOI, не обязательно обучают хорошим навыкам и практикам разработки программного обеспечения, поскольку реальные программные проекты обычно содержат тысячи строк кода и разрабатываются большими командами в течение длительных периодов времени. [21] Питер Норвиг заявил, что на основе имеющихся данных победа в соревнованиях по программированию отрицательно коррелирует с производительностью программиста на его работе в Google (хотя у победителей соревнований были более высокие шансы получить работу). [23] Позже Норвиг заявил, что эта корреляция наблюдалась на небольшом наборе данных, но что ее нельзя было подтвердить после изучения большего набора данных. [24] [ ненадежный источник? ]
Еще одно мнение заключается в том, что вместо того, чтобы «тратить» свое время на излишнюю конкуренцию, решая проблемы с известными решениями, высококлассные программисты должны вместо этого вкладывать свое время в решение реальных проблем. [21]