Конкурс Тьюринга студенческих работ по теор. информатике и дискретной математике

    В прошлом году в Академическом университете прошел первый конкурс студенческих работ по теоретической информатике и дискретной математике им. Алана Тьюринга. Недавно мы объявили второй конкурс (срок подачи работ 10 мая 2017 года), а в этой статье мы расскажем об итогах первого конкурса.


    Зачем? Основная цель этого конкурса — мотивационная: мы хотим, чтобы больше студентов делали выбор в пользу занятия наукой.

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

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

    Отбор работ. Рецензирование работ проходило по стандартам международных конференций: каждая работа получила не менее трех рецензий. Рецензировали как члены жюри, так и внешние рецензенты. Все участники получили рецензии на свои работы. Мы учитывали конфликты интересов и на этапе отбора работ на финальный тур члены жюри не имели доступа к обсуждению работ своих студентов.

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

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

    Победитель. Первое место получила работа “Поиск палиндромов в потоковой модели” Олега Меркурьева (Уральский Федеральный университет, научный руководитель А.М. Шур). В этой работе решается задача о нахождении в данной строке самой длинной подстроки-палиндрома в специальной потоковой модели вычислений. В этой модели строка читается посимвольно и не может быть полностью сохранена в памяти. Эта модель активно изучается в последнее время в связи с большим количеством потенциальных приложений: вычислительно слабые устройства, через которые проходит много данных, — это, например, маршрутизаторы.

    В работе разработаны новые алгоритмы, решающие задачу приближенно, в том смысле, что полученное решение не обязательно будет оптимальным, но будет близко к оптимальному. Время работы построенных алгоритмов линейно, на обработку одного символа тратится константное число шагов, а объём используемой памяти лишь немного превышает теоретические нижние оценки. Полученные алгоритмы существенно улучшают результаты из предыдущей работы по этой теме Гавриховского и Узнанского 2015 года.

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

    Общие выводы. Опыт первого конкурса показал, что в России пишется немало студенческих научных работ достойного уровня, а конкурс — это хороший повод собрать талантливых молодых учёных вместе. Мы надеемся, что популярность научных исследований среди студентов будет расти, и на втором и последующих конкурсах будет представлено ещё больше интересных научных работ.
    Computer Science Center
    140.93
    Company
    Share post

    Comments 0

    Only users with full accounts can post comments. Log in, please.