Студенты "ПМИ" приняли участие в международной летней школе по программированию

Студенты образовательной программы "Прикладная математика и информатика" Рамиль Яруллин, Айбек Аланов и Никита Зетилов приняли участие в международной летней студенческой школе по программированию "Сазанка". Рамиль Яруллин, студент 3 курса ПМИ, рассказал об отборе на участие в летней школе, учебной программе и тренировках.

«Сазанка» – это международная летняя студенческая школа по программированию, которую ежегодно проводит Саратовский государственный университет. Руководителем этого мероприятия является Михаил Мирзаянов, основатель codeforces.com. В этом году летняя школа проходила с 3-го по 13-е августа. Чтобы поучаствовать, можно было зарегистрировать свою команду из двух-трех человек, либо подать заявку как индивидуальный участник. Мы с Алановым Айбеком сформировали команду, а Зетилов Никита участвовал индивидуально.

 

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

 

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

·     z- и префикс- функции строки, свойства

·     алгоритм Кнута-Морриса-Пратта

·     структура данных бор

·     задача о множественном поиске образцов в тексте, алгоритм Ахо-Корасик, автомат Ахо-Корасик

·     структура данных суффиксный массив

·     структура данных суффиксное дерево, алгоритм Укконена

·     использование строковых хеш-функций

 

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

 

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

    Рамиль Яруллин