Олимпиады по программированию и научная работа

Алексей Самсонов

Статья опубликована в буклете Четвертьфинала ACM ICPC 2010/11 (октябрь 2010)

В последнее время студенческие олимпиады по программированию становятся всё более и более популярными. Свои соревнования организуют такие компании, как Google и Microsoft, в регулярных соревнованиях, проводимых американской корпорацией TopCoder, участвуют тысячи людей, а победителей чемпионата мира по программированию принимают президенты стран. Сейчас у талантливых и амбициозных студентов-математиков, не желающих в своём обучении ограничиваться посещением лекций и выполнением домашних заданий, есть отличная возможность проявить себя в спорте, в данном случае — в соревнованиях по спортивному программированию. Однако одной из целей, стоящих перед университетами, всегда было проведение научных исследований. Не лучше ли таким студентам вместо «игр» сразу же начать заниматься серьёзными научными проблемами? Не отвлекают ли олимпиады студентов и общественность от той научно-исследовательской работы, которая ведётся в университете? Наконец, насколько стиль мышления и навыки, которые вырабатываются у олимпиадников, полезны или вредны с точки зрения их будущей научной работы?

Современные олимпиады и их связь с наукой

Сначала рассмотрим, как современный мир спортивного программирования связан с наукой, в частности, с высшей математикой и theoretical computer science.

Около двадцати лет назад для успешного выступления в рассматриваемых нами олимпиадах действительно достаточно было «хорошо программировать»: грамотно формализовывать задачу, безошибочно и достаточно эффективно реализовывать её решение на одном из языков программирования, например, на C++.

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

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

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

Ежегодно во всём мире появляются сотни новых олимпиадных задач. Идеи некоторых задач приходят из «реальной жизни». Но специфика олимпиадных задач такова, что почти все они должны быть в принципе решаемы за те несколько часов, что идёт соревнование. Поэтому многие реальные задачи приходится сильно упрощать, тем самым лишая их практического смысла. Иногда сложные версии олимпиадных задач могут заинтересовать их автора или кого-то ещё и послужить основанием для настоящего научного исследования, однако такое происходит крайне редко.

В олимпиадном движении не создаётся новое знание. Вместо этого олимпиады очень активно это новое знание используют. Сложные задачи придумываются по научным статьям и кандидатским диссертациям. Так, дерево Фенвика, придуманное в 90-х годах, сейчас считается стандартной структурой данных, изучаемой даже школьниками. Новые алгоритмы работы с суффиксными массивами и автоматами сразу же после их публикации тщательно исследуются на предмет того, можно ли им найти применение на олимпиадах. Силами олимпиадного движения создаются изящные реализации сугубо теоретических на первый взгляд алгоритмов, придумывается множество упрощений и неасимптотических оптимизаций широко известных алгоритмов. Все эти «изобретения» могут содержать достаточно глубокие идеи, однако они не несут в себе научного знания как такового, а обладают лишь эстетической (изредка — практической) ценностью, которую к тому же очень сложно объективно оценить. Так, научному сообществу вряд ли будет интересна заметка о том, как реализовать вычисление z-функции, подробно описанное Гасфилдом, используя лишь один условный оператор вместо четырёх.

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

Конечно, в реальности не всё так безоблачно. Связь математиков, разрабатывающих алгоритмы, и олимпиадников практически не налажена, поскольку последние не публикуют свои результаты. Что намного хуже, из-за специфики олимпиадных задач в них практически никогда не используются приближённые и эвристические методы, сложные или ресурсоёмкие алгоритмы, параллельные вычисления. В олимпиадах практически не встречается реальное распознавание образов, моделирование процессов с помощью дифференциальных игр и многие другие темы, которые в первую очередь интересуют математиков-практиков и для исследования которых в научных институтах строят суперкомпьютеры. Необходимо отметить, что в последние годы было предпринято множество попыток проводить олимпиады с «исследовательскими» задачами (например, уложить граф на плоскость так, чтобы количество пересекающихся рёбер было минимальным). Однако ни одна из этих попыток не имела большого успеха, в первую очередь — из-за сложности участия в таких олимпиадах и недостатка зрелищности.

Образовательный эффект олимпиад

