Олимпиады по программированию

Олимпиада по программированию (олимпиада по информатике) — интеллектуальное соревнование по решению различных задач на ЭВМ, для решения которых необходимо придумать и применить какой-либо алгоритм или программу на одном из языков программирования. Как правило участникам выдается комплект из нескольких задач. Задача считается решённой, если участники смогли составить программу, которая правильно работает на тестах, подготовленных жюри. Тесты участникам неизвестны.

Открытый чемпионат по спортивному программированию Яндекс.Алгоритм, 22 августа 2013 года.

Олимпиады бывают личные и командные. В командных олимпиадах обычно участвует 3 человека и им на всё время олимпиады предоставляется 1 компьютер для решения задач. Для проведения подобных соревнований используются специализированные программные турнирные системы.

ACM International Collegiate Programming Contest
Основная статья: Международная студенческая олимпиада по программированию

Крупнейшая международная студенческая командная олимпиада по программированию — ACM International Collegiate Programming Contest. Генеральными спонсорами чемпионата выступают такие компании как Microsoft и IBM. В 2004 году в ней участвовало 3150 команд из 75 стран.

Команды из России неоднократно становились победителями этого престижного соревнования[1][2][3][4][5]. По итогам удачных выступлений команды удостаивались встречи с Президентом РФ[6][7][8]. Один из тренеров и организаторов этих олимпиад в России был награждён Премиями Президента РФ и Правительства РФ в области образования[9].

Олимпиады в СССР и России

Среди школьников

Первая олимпиада по программированию среди школьников г. Москвы прошла в 1981 году (на ней было всего 4 участника), а первая олимпиада в СССР (под названием олимпиада по информатике) прошла среди школьников и состоялась в 1988 году в Свердловске[10]. В дальнейшем олимпиады по информатике стали частью всесоюзных (а после распада СССР — всероссийских) предметных олимпиад школьников.

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

Перечневые олимпиады

Каждый год Российский Совет Олимпиад Школьников (РСОШ) составляет специальный перечень олимпиад, в числе которых могут находиться и личные олимпиады по спортивному программированию. Такие соревнования всегда проходят в два этапа: отборочный (онлайн) и заключительный (очно, но допускались исключения из-за пандемии COVID-19). Правом проведения перечневых олимпиад обладают только органы власти в сфере образования и высшие учебные заведения.[11]

Высокие результаты, показанные на таких олимпиадах, могут давать некоторые привилегии при поступлении в вуз, в том числе поступление без вступительных испытаний или округление результатов ЕГЭ по информатике до 100 баллов (если школьник набрал хотя бы 75 баллов).

Командные соревнования школьников

Также проводятся многоуровневые командные олимпиады среди школьников, по правилам аналогичным правилам международных студенческих олимпиад[12][13].

Самой известной командной олимпиадой является Всероссийская командная олимпиада школьников по программированию[14] (ВКОШП). Она обычно проводится в начале декабря в разных городах России: Санкт-Петербург, Барнаул и городах в других странах. На эту олимпиаду нужно отобраться в своем регионе, от Москвы обычно проходят 10—20 команд, от Санкт-Петербурга — чуть меньше[15].

Студенты

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

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

Олимпиады в Белоруссии

Олимпиады среди школьников

В Белоруссии олимпиады по программированию (по информатике) среди школьников проходит в несколько этапов.

Первый этап — внутришкольная олимпиада. Проводится среди учеников конкретного учреждения образования. В результате соревнования, победители проходят на следующий этап. Для проведения таких олимпиад используются системы тестирования (турнирные системы). Какую именно систему использовать решают организаторы олимпиады. Например, в Бресте используется система Brain Training, в некоторых заведениях система eJudge.

Второй этап — муниципальная олимпиада (иногда её называют городской). Такая олимпиада проводится среди победителей предыдущего этапа, представленных каждой школой определённого района города. Например, в Бресте проводятся две районные олимпиады: для Московского и Ленинского района. Победители от каждого района проходят на следующий этап. Обязательные условия для продолжения участия в олимпиаде (переход на следующий этап) — набрать более 50 % возможных баллов (в 2014—2015 учебном году это правило отменено).

Третий этап — областная олимпиада. Здесь принимают участие победители предыдущего этапа (районной олимпиады). Вся Белоруссия разделена на 6 областей (Брестская, Витебская, Могилёвская, Гродненская, Гомельская и Минская), а также город Минск. Кроме того, в качестве отдельной команды выступает ГУО «Лицей Белорусского государственного университета». В каждой из них происходит отбор участников на следующий этап олимпиады.

Четвёртый этап — республиканская олимпиада (заключительный этап). Победители областных олимпиад соревнуются за звание лучшего программиста среди школьников.

Лучшие участники республиканской олимпиады (обычно только из 9-11 классов), отбираются на сборы по подготовке к международной олимпиаде по информатике. В течение сборов из них отбирается окончательная команда.

