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

Олимпиада по программированию — интеллектуальное соревнование по решению различных задач на ЭВМ, для решения которых необходимо придумать и применить какой-либо программу и/или алгоритм на одном из языков программирования.

Олимпиады по программированию проводятся с целью выявления наиболее талантливых и способных людей в области программирования, а также пробуждения интереса к программированию.

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

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

• Районная олимпиада;
• Городская олимпиада;
• Республиканская или областная олимпиада;
• Окружная олимпиада;
• Всероссийская олимпиада;
• Международная олимпиада;

Участие в данных олимпиадах и хорошие результаты показанные на них могут давать некоторые привилегии при поступлении в вуз. Участие в олимпиаде по программированию считается успешным, если участники смогли составить программу и проверить ее на ЭВМ на тестах, предоставленных жюри. Решение задачи считается правильным, если ЭВМ дает правильные результаты на (всех) тестах жюри. Алгоритм (программа) содержит ошибки, если на некоторых тестах ЭВМ дает сбои, отказы или неправильные результаты. Победители олимпиад составляют алгоритмы и программмы практически без ошибок.

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

Крупнейшая международная студенческая командная олимпиада по программированию называется ACM International Collegiate Programming Contest. В 2004 году в ней участвовало 3150 команд из 75 стран. Крупнейшее технологическое соревнование, кубок технологий Imagine cup организуется при поддержке компании

В последнее время начал циркуляцию также более общий термин «спортивное программирование». Состязания по спортивному программированию не связаны напрямую с системой образования, то есть в них также принимают участие и профессиональные программисты. Самые популярные состязания по спортивному программированию в мире — это конкурс Test-The-Best

Ещё один вид соревнований проводится на сайте http://zcontest.ru. Каждую весну начиная с 2005 года, на длительный промежуток времени (обычно месяц) выкладывается набор задач повышенной сложности. Решения прнимаются и анализируются автоматической системой SPOJ. Особенностью соревнования является, то, что для большинства задач, количество очков набранных участниками зависит от эффективности решения. Официальный язык соревнования русский. Поддерживаются большинство существующих языков программирования (C/C++, С#, Pascal, Lisp, Brainfuck). Участие свободное, никаких специальных ограничений на уровень образования участников не налагается.

Задачи

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

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

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

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

Классификация задач

Участниками олимпиад и членами жюри часто вводится неофициальная классификация задач олимпиадного программирования. Это связано с тем, что, несмотря на различие сюжетов, алгоритмы и структуры данных, используемые для решения задач часто похожи друг на друга и их можно разделить на несколько категорий. Категории обычно носят названия классов алгоритмов или соответствующих разделов математики. Необходимо отметить, что всегда возможно придумать задачу, не относящуюся ни к одной из категорий. Для этого вводят категорию «Разное». Кроме того, одна и та же задача может входить сразу в несколько разделов.

• Пробная задача
• Утешительная задача
• Эмуляция
• Теория чисел
• Комбинаторика
• Теория вероятностей
• Теория игр
• Теория графов
• Длинная арифметика
• Динамическое программирование
• Двоичный поиск
• Жадный алгоритм
• Линейное программирование
• Структуры данных
• Работа со строкой
• Последовательности
• Полный перебор
• Оптимизация
• Физика
• Вычислительная геометрия
• Разное

На каждую категорию можно придумать задачи самого разного уровня сложности. Поэтому факт отнесения задачи к одной из категорий не может свидетельствовать о её сложности.

См. также

• Международный конкурс запутанного кода на C (англ. International Obfuscated C Code Contest)
• Международная олимпиада по информатике
• Киевские олимпиады по информатике

Ссылки

• [1] - IT 2007. Международный турнир по программированию среди школьников
• [2] - АС Олимпиада 3.0
• [3] — Сайт Северо-Восточного полуфинала Чемпионата мира по программированию среди студентов.
• [4] — Архив школьных олимпиад по информатике в Санкт-Петербурге.
• [5] — Московская олимпиада по информатике. Летняя компьютерная школа.
• [6] — Московская областная олимпиада по информатике. Архив личных и командных олимпиад, библиотека.
• [7] — CHASOLIMP - международные дистанционные олимпиады проекта "Олимпиады: подготовка и проведение" на русском языке
• [8] — Белорусские олимпиады по информатике.
• [9] — Украинские олимпиады по информатике.
• [10] — Test-The-Best. Регулярно проходящие конкурсы по спортивному программированию. Лента новостей спортивного программирования. Архив задач. (Заброшен. Больше не работает.)
• [11] — Портал олимпиадного движения Таганрогского государственного радиотехнического университета. Имеется архив задач с возможностью онлайн-проверки.
• [12] — Раздел на сайте НГУ, посвященный проводимым там школьным и студенческим олимпиадам; можно найти архив задач прошлых лет и порешать их.
• [13] — Сайт МГУ, посвященный олимпиадам по программированию
• [14] — Сайт МФТИ, посвященный олимпиадам по программированию
• [15] — Сайт УрГУ, посвященный олимпиадам по программированию, большой архив задач
• [16] — Сайт ЮУрГУ, посвященный олимпиадам по программированию, большой архив задач, архив олимпиад
• [17] — Сайт XVIII Всероссийской олимпиады школьников по информатике (2006 г.)
• [18] — Сайт XIX Всероссийской олимпиады школьников по информатике (2007 г.)
• [19] — Сайт IOI 2006 (Всемирная олимпиада по информатике), которая пройдет в августе в Мексике
• [20] — Сайт IOI, если подняться вверх по разделам, то вообще всех всемирных олимпиад.
• [21] — Тоже сайт IOI
• [22] — Проект ТопКодер. Включает в себя множество олипиад в том числе и по программированию
• [23] — Ежегодный открытый Зеленоградский турнир по программированию. Участие свободное. Проводится каждую весну с 2005 года.
• [24] — Сайт турнирной системы Contester, которая позволяет проводить тренировки по программированию и организовывать соревнования. В дистрибутив входит несколько задач.

Внешние ссылки

• Интернет олимпиады по информатике и программированию (Всероссийские и городские интернет олимпиады для школьников 7-11 классов по информатике и программированию в СПбГУ ИТМО. Положения, сроки проведения, примеры типовых задач и регистрация участников.)