Публикуем статью Павла Дубова, студента ФИВТ МФТИ, преподавателя курса Алгоритмы. Олимпиадное программирование в 1С: Клубе программистов и тренера нашей олимпиадной сборной.



Рано или поздно перед любым школьником, планирующим поступать в приличный вуз на IT-специальность, встаёт вопрос: как и к чему готовиться? Безусловно, самый банальный ответ — готовиться к ЕГЭ, доводя самоконтроль до исступлённого автоматизма, чтобы избегать ошибок в ответственные моменты. Но есть и другой путь, позволяющий не только дать себе дополнительные шансы, но и приобрести навыки, необходимые для устройства на работу в хорошие компании.

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

На данный момент существует несколько уровней олимпиад по информатике. На самом «высоком» уровне находится Всероссийская олимпиада школьников. Получение диплома на этой олимпиаде гарантирует участнику поступление в любой вуз по соответствующему профилю без экзаменов. Олимпиады других уровней в зависимости от вуза могут давать либо поступление без экзаменов, либо 100 баллов на ЕГЭ по информатике. Для таких льгот требуется набрать минимальный балл на самом ЕГЭ — обычно 65 баллов, что, в общем, при условии получения диплома труда не составляет. Распределение олимпиад по уровням каждый год публикует Минобрнауки в интернете. Так как олимпиад несколько, можно попытать успеха несколько раз и таким образом упростить себе задачу.



Так что же нужно для того, чтобы начать подготовку?

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

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



Для тех, кто хочет совмещать структурированность материала и хорошую компанию, для них и существует 1C: Клуб программистов (http://club.1c.ru): последовательность курсов, среди которых человек с любым уровнем знаний может найти себе подходящий. Кроме алгоритмических курсов на языке Java существуют также курсы по «промышленной» Java, системному администрированию и управлению разработкой проектов.

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

Затем следуют Первый и Второй модули, в которых происходит закрепление приобретённых навыков, разбираются простые структуры данных и алгоритмы: НОД/НОК, массивы и сортировки, строки, стек и очередь, графы и обходы, метод динамического программирования.

в 3-4 модулях идёт нацеленная подготовка инструментов, часто используемых на серьёзных олимпиадах: комбинаторная генерация, наибольшая возрастающая/общая подпоследовательность, алгоритмы на графах, суммы игр, бинарный поиск, вычислительная геометрия, выпуклая оболочка, двоичная куча, деревья отрезков, хеширование.

Разумеется, не обязательно приходить именно на Стартовый модуль: если владеешь основным конструкциями языка — можно начинать сразу с Первого. Если Первый или Второй кажутся скучными и понятными — можно пропустить и их.

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

Я занимаюсь с группами 3-4 модуля и веду сборы.

Обычно, занятия 3-4 модуля проходят так: сначала мы разбираем необходимую теорию, а затем ребята решают задачи и сдают их в тестирующую систему. Задач чаще всего около 10 — от самых простых (для развития нужного навыка) до уровня олимпиад. При этом я смотрю код как во время написания, чтобы убедиться, что процесс идёт в нужном направлении, так и после сдачи, чтобы дать советы, ускоряющие или упрощающие разработку решений в дальнейшем.



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

У ребят на сборах нет единой задачи: скажем, в этом году двое готовились к заключительному этапу Всероссийской олимпиады, а основная масса готовилась к Московской олимпиаде, которая проводится в версиях для 7-9 и 10-11 классов. В итоге, на каждом соревновании нам удалось добиться призёрств.



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

Бывает, что и меня учат чему-нибудь: например, как избавиться от ±1 при написании дерева отрезков, где вкуснее всего хот-доги или в каком году родилась Мария-Антуанетта. Так что скучно не бывает.

Не знаю уж, в чём тут секрет, но Клуб очень домашний. Можно найти друзей, команду по Counter-Strike, компанию для настольных игр, или устроить парочку хакатонов и с одногруппниками сделать своего Mario.

Да и голодным никто не остаётся. Наверное, это одна из причин такой атмосферы: одно дело — скоротать время, листая ленту социальной сети, а другое — отложив смартфон, кушать бутерброд и пить чай с печеньками. Тут уж обязательно с кем-нибудь познакомишься!