ОБРАЗОВАНИЕ

Ошеломляющий успех наших программистов

На прошедшем в конце марта в Праге финале студенческого командного чемпионата мира по программированию (International Collegiate Programming Contest, ICPC, www.acmicpc.org) три из четырех золотых медалей завоевали представители отечественной программистской школы: абсолютным чемпионом стала команда Санкт-Петербургского университета информационных технологий, механики и оптики (ИТМО, до прошлого года он назывался Институтом точной механики и оптики). Еще две медали высшей пробы получили коллективы Белорусского и Пермского государственных университетов, занявшие соответственно третье и четвертое места (по условиям соревнований золотые награды вручаются первым четырем призерам, серебряные - командам, занявшим места с 5-го по 8-е, и бронзовые - с 9-го по 12-е). В 2004 г. кроме упомянутых выше команд в первую четверку смог пробиться лишь коллектив шведского института KTH - Royal Institute of Technology.

ACM-ICPC: немного истории

Чемпионаты ICPC проводятся под эгидой известной международной ассоциации - Association for Computing Machinery (ACM, www.acm.org), объединяющей специалистов в области компьютерных технологий, и считаются самыми крупными и авторитетными мероприятиями такого рода в мире. Начало им было положено в 1970 г., когда прошли первые олимпиады для университетов США и Канады. С 1977 г. они приобретают сохранившуюся до нынешних времен форму многоэтапного соревнования. В 80-е годы к организации чемпионатов подключились энтузиасты из Baylor University, усилиями которых была создана международная университетская сеть ICPC, а состязания приобрели воистину всемирный масштаб. С 1984 г. оргкомитет ACM-ICPC возглавляет настоящий энтузиаст этого движения - профессор Baylor University Уильям Паучер, по мнению которого подобные соревнования служат прекрасной средой для взаимного общения и профессионального роста молодых людей, поскольку они учатся бороться не друг с другом, а со сложными проблемами - пусть пока это всего лишь довольно специфические олимпиадные задачи.

Следующий важный этап развития движения ACM-ICPC начался в 1997 г., когда его генеральным спонсором стала корпорация IBM (www.ibm.com). Благодаря ее поддержке за прошедшие с тех пор семь лет число университетов, принимающих участие в предварительных этапах состязания, увеличилось в 2,5 раза и достигло 1412, а число команд выросло почти в 4 раза (сегодня их 3150). Многоэтапная процедура отбора начинается с проведения внутриинститутских соревнований, победители которых допускаются к предварительному этапу, где выступают команды разных университетов одной и той же страны. Лучшие из них собираются на региональные чемпионаты (Северная Америка, Африка и Ближний Восток, Азиатско-Тихоокеанский регион, Европа и Латинская Америка), являющиеся последним отборочным этапом перед финалом. В нынешнем году в соревнованиях всех уровней приняли участие более 20 тыс. студентов из 75 стран.

Каждый поднятый над столом команды

воздушный шар - это решенная задача

В Праге собрались 73 команды из 31 страны. Наиболее мощно были представлены учебные заведения США - 21 команда. Следом с 8 командами идет Россия, честь которой защищали студенты Московского, Санкт-Петербургского, Нижегородского, Новосибирского, Пермского и Петрозаводского госуниверситетов, а также Ижевского технического университета и питерского ИТМО. Еще 3 команды, представлявшие страны бывшего Советского Союза, с известными оговорками тоже можно считать наследниками общей научной и преподавательской школы. Это программисты из Белорусского и Тартуского университетов и Киргизско-русского славянского университета. Отметим, что славящиеся своими программистами Китай и Индия смогли провести в финал 6 и 2 команды соответственно, но из них в призовую дюжину удалось пробиться лишь одной (из китайского университета ZhongShan - 11-е место). У нас же серебро (8-е место) завоевал еще и коллектив из Ижевска.

Россияне становятся чемпионами ACM-ICPC далеко не впервые: в последний раз это было на соревнованиях 2000 и 2001 гг., когда блеснула команда Санкт-Петербургского университета. Однако в 2002-м титул победителя завоевал Шанхайский университет, а в 2003-м - Варшавский. И вот праздник снова на нашей улице. Замечательная его особенность, как мне кажется, состоит в том, что впервые в мировую студенческую элиту по праву пробились не только знаменитые столичные вузы, но и региональные университеты, которые нам в таком качестве доселе известны не были.

Чемпионат ACM-ICPC: взгляд изнутри

Довольно жесткие условия соревнований призваны выявить не просто лучших программистов: победа невозможна, если они не умеют оптимально распределять свои ресурсы и работать в коллективе. Команда состоит из трех человек. Им предлагается за 5 ч решить 10 задач. Есть еще и тренер, но ему общаться со своими питомцами во время соревнований запрещено. Побеждает коллектив, решивший наибольшее число задач, причем все задачи считаются равноценными. В действительности это, конечно, не так: оргкомитет сознательно подбирает задачи разной трудности, с тем чтобы две-три из них оказались по зубам большинству участников финала. Поэтому первая проблема для команды - выявление самых легких задач, решением которых имеет смысл заняться в первую очередь.

Абсолютные чемпионы мира - команда ИТМО со своими наставниками

