В прошлом году в Академическом университете прошел первый конкурс студенческих работ по теоретической информатике и дискретной математике им. Алана Тьюринга. Недавно мы объявили второй конкурс (срок подачи работ 10 мая 2017 года), а в этой статье мы расскажем об итогах первого конкурса.
Зачем? Основная цель этого конкурса — мотивационная: мы хотим, чтобы больше студентов делали выбор в пользу занятия наукой.
Жюри. В состав жюри вошли действующие учёные, работающие в разных областях информатики и дискретной математики. Жюри составлялось по такому принципу: половина из Санкт-Петербурга, где проходит очный тур, половина из других городов.
Конкурс состоял из двух туров: заочного и очного. В заочном туре работы рецензировались и жюри отбирало участников финального очного тура. Всего на конкурс было подано 22 работы.
Отбор работ. Рецензирование работ проходило по стандартам международных конференций: каждая работа получила не менее трех рецензий. Рецензировали как члены жюри, так и внешние рецензенты. Все участники получили рецензии на свои работы. Мы учитывали конфликты интересов и на этапе отбора работ на финальный тур члены жюри не имели доступа к обсуждению работ своих студентов.
Финальный тур. На финальный тур были приглашены авторы 8 работ (две работы из Санкт-Петербурга, две из Москвы, три из Новосибирска и одна из Екатеринбурга). Финалисты выступали с докладами, члены жюри и все присутствующие задавали вопросы и обсуждали. Иногородние члены жюри смотрели выступления по видеотрансляции и также задавали вопросы.
Подведение итогов. После всех выступлений жюри удалилось на заседание. Оказалось очень непростой задачей выбрать победителей, у каждой работы нашлись члены жюри, желающие выдать ей премию. Поэтому присуждение премий вызвало жаркую дискуссию. В итоге решение принималось многораундовым рейтинговым голосованием.
Победитель. Первое место получила работа “Поиск палиндромов в потоковой модели” Олега Меркурьева (Уральский Федеральный университет, научный руководитель А.М. Шур). В этой работе решается задача о нахождении в данной строке самой длинной подстроки-палиндрома в специальной потоковой модели вычислений. В этой модели строка читается посимвольно и не может быть полностью сохранена в памяти. Эта модель активно изучается в последнее время в связи с большим количеством потенциальных приложений: вычислительно слабые устройства, через которые проходит много данных, — это, например, маршрутизаторы.
В работе разработаны новые алгоритмы, решающие задачу приближенно, в том смысле, что полученное решение не обязательно будет оптимальным, но будет близко к оптимальному. Время работы построенных алгоритмов линейно, на обработку одного символа тратится константное число шагов, а объём используемой памяти лишь немного превышает теоретические нижние оценки. Полученные алгоритмы существенно улучшают результаты из предыдущей работы по этой теме Гавриховского и Узнанского 2015 года.
В основе метода решения лежит использование хеширования, как и в алгоритме Рабина-Карпа поиска подстрок. Полиномиальный хеш подстрок легко пересчитывается при операциях сдвига, что позволяет тратить O(1) времени на обработку каждого символа. С учетом того, что нас устраивает приближенное решение, алгоритму достаточно хранить не все «частичные хеши», а только некоторые, это и позволяет существенно экономить память. Подробнее можно прочитать в конкурсной работе.
Общие выводы. Опыт первого конкурса показал, что в России пишется немало студенческих научных работ достойного уровня, а конкурс — это хороший повод собрать талантливых молодых учёных вместе. Мы надеемся, что популярность научных исследований среди студентов будет расти, и на втором и последующих конкурсах будет представлено ещё больше интересных научных работ.
Зачем? Основная цель этого конкурса — мотивационная: мы хотим, чтобы больше студентов делали выбор в пользу занятия наукой.
Жюри. В состав жюри вошли действующие учёные, работающие в разных областях информатики и дискретной математики. Жюри составлялось по такому принципу: половина из Санкт-Петербурга, где проходит очный тур, половина из других городов.
Конкурс состоял из двух туров: заочного и очного. В заочном туре работы рецензировались и жюри отбирало участников финального очного тура. Всего на конкурс было подано 22 работы.
Отбор работ. Рецензирование работ проходило по стандартам международных конференций: каждая работа получила не менее трех рецензий. Рецензировали как члены жюри, так и внешние рецензенты. Все участники получили рецензии на свои работы. Мы учитывали конфликты интересов и на этапе отбора работ на финальный тур члены жюри не имели доступа к обсуждению работ своих студентов.
Финальный тур. На финальный тур были приглашены авторы 8 работ (две работы из Санкт-Петербурга, две из Москвы, три из Новосибирска и одна из Екатеринбурга). Финалисты выступали с докладами, члены жюри и все присутствующие задавали вопросы и обсуждали. Иногородние члены жюри смотрели выступления по видеотрансляции и также задавали вопросы.
Подведение итогов. После всех выступлений жюри удалилось на заседание. Оказалось очень непростой задачей выбрать победителей, у каждой работы нашлись члены жюри, желающие выдать ей премию. Поэтому присуждение премий вызвало жаркую дискуссию. В итоге решение принималось многораундовым рейтинговым голосованием.
Победитель. Первое место получила работа “Поиск палиндромов в потоковой модели” Олега Меркурьева (Уральский Федеральный университет, научный руководитель А.М. Шур). В этой работе решается задача о нахождении в данной строке самой длинной подстроки-палиндрома в специальной потоковой модели вычислений. В этой модели строка читается посимвольно и не может быть полностью сохранена в памяти. Эта модель активно изучается в последнее время в связи с большим количеством потенциальных приложений: вычислительно слабые устройства, через которые проходит много данных, — это, например, маршрутизаторы. В работе разработаны новые алгоритмы, решающие задачу приближенно, в том смысле, что полученное решение не обязательно будет оптимальным, но будет близко к оптимальному. Время работы построенных алгоритмов линейно, на обработку одного символа тратится константное число шагов, а объём используемой памяти лишь немного превышает теоретические нижние оценки. Полученные алгоритмы существенно улучшают результаты из предыдущей работы по этой теме Гавриховского и Узнанского 2015 года.
В основе метода решения лежит использование хеширования, как и в алгоритме Рабина-Карпа поиска подстрок. Полиномиальный хеш подстрок легко пересчитывается при операциях сдвига, что позволяет тратить O(1) времени на обработку каждого символа. С учетом того, что нас устраивает приближенное решение, алгоритму достаточно хранить не все «частичные хеши», а только некоторые, это и позволяет существенно экономить память. Подробнее можно прочитать в конкурсной работе.
Общие выводы. Опыт первого конкурса показал, что в России пишется немало студенческих научных работ достойного уровня, а конкурс — это хороший повод собрать талантливых молодых учёных вместе. Мы надеемся, что популярность научных исследований среди студентов будет расти, и на втором и последующих конкурсах будет представлено ещё больше интересных научных работ.