В современных олимпиадах (особенно это касается олимпиад, проводимых в Восточной Европе) используются не только современные алгоритмы и структуры данных, но и сведения из самых разных областей математики — от комбинаторики слов до теории функций комплексного переменного. Поэтому участник, желающий показывать на соревнованиях высокие результаты, должен обладать достаточно широким математическим кругозором и знать некоторые области (особенно, дискретную математику) существенно лучше своих однокурсников. Значительное количество времени приходится тратить не только на тренировки, но и на самостоятельное изучение теории как с помощью классических учебников вроде “Introduction to Algorithms”, так и с помощью научных статей. Важно отметить, что в настоящий момент на математических факультетах последнему виду работы практически не уделяется внимания — для сдачи большинства предметов достаточно лишь иметь грамотный конспект лекций. Таким образом, олимпиады прививают достаточно ценный навык самостоятельного изучения материала.

Особое внимание следует уделить тому, как появляется потребность в изучении нового материала. Возникает ситуация, когда олимпиадник сталкивается с задачей, которую не может решить, поскольку ему не хватает для этого теоретической подготовки. В процессе разбора соответствующего материала он сразу же понимает область применения изучаемых алгоритмов (методов, теорем) на практике на примере рассматриваемой задачи. Поскольку получение нового знания осмысленно и есть повод сразу же использовать его в задаче, вероятность того, что оно попадёт в глубокий пассив и забудется, будет меньше. Так, с леммой Бернсайда можно познакомиться на лекции по теории групп, где она появляется после введения многочисленных определений и проведения утомительных доказательств. С другой стороны, олимпиадник может «выйти» на эту лемму, решая задачу о том, сколькими способами из заданного набора цветных стержней можно составить додекаэдр, если додекаэдры, получаемые друг из друга поворотом, считаются одинаковыми. При самостоятельном разборе этой задачи лемма будет казаться полезной и значимой, а с осознанием понятий орбиты и стабилизатора проблем тоже, скорее всего, не возникнет. Главная же польза от такого подхода заключается в том, что изучив лемму Бернсайда с практической точки зрения и сведя термины задачи к терминам теории групп (а не наоборот), повторить этот процесс для другой задачи будет существенно проще. Так, опытный участник соревнований по программированию достаточно быстро решит задачу о том, сколькими способами можно раскрасить граф, если изоморфные графы считаются одинаковыми. Для этого достаточно лишь увидеть аналогию между этой задачей и задачей о додекаэдре, сформулировать её в терминах теории групп и воспользоваться знанием необходимых фактов. Умение находить подобные аналогии стоит рассмотреть отдельно.

Олимпиадный стиль мышления

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

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

Итак, научная деятельность достаточно специфична, но она скорее непривычна для бывших участников олимпиад так же, как и для всех остальных людей, а не противопоказана им. Действительно же полезное умение, вырабатываемое во время олимпиад — это умение строить аналогии и рассматривать разные интерпретации задачи. Так, Дьёрдь Пойа писал, что «возможно, не существует открытий ни в элементарной, ни в высшей математике, ни даже, пожалуй, в любой другой области, которые могли бы быть сделаны без аналогии». В олимпиадах многие задачи построены на стыке разных областей математики (например, вычислительной геометрии и теории графов), поэтому олимпиадник яснее видит взаимосвязи между ветвями науки и часто способен применять рассуждения из одной области знаний в другой, что бывает крайне важно для получения нового результата.

Кроме того, олимпиады развивают умение сводить новые задачи к уже известным, в особенности, разбивать сложную задачу на несколько простых и хорошо изученных. Очень часто стратегия решения задачи заключается в том, что нужно перебрать все элементы ограниченного множества известных приёмов, алгоритмов и трюков и проверить, какие из них применимы к конкретной задаче. Таким образом, задачу получится либо упростить, либо свести к известной, либо хотя бы сформулировать на другом языке. Но умение быстро находить нужный алгоритм или приём или подгонять задачу под известный алгоритм крайне ценно в науке! Так, в комбинаторике слов доказательство многих утверждений заключается в построении нужного морфизма и сведении утверждения к известным фактам о хорошо изученной последовательности Туэ-Морса. Джанкарло Рота в своей статье отмечает, что у каждого математика есть в запасе только ограниченный набор методов. Значит, способность использовать их по максимуму и применять их к самым разным задачам крайне важна. Тот же Рота упоминает о «методе Фейнмана», который гласит, что учёному нужно постоянно держать в голове несколько задач, и как только он узнаёт (или придумывает) новый трюк или алгоритм, пытаться применить его к этим задачам.

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

Популярность олимпиад и скоротечность олимпиадной карьеры

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

С помощью соревнований можно существенно и достаточно быстро поднять авторитет учебного заведения и повысить его популярность в глазах общественности. Утверждение «наши программисты (математики) — сильнейшие в регионе (стране, мире)» можно считать справедливым благодаря формальным правилам соревнований, качество же научной работы оценивать и сравнивать куда сложнее.

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

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