Александр Силонов
28 февраля в Атланте состоялся финал очередного командного чемпионата мира по программированию среди студентов, проводимого международной ассоциацией ACM. На этот раз результаты чемпионата продемонстрировали безусловное превосходство восточноевропейской системы подготовки программистов перед американской. Никогда еще российские команды не были так близки к успеху...
Из истории Чемпионатов
В 1947 г. сотрудники Пенсильванского университета - создатели первого в мире компьютера ENAC - основали организацию ACM (Association for Computing Machinery, Ассоциация по компьютерному оборудованию) с целью координации деятельности мирового компьютерного сообщества. В настоящее время это самая авторитетная международная организация в компьютерном мире, насчитывающая более 80 тыс. членов - ученых, инженеров и программистов со всего света. ACM издает книги и периодику, организует конференции, присуждает награды за достижения в области информационных технологий; в ее рамках действуют специальные группы по интересам (Special Interests Groups, SIGs). В числе прочего ассоциация проводит среди студентов технических вузов командные чемпионаты мира по программированию - ACM International Collegiate Programming Contests. Идея таких чемпионатов возникла в 1970 г., а первые финальные состязания прошли в 1977 г. Директором чемпионата на протяжении последних десяти лет был профессор университета Бейлор (шт. Техас) Билл Паучер.
Большую часть затрат на проведение соревнований берет на себя генеральный спонсор. В течение четырех лет (финалы 1994 - 1997 гг.) таким спонсором была корпорация Microsoft, в прошлом году эстафету на пятилетний срок приняла IBM.
Желающих участвовать в чемпионате очень много, поэтому соревнования проходят в два этапа. Команды, занявшие первые три места на региональных соревнованиях первого этапа, обычно проходящих осенью, затем встречаются в феврале следующего года на втором, финальном этапе, в ходе которого определяются чемпионы мира, Северной Америки и Европы.
За годы спонсорства Microsoft число команд, участвовавших в региональных соревнованиях, увеличилось с 500 до 1000, число финалистов - с 32 до 50. Всего Microsoft выделила около 27 млн. долл. на организацию соревнований и призы победителям.
Поначалу в чемпионате участвовали в основном команды из вузов США и Канады, а остальной мир был представлен одной европейской региональной группой. Затем американцев стали теснить. Заметный рост числа региональных групп из восточного полушария начался в 1990 г. Именно тогда в финале впервые победила не североамериканская команда: чемпионами мира стали программисты из университета Отаго (Новая Зеландия); пятое место заняла команда Технического университета г. Эйндховена (Нидерланды). В 1991 г. первое место досталось австралийцам - сборной Мельбурнского университета, в 1994 г. - команде университета Ватерлоо (Канада), а в 1995 г. чемпионами наконец становятся европейцы - студенты университета Альберта-Людвига из немецкого города Фрайбурга, третье место - у сборной Технического университета голландского города Дельфта. Правда, через год европейцам (сборной Софийского университета) досталось лишь четвертое место. В финале прошлого года американцы - сборные Харвей-Мадд - Колледжа и Вашингтонского университета - завоевали соответственно первое и второе места, третьим был Квинслендский университет (Австралия), четвертым - Национальный университет Тайваня, пятым - уже упомянутый университет Ватерлоо, на шестом месте - шведский университет Умео, на седьмом - словацкий университет Комениуса; восьмой результат - у сборной Санкт-Петербургского государственного университета.
Чемпионаты ACM и Россия
Командный чемпионат мира по формуле ACM попал в поле зрения россиян лишь в 1993 г., тогда же были созданы первые команды. Интересно, что главные силы наших молодых программистов оказались сосредоточены не в Москве, а в Северо-Западном регионе. Так, именно СПбГУ и Санкт-Петербургский государственный институт точной механики и оптики (СПбГИТМО) выставляют на региональные соревнования по нескольку весьма успешно выступающих сборных. Помимо традиционно мощной системы обучения в школах и вузах, сказался и личный вклад в подготовку команд Владимира Парфенова, руководителя первой сборной СПбГИТМО, и Антона Суханова, бывшего тренера этой команды, ныне работающего в г. Редмонде в Microsoft. Своими успехами студенты отчасти обязаны и местным спонсорам - фирмам “Ингресс”, “Ланк” и “Ниеншанц”, предоставившим вычислительную технику для проведения региональных этапов чемпионата и оплативших авиабилеты для поездки на финальные состязания.
Значительный программистский потенциал сосредоточен также на Урале: екатеринбургские вузы традиционно представляют по нескольку сильных команд на региональных этапах чемпионата, в нынешнем году сборная Уральского государственного университета вышла в финал.
А первой российской командой, участвовавшей в полуфинальных соревнованиях, была сборная СПбГУ, выступившая в 1993 г. в Восточно-Европейском регионе. В финал чемпионата ACM наши соотечественники впервые пробились лишь в 1996 г. Тогда же успешное выступление команды СПбГУ в Амстердаме на полуфинальных соревнованиях побудило Билла Паучера создать отдельную российскую региональную группу.
Как проходит соревнование
Состязающиеся команды собираются в одном большом зале, каждая получает свой компьютер (один на троих участников) с предустановленным и протестированным программным обеспечением - заранее заказанным инструментарием для разработки программ и средством для обмена информацией с жюри. Аппаратная конфигурация у всех компьютеров одна и та же (в Атланте это были машины производства IBM с процессором Pentium II-233, 96 Мбайт ОЗУ и 2 Гбайт жестким диском), все они объединены в локальную сеть (на региональных состязаниях в России применялась ОС Novell NetWare, в Атланте - NT 4.0). В том же зале отводится место для распорядителей соревнования и для зрителей. На большие экраны проецируется таблица с текущими результатами участников, выдаваемыми специальной программой-монитором. Ту же таблицу команды могут увидеть на своих компьютерах, а зрители - на установленном в зале терминале.
Студенты СПбГУ были так близки к успеху!
Команды получают по конверту с тремя экземплярами заданий (дается шесть - восемь заданий, каждому из которых присваивается своя буква и свой цвет). Как правило, выполнение заданий требует солидной математической подготовки и умения нетривиально мыслить. Одна задача обычно бывает достаточно простой, чтобы в активе каждой команды был хотя бы один плюс, а две отличаются повышенной сложностью - их решение под силу лишь очень одаренным студентам. По сигналу конверты разрешается вскрыть, и программисты приступают к работе. Соревнование длится пять часов. Побеждает команда, правильно решившая за этот срок максимальное число задач. Если таких команд оказывается несколько, победительницей становится та, что затратила на решение минимальное время (набрала меньше штрафных минут).
Решив очередную задачу, т. е. написав очередную программу, команда через сеть посылает исходный текст (код) судьям - опытным программистам. Те производят компиляцию присланного текста и построение задачи, а затем прогоняют полученную программу через соответствующий набор тестов (состав и характер этих тестов - строжайший секрет организаторов чемпионата). Если все перечисленные операции прошли удачно, жюри тем же способом возвращает команде положительный ответ, после чего к столику команды прикрепляют воздушный шарик, цвет которого соответствует решенной задаче. Таким образом и состязающиеся, и зрители получают наглядную картину соотношения сил команд и распределения задач по сложности (в первую очередь решаются самые простые задачи).
Если жюри присылает негативный ответ, причиной этого может быть либо ошибка компиляции (невозможность получить исполняемый файл из исходного текста), либо ошибка при выполнении какого-либо из тестов (программа выдала неправильный или неверно оформленный результат, завершила работу с ненулевым кодом возврата или превысила установленный лимит времени выполнения). Надо сказать, что жюри также изредка допускает ошибки: участники жалуются, что одно и то же решение может быть признано сначала ошибочным, а затем - правильным, что стоит команде и времени, и нервов.
Единого способа оптимально организовать решение восьми задач силами трех программистов нет. Участники-ветераны и их тренеры разработали несколько стратегий поведения: можно навалиться всем сразу на одну задачу, потом на другую и т. д.; можно поделить задачи между всеми тремя участниками, наделенными одинаковыми функциями; можно выделить в команде одного “математика” и двух “кодировщиков” или “диктатора” и “подчиненных”, и т. п.
Теоретически соревнующиеся могут решать задачи, используя любой язык программирования и инструментарий, но, насколько мне известно, в действительности спонсоры накладывают свои ограничения: пока чемпионат проходил под эгидой Microsoft, средства разработки программ приходилось выбирать из продуктов этой фирмы, то же самое повторяется и с приходом эпохи спонсорства IBM. В Атланте команды пользовались версиями пакета Visual Age для различных языков.
Важной особенностью чемпионатов является повсеместное использование английского языка: на нем сформулированы задачи, на нем происходит все общение между командами и организаторами. Для многих иностранных участников это представляет трудность (к примеру, в финале 1997 г. сборная МГУ из-за проблем с английским получила немало штрафных минут). Учитывая это, организаторы в нынешнем году старались сформулировать условия задач как можно более компактно и просто, чтобы компенсировать языковое неравенство студентов из разных стран.
Еще одно существенное ограничение: ни один участник не может выступать в финалах чемпионата ACM более двух раз. Это способствует вовлечению в соревнование большего числа молодых программистов и позволяет по степени стабильности результатов того или иного вуза на протяжении многих лет оценить силу стоящей за ним школы.
Финал 22-го Чемпионата
К нынешнему году популярность мирового чемпионата достигла небывалого размаха: на первом, осеннем этапе соревновалось 1250 команд в 21 региональной группе (существует пять европейских групп, одиннадцать североамериканских, одна южноамериканская, две азиатско-тихоокеанские и по одной в Австралии и Новой Зеландии). К финалу пробились 54 команды, из них только 25 - из вузов США.
Россияне были представлены четырьмя командами: сборными СПбГУ, СПбГИТМО, МГУ (на базе мехмата) и Уральского государственного университета (г.Екатеринбург). Проведенное мною неофициальное анкетирование позволило установить, что в среднем возраст российских участников - 19 лет, стаж программирования - семь лет, число освоенных языков программирования - семь; на вопрос, рассчитывают ли они строить свою программистскую карьеру на Родине, почти все ответили утвердительно.
Местом проведения финальных соревнований была выбрана столица американского штата Джорджия Атланта (до сих пор название этого города в сочетании с аббревиатурой IBM и словом “соревнование” у многих ассоциировались лишь с не очень удачным опытом Голубого гиганта в информационном обеспечении Олимпийских игр 1996 г.; но на сей раз в качестве спонсора чемпионата ACM корпорация оказалась на высоте). Состязания и часть сопутствующих мероприятий проходили в сорокапятиэтажном здании отеля “Мариотт-Маркиз” в деловом центре города, там же разместились и все, кто имел отношение к чемпионату.
Официальные мероприятия заняли три дня. 26 февраля IBM провела презентации рекламного характера, представление своих новых продуктов и встречи студентов и тренеров с программистами и инженерами корпорации, в том числе с одним из создателей программы для шахматного компьютера Deep Blue , выигравшего матч у Г. Каспарова.
Второй день, 27 февраля, начался с так называемой практики (practice) - пробного ознакомительного соревнования в условиях, приближенных к “боевым”, но без учета результатов. В ходе практики соревнующиеся команды получают и решают всего одну задачу, приноравливаются к предоставленной им вычислительной технике, работая при этом без особого напряжения. В тот же день было проведено еще одно неофициальное и необязательное соревнование, Visual Age for Java Contest, в котором требовалось с помощью программы фирмы IBM написать на Java и встроить в HTML-страницу утилиту-калькулятор, сходную с той, что имеется в Windows. Столики многих команд на этом соревновании пустовали. Из команды МГУ участвовал (но безуспешно) всего один студент, остальные российские команды от участия отказались из-за отсутствия опыта работы с Java и нежелания тратить силы перед основным, решающим состязанием. А оно состоялось на следующий день.
28 февраля в 10 утра занявшие свои места команды вскрыли конверты с восемью заданиями и погрузились в работу. Спустя некоторое время копии заданий стали доступны и зрителям, в том числе тренерам команд. Через час зал был уже расцвечен несколькими воздушными шариками, соответствующие результаты появились на информационном мониторе. Сборные СПбГУ и СПбГИТМО постоянно держались в первой половине общей таблицы, а первое место некоторое время оспаривали разные команды, пока не выявился явный лидер - сборная пражского Карловского университета, первой решившая пять задач и имевшая наименьшее штрафное время.
По традиции за час до окончания соревнования сведения о положении команд, выводимые на информационный монитор, перестали обновляться. Еще через полчаса организаторы прекратили отмечать цветными шариками верно решенные задачи - наступила неизвестность (которая длилась еще целый час после завершения соревнования). К этому моменту вперед вырвалась сборная СПбГУ: питерцы успели решить шестую задачу, а чехи оставались с пятью. У наших соотечественников был реальный шанс решить еще одну задачу - в этом случае они почти наверняка становились чемпионами. Но вышло иначе. Победили пражане, в последний час догнавшие питерцев по количеству решенных задач, но затратившие меньше времени. Они и стали чемпионами мира и Европы, наши оказались вторыми. Команда СПбГИТМО, решившая пять задач, поделила 11 - 16 места еще с пятью командами, две из которых представляли китайские вузы. Сборные МГУ и УрГУ, одолевшие по четыре задачи, вошли в группу команд, поделивших 17 - 24 места. Это тоже можно считать неплохим результатом.
Некоторые наблюдения и выводы
В нашей стране пик интереса к программированию пришелся на вторую половину восьмидесятых, когда персональные компьютеры успели получить достаточно широкое распространение, а рынок ПО был еще достаточно диким, так что программы пытались создавать все кому не лень. Сейчас, с наступлением эпохи индустриального программирования, стало гораздо меньше “бытовых” программистов-индивидуалов: создать в одиночку современное конкурентоспособное приложение для такой среды, как, скажем, Windows 95, непросто; к тому же рынок насыщен, можно найти программное средство практически на любой случай жизни. Отрадно, что несмотря на все это интерес к программированию, причем в самом чистом и высоком смысле слова, растет.
Чемпион мира и Европы по программированию — сборная пражского Карловского университета
Впрочем, сейчас растет и спрос на программистов. Примечательно, что соревнования проходили под аккомпанемент сообщений американских СМИ о катастрофической нехватке в стране специалистов по информационным технологиям: по разным оценкам, число вакансий в этом секторе бизнеса составляет от 90 до 400 тыс. (во многом это обусловлено страхом перед пресловутой проблемой, связанной со сменой тысячелетия, и перед угрозой компьютерному сообществу, исходящей от хакеров). Очевидно, что заполняться эти вакансии будут в немалой степени путем привлечения иностранных специалистов, престиж которых еще больше укрепился благодаря успехам иностранцев на прошедшем чемпионате. Следует также учесть, что иностранные команды были в основном мононациональными по составу, а в сборных американских вузов было немало граждан европейских и азиатских государств. К примеру, за сборную Массачусетского технологического института, занявшую пятое место (это была единственная команда из США, вошедшая в первую десятку), выступал студент из Болгарии, а в составе сборной университета Беркли (одиннадцатое место) был россиянин.
Говоря об успехах европейцев, нужно подчеркнуть, что в первую очередь речь идет о странах бывшего соцлагеря: в финале чемпионата-98 не было ни одной команды из Великобритании, Франции, Испании, Италии; сплоховали и некогда сильные голландцы. Из представителей вузов Западной Европы наибольшего успеха на этот раз добились студенты шведского университета Умео, завоевавшие четвертое место. Студенты Варшавского университета заняли девятое место, сборная Политехнического университета Бухареста - десятое. Похоже, сказалась традиционно сильная советская система подготовки математиков, в свое время пустившая корни и в других соцстранах.
Отмечу также, что в финале-98 в командах практически отсутствовали представительницы прекрасного пола. В составе нескольких сборных девушки были, но во время состязаний они оставались на скамейке запасных. Хотя пятичасовое соревнование требует огромного напряжения - не только умственного, но и физического (что скорее под силу мужчинам), хочется надеяться, что в финале будущего года можно будет увидеть смешанные команды. Кстати, этот финал впервые состоится в Европе - в голландском городе Эйндховене. А пока поздравим студентов СПбГУ с престижным вторым местом и пожелаем нашим командам успеха на следующем чемпионате. Для этого им помимо хорошей программистской и математической подготовки потребуется уверенное владение английским, да и без поддержки местных спонсоров не обойтись. И еще один совет - не следует пренебрегать языком Java.
Официальный Web-адрес организаторов чемпионата ACM - acm.baylor.edu/acmicpc/.
Материалы об участии российских вузов в чемпионате вы найдете по адресу: www.usu.ru/win/usu/events.
С автором можно связаться, написав по адресу: silonov@familypc.ru.
К сожалению, российским командам трудно найти спонсоров для участия в чемпионате
