Специализация: теоретическая информатика
Теоретическая информатика – одна из пяти специализаций, предлагаемых на выбор студентам программы «Прикладная математика и информатика». Василий Алферов, выпускник 2020 года, рассказал, как это направление появилось в бакалавриате, какие его проекты брали призовые места в международных соревнованиях и были представлены на конференциях.
Василий Алферов, выпускник программы «Прикладная математика и информатика» 2020 года, студент программы «Программирование и анализ данных»
Университет — это отличный шанс попробовать себя в науке перед тем, как уходить в индустрию, такую возможность я упускать не хотел. Когда я выбирал специализацию, «Теоретической информатики» (Computer Science) среди предложенных не было. На курсе было еще несколько ребят, интересующихся этим направлением, и специально под нас открыли CS-курсы. По сути, специализация была создана с нуля по пожеланиям небольшой группы студентов.
За два года плотного изучения CS я работал над двумя крупными проектами. Первый проект на третьем курсе — реализация солвера для задачи о вершинном покрытии. Для этого пришлось покопаться в статьях про полиномиальные ядра и придумать способы их быстрой реализации на практике, потому что, как правило, статьи глубоко теоретические и про пользу на практике там никто не задумывается. В 2019 году мой солвер занял призовое место на PACE Challenge среди солверов, написанных другими академическими исследователями. Второй проект, он же мой бакалаврский диплом, — про улучшение алгоритма для задачи максимальной разрешимости. Мне удалось значительно улучшить результат, державшийся 20 лет. В феврале мой новый алгоритм был представлен на конференции AAAI.
Я рассматриваю как возможность продолжить обучение до получения PhD, так и уйти после магистратуры в индустрию. Все-таки заниматься наукой в качестве проектов в университете — это одно, а в качестве основной специализации — совсем другое. Мне нравится первое, но я совсем не уверен, что понравится второе.
На специализации «Теоретическая информатика» студенты изучают такие предметы, как Методы оптимизации, теорию информации, численные методы, вероятностные алгоритмы, точные экспоненциальные алгоритмы, дополнительные главы алгоритмов и структур данных, вычислительную геометрию, криптографические протоколы, приближенные алгоритмы, параметризованные алгоритмы.
Более подробно с описанием курсов можно ознакомиться на сайте программы «Прикладная математика и информатика».