Для примера - вот одно из предложенных заданий. На квадратной сетке конечных размеров, являющейся моделью города, расположены дома (нечто вроде кораблей в известной игре "Морской бой"). Нужно соединить их прямолинейными мостиками (галереями) таким образом, чтобы можно было из любого дома пройти в любое другое здание города, не спускаясь на "грешную землю", причем следует найти решение с минимальным числом таких мостиков. Конечно, участники не получают "карту" конкретного города: они должны представить программу, реализующую общий алгоритм, пригодный для любой возможной конфигурации. Поскольку для некоторых из конфигураций решения просто не существует, для других - равноценных решений может быть несколько, а для третьих удается построить только группы связанных между собой домов, но сами такие группы изолированы друг от друга (кластеры), то каждая подобная ситуация должна быть выявлена программой и соответствующим образом обработана. Например, если есть несколько равноценных по числу мостиков решений, то из них нужно выделить то, где минимальна суммарная длина мостиков.

Программу разрешается писать на одном из трех языков - C/C++, Паскале или Java. Интересно, что судейская коллегия не оценивает правильность или, допустим, изящество алгоритмов и исходных кодов. Она просто проверяет сданную программу на некотором достаточно полном наборе тестовых примеров и, если получает набор правильных ответов, фиксирует время и выдает команде воздушный шарик. Так как соревнования проходили в одном большом концертном зале пражского дворца Obecni Dum, то по числу витающих над каждым столом шариков любой наблюдатель мог сразу же составить представление о текущей расстановке сил. Скорость выполнения заданий очень важна, ведь при равном числе решенных задач итоговое положение команд определяется по суммарному затраченному времени. В пражском финале, решив пять задач, можно было оказаться и на 6-м, и на 12-м месте, так, команда Гарварда, занявшая 9-е место, опередила Варшавский университет всего лишь на одну минуту.

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

Праздник со слезами на глазах

Иными словами, эти молодые ребята (как правило, студенты второго-третьего курсов) должны владеть и, как показал чемпионат, уже владеют многими знаниями и навыками, необходимыми для профессиональной работы в реальных проектах. Найдется немало фирм, желающих взять их на заметку, и, думается, одной из первых здесь будет генеральный спонсор - IBM. Когда о наличии подобных планов спросили отвечающего за спонсорский проект директора по программам IBM Centers for Advanced Studies Габриэля Силбермана, тот с широкой улыбкой заверил журналистов, что корпорация с удовольствием приняла бы в свой штат всех участников финала. Однако большинству из них предстоит еще долго учиться, а затем решать и другие жизненные проблемы, а потому сегодня говорить об этом просто рано. Вполне возможно, что победители получат специальные стипендии или будут приглашены на летнюю практику в одно из подразделений IBM.

Финальная часть мирового первенства

проходила в концертном зале Obecni Dum

Процедура подведения итогов была по-своему драматичной. Хотя тренеры внимательно следили "за воздушным пространством", фиксируя количество поднятых соперниками шариков, никто не мог гарантировать, что какая-нибудь команда не сдаст задачу в последнюю минуту и не смешает таким образом все карты. По мере объявления призеров и продвижения от конца списка двенадцати сильнейших к его началу напряжение нарастало. Как я уже говорил, места с 12-го по 6-е поделили команды, решившие по пять задач. Затем, по мере того как объявление каждого следующего призера сопровождалось одной и той же фразой - "шесть задач", у присутствовавших зрела уверенность, что чемпиона выявит только "фотофиниш" - временной показатель. Поэтому, когда жюри сообщило, что абсолютный чемпион - команда питерского ИТМО - единственная решила семь задач, зал приветствовал ее стоя.

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

Итак, пражский финал еще раз напомнил нам всем о том потенциале, который сохранила Россия в области программирования и высшего образования. Следует ли опасаться, что уважаемый спонсор и другие крупные зарубежные компании заберут себе всех наших лучших молодых специалистов? Если вспомнить о снижении спроса на ИТишников в США и ужесточении ограничений при выдаче рабочих виз иностранцам, эта перспектива не кажется столь уж неизбежной. Да и осторожные ответы г-на Силбермана, о которых я упоминал выше, заставляют усомниться в способности IBM "принять на работу всех финалистов". Рискну предположить, что подобные успехи наших юных студентов в немалой степени способствуют формированию имиджа России как страны высококлассных программистов и будут стимулировать отечественную отрасль так называемого офшорного программирования. При надлежащем развитии этого сегмента спрос на специалистов высшей квалификации будет очень высоким, и тогда нужно будет только разумно использовать сей "естественный и возобновляемый" ресурс, а не выдавливать его низкими зарплатами за рубеж.

Впрочем, возобновляемым он будет лишь до тех пор, пока имеющиеся научные и преподавательские школы смогут продолжать активную творческую деятельность. Как они будут это делать при той катастрофически низкой оснащенности техническими средствами профильных кафедр, о которой мне в частных беседах рассказывали члены ряда делегаций? Я знаю, что многие отечественные ИТ-компании ведут благотворительную деятельность или готовы ее вести, но не всегда могут найти достойные объекты. Хочу обратить их внимание на ИТ-кафедры вузов, особенно периферийных, ведущих активную работу с молодыми ребятами. Не нужно дожидаться, когда они добьются выдающихся результатов: пример пермяков и ижевцев показывает, что это чудо может произойти в любой момент и в любом регионе. Мне кажется, ИТ-компаниям сложно будет найти более уместный способ "творить благо".

Версия для печати