Научно-исследовательская работа, пожалуй, самая интересная часть нашего обучения. Идея в том, чтобы ещё в университете попробовать себя в выбранном направлении. Например, студенты с направлений Software Engineering и Machine Learning часто идут делать НИРы в компании (в основном, JetBrains или Яндекс, но не только).

В этом посте я расскажу о своём проекте по направлению Computer Science. В рамках работы я изучил и реализовал на практике подходы к решению одной из самых известных NP-трудных задач: задаче о вершинном покрытии.

Сейчас очень быстро развивается интересный подход к NP-трудным задачам — параметризованные алгоритмы. Я постараюсь ввести вас в курс дела, рассказать несколько простых параметризованных алгоритмов и описать один мощный метод, который очень мне помог. Свой результаты я представил на соревновании PACE Challenge: по итогам открытых тестов мое решение занимает третье место, а окончательные результаты будут известны 1 июля.

Прошлым летом я участвовал в Google Summer of Code — программе для студентов от компании Google. Ежегодно организаторы отбирают несколько Open Source-проектов, в том числе от таких известных организаций, как Boost.org и The Linux Foundation. Для работы над этими проектами Google приглашает студентов со всего мира. 

Как участник Google Summer of Code 2019 я делал проект в рамках библиотеки Alga с организацией Haskell.org, занимающейся развитием языка Хаскелль — одного из самых известных функциональных языков программирования. Alga — библиотека, представляющая типобезопасное представление для графов в Хаскелле. Она используется, например, в semantic — библиотеке компании Github, строящей по коду семантические деревья, графы вызовов и зависимостей и умеющей их сравнивать. Мой проект состоял в добавлении туда типобезопасного представления для двудольных графов и алгоритмов для этого представления. 

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

Вторая часть перевода лонгрида посвященного визуализации концепций из теории информации. Во второй части рассматриваются энтропия, перекрестная энтропия, дивергенция Кульбака-Лейблера, взаимная информация и дробные биты. Все концепции снабжены прекрасными визуальными объяснениями.

Для полноты восприятия, перед чтением второй части, рекомендую ознакомиться с первой.