Дата-сайентист Анатолий Карпов окончил психологический факультет СПбГУ, преподавал статистику, работал аналитиком во «ВКонтакте», а сейчас переехал в Москву и занимается аналитикой в отделе рекламы Mail.ru. Анатолий — автор нескольких популярных онлайн-курсов по математической статистике и анализу данных. Он рассказал «Цеху», как пришел в профессию, где учился и какие первые шаги сегодня стоит делать начинающим дата-сайентистам...
🤔Вопрос: Знаком ли вам алгоритм Хопкрофта-Карпа, если да, то для чего он нужен ? 😎Ответ: Этот графовый алгоритм, принимающий на вход двудольный граф и возвращающий максимальное, по мощности паросочетании - произвольное множество ребер такое, что каждая вершина графа инцидентна не более чем одному ребру из этого множества. Время работы от O(|E|sqrt(|V|)) до O(|V|^2.5). Любое наибольшее паросочетание является максимальным. Обратное неверно. Плюсы: 1/ Алгоритм находит максимальное множество кратчайших...