Чемпионат мира по программированию

 

                  В.А.Каймин, Электронный Университет WDU

                 

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

            Первые московские олимпиады по программированию для студентов начали проводиться в начале 80-ых годов на базе ведущих московских вузов - МЭСИ, МИЭМ и МИСИС. Первые наши олимпиады по программированию были лично-командными. Победителями олимпиад объявлялись лучшие студенты и лучшие вузовские команды.

            Первыми победителями московских олимпиад были Борис и Сергей Нуралиевы, ставшие позже основателями фирмы 1С и разработчиками бухгалтерских программ, и команда студентов МИЭМ, куда входили Тэтюхин Михаил и Тютюнников Николай, создавшие первый офисный пакет для отечественных IBM-совместимых компьютеров.

            В московских олимпиадах по программированию студентам предлагался набор из 5-6 задач, которые должны были решены на ЕС ЭВМ за 3 или 4 часа времени. Для решения задач на ЭВМ использовались языки программирования Фортран, ПЛ/1 или Паскаль - по выбору участников.

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

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

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

             Анализ работ участников олимпиад показал, что практически все победители для написания программ на языках Фортан и ПЛ/1 применяли принципы структурного программирования и многие из них использовали структурный псевдокод для записи алгоритмов.

            В США в начале 80-ых годах американская ассоциация АСМ начала проводить национальные командные чемпионаты по программированию среди студенческих команд, которые со временем превратились в международные соревнования и получили название - Чемпионат мира по программированию.

            Чемпионат мира по программированию проходит в 3 тура по континентальным и национальным регионам. На финальный всемирный тур съезжаются команды-победители региональных турниров с всех континентов - Европы, Америки, Азии, Австралии и Африки.

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

            Студенческие команды состоят из трех человек, которым во время соревнований предоставляется компьютер и набор от 5 до 10 задач, которые должны быть решены на ЭВМ за 5 или 6 часов времени.

            На чемпионатах по программированию для решения задач на ЭВМ с 2000 года разрешается использовать языки програм­мирования Паскаль, С/С++ или Java. До 2000 года на чемпионатах мира по программированию разрешалось использовать язык програм­мирования Quick Basic.

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

            Типология ошибок, принятая на чемпионатах по программированию:

            1) синтаксические ошибки;

            2) ошибки выполнения программ ( пример - деление на 0 );

            3) неправильные результаты;

            4) превышение лимита времени.

            В России командные чемпионаты по программированию начали проводиться в 1995 году в Петербурге, где ныне проводится Северо-Восточный полуфинал Чемпионата мира. Четвертьфинальные соревнования чемпионата мира проводятся в Москве, Петербурге, Екатеринбурге, Петрозаводске и Владивостоке.

            В 2000 году команда студентов Санкт-Петербургского университета впервые стала чемпионом мира по программированию, а в 2001 году команда СПбГУ вновь стала чемпионом мира по программированию.

            В 2002-2003 годах команды Московского Университета, Петербургского института точной механики и оптики получили Золотые медали Чемпионата, а команда Саратов­ского университета - Серебряные медали Чемпионата мира по программированию, а чемпионами мира стали студенты Варшавского университета.

            Удивительно, но последние годы команды американских университетов не поднимаются выше 10 места. За места в первой десятке лучших студенческих команд программистов в чемпионатах мира соревнуются команды из России, Восточной Европы и Китая.

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

            За повторные пуски программ на чемпионатах по программированию начисляются штрафные очки, которые равны времени получения результата от начала турнира и тем самым существенно влияют на распределение мест при равном числе решенных задач.

            Победителями турниров становятся те, кто решит на ЭВМ наибольшее число задач за наименьшее число пусков. Существенное конкурентное преимущество имеют те студенты и команды, которые умеют составлять программы практически без ошибок.

            Напомним определения из теории программирования:

            1) Программа содержит ошибки, если можно указать такие исходные данные (тесты), при которых она даст сбой отказ или неправильные результат.

            2) Результат решения - правильный, если он отвечает требованиям поставленной задачи при имеющихся исходных данных.

            3) Программа не содержит ошибок, если она дает правильные результаты для любых допустимых исходных данных.

            В конкурсных задачах на чемпионатах по программировании. приводятся не только исходные условия задач, но и образцы тестов - перечень конкретных исходных данных с соответствующими правильными результатами.

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

            Данные требования к приемке программ приняты в настоящее время ведущими фирмами IBM и Microsoft, являющихся мировыми лидерами в промышленной разработке программного обеспечения и одновременно - основными спонсорами чемпионатов мира по программированию.

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

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

            Подготовка к участию в олимпиадах и турнирах чемпионата мира по программированию может проводиться дистанционно с использованием сети Интернет. Для этого вузы-организаторы олимпиад открывают виртуальные турниры, доступные через Интернет.

            Виртуальные турниры начинаются с регистрации участников и ознакомления их с условиями участия в турнирах через Интернет. После регистрации участники получают доступ к текстам задач и к системе автоматического тестирования программ, которая будет проверять правильность создаваемых ими программ.

            Главная проблема - научиться составлять алгоритмы и программы практически без ошибок и научится проводить исчерпывающие анализ их правильности. Такого рода усовершенствованные методы разработки программ были созданы в начале 70-х годов и до сих пор используются на фирме IBM.

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

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

            Статистика IBM показала, что использование усовершенствованных методов в 10 раз уменьшает число ошибок в программах с 2-3 ошибок на 100 операторов до 2-3 ошибок на 1000 операторов.  Иными словами программы размером в 200-300 операторов по методике IBM создаются практически без ошибок.

            Опыт использования методики IBM показывает, что остаточные ошибки носят как правило логический характер - ошибки в постановке задачи, ошибки в выбранном методе решения, неправильная организация ввода-вывода данных и т.п. Ошибки в реализации алгоритмов и программ выявляются при сверке их текстов.

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

            Студенты МИЭМ, участвовавшие и побеждавшие в студенческих олимпиадах по программированию в 80-х годах, были обучены не только систематическим методам разработки программ для ЭВМ, но и систематическим методам анализа их правильности. Позже они создали самые первые пакеты учебных программ для школьных ЭВМ.

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

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

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

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

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

            Примеры конкурсных задач чемпионатов и олимпиад по программированию для студентов и школьников можно найти в Интернет в электронном учебнике “Информатика” в библиотеке Электронного Университета:  http://wdu.da.ru