Другие известные соревнования

В последнее время появился более общий термин «спортивное программирование». Состязания по спортивному программированию не связаны напрямую с системой образования, то есть в них также принимают участие и профессиональные программисты. Популярное состязание по спортивному программированию в мире — ресурс TopCoder, на котором регулярно проводят раунды (SRM), по результатам которых формируется рейтинг участников, а также ежегодный TopCoder Open. Появившийся позднее российский ресурс Codeforces также проводит регулярные раунды[9], по результатам которых формируется свой рейтинг. В конце 2021 года в России набрала популярность платформа Sort Me, ежемесячно проводящая Sort Me Round[16] по модифицированным правилам ACM[17].

Крупные ИТ-компании проводят регулярные и как правило личные соревнования по программированию, среди таковых — Google Code Jam, Facebook Hacker Cup, Russian Code Cup.

Задачи

На классических олимпиадах по программированию участникам предлагается некоторый набор задач различного уровня сложности. Решением задачи является программа, написанная на одном из допустимых языков программирования. Эта программа должна корректно считывать любые входные данные указанного формата из определённого входного потока, корректно обрабатывать их согласно условию задачи, и выводить в определённый выходной поток в указанном виде. Для ввода-вывода могут использоваться как стандартные консольные потоки, так и файловые (часто входной файл имеет имя «input.txt», а выходной — «output.txt»).

Все решения проверяются автоматизированной тестирующей системой. Она запускает каждое решение на некотором наборе тестов. После завершения работы программы она оценивает правильность полученных выходных данных — сравнивает с эталонными или производит более сложные действия. Участнику неизвестна большая часть входных данных, поэтому, если тестирующая система сообщает ему, что на одном или нескольких тестах программа отработала неправильно, он должен самостоятельно догадаться, где ошибка.

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

Авторы стараются подбирать входные данные таким образом, чтобы время работы неэффективного решения во много раз превышало установленный лимит, что исключает влияние на результат различий в характеристиках процессора, погрешности измерений, влиянии Turbo Boost и других факторов. При этом замеряется процессорное, а не реальное время выполнения, так что загруженность процессора тестирующего сервера другими задачами так же не должна повлиять на результат.

Особенностью олимпиадных задач является художественность их условия. В условиях редко ведётся речь о структурах данных и алгоритмах, приводящих к решению. Чаще условие задачи представляет собой короткий рассказ со своим сюжетом, героями и конфликтом. Таким образом, чтобы решить олимпиадную задачу, нужно предварительно составить математическую модель событий, и уже по ней подобрать или построить подходящий алгоритм. Алгоритм может быть как одним из уже известных алгоритмов, так и абсолютно новым, непохожим на другие.

Пример классической простейшей задачи, часто используемой для пробного тура: A+B.

Примечания
  1. SnarkNews
  2. Чемпионы мира из ИТМО в новостях РЕН ТВ :: :: Видео на RuTube (недоступная ссылка)
  3. В Петербурге открылась академия программирования — Наталья Шергина — «Чемпионы мира получили кластер» — Российская Газета — В Северной столице открылась …
  4. Студенты ИТМО стали чемпионами мира по программированию
  5. Дмитрий Медведев встретился с победителями чемпионата мира по программированию — Первый канал
  6. Президент сегодня встретился со студентами — победителями чемпионата мира по программированию — Первый канал
  7. Президент России Дмитрий Медведев продолжит традицию встреч с российскими студентами-победителями Чемпионата мира по программированию среди сборных команд вузов. — РИА Новости …
  8. Три золотых медали привезли в РФ победители первенства планеты по программированию — Первый канал
  9. Станкевич Андрей Сергеевич (недоступная ссылка)
  10. Олимпиады — История олимпиады (недоступная ссылка). Дата обращения: 9 сентября 2011. Архивировано 10 августа 2011 года.
  11. Порядок проведения олимпиад школьников. Российская газета. Дата обращения: 25 января 2022.
  12. Уральская региональная олимпиада по программированию (недоступная ссылка). Центр классического образования УрФУ им. Б. Н. Ельцина (УрГУ). Дата обращения: 9 ноября 2011. Архивировано 6 октября 2010 года.
  13. Олимпиады по информатике. Санкт-Петербург, Россия.
  14. Олимпиады по информатике. Санкт-Петербург, Россия. neerc.ifmo.ru. Дата обращения: 27 июля 2016.
  15. SN on ВКОШП - 2015 (англ.). vkoshp2015.snarknews.info. Дата обращения: 27 июля 2016.
  16. sort-me.org - Resource - CLIST. clist.by. Дата обращения: 25 января 2022.
  17. Sort Me, Sort Me. Правила Sort Me Round. Teletype (24 октября 2021). Дата обращения: 25 января 2022.

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.