Привет, меня зовут Михаил Ройзнер. Недавно я выступил перед студентами Малого Шада Яндекса с лекцией о том, что такое рекомендательные системы и какие методы там бывают. На основе лекции я подготовил этот пост.

План лекции:

1. Виды и области применения рекомендательных систем.
2. Простейшие алгоритмы.
3. Введение в линейную алгебру.
4. Алгоритм SVD.
5. Измерение качества рекомендаций.
6. Направление развития.

Около недели назад Яндекс объявил о наборе на новый учебный год в свою школу. Обучение ведётся по двум направлениям: анализ данных и computer science. В качестве вступительного задания абитуриенту школы предлагается рассказать о себе и решить несколько несложных задачек по математическому анализу, теории вероятностей и программированию. Решения можно отправлять до 15 августа.

Кроме того во время обучения в школе можно получить диплом высшей школы экономики, а после — пройти стажировку в Яндексе.

Обучение бесплатное, очно-заочное (вечернее), занятия проходят по вечерам, примерно с 18 до 20. Судя по отзывам моих знакомых, учиться интересно и местами даже сложно.

На сайте ничего не сказано о возрастном ограничении, так что дерзайте!

UPD: после заочной анкеты проводится очное собеседование, на котором вопросы могут быть сложнее. kronos о собеседовании.

Введение

Задача о максимальном потоке является классической и имеет множество применений. Напомню постановку проблемы. Дан взвешенный ориентированный граф с неотрицательными весами (пропускными способностями). Выделены две вершины: исток S и сток T такие, что любая другая вершина лежит на пути из S в T. Потоком назовем функцию F: V x V с такими свойствами

1. Ограничение пропускной способности. Поток по ребру не может быть больше его (ребра) пропускной способности.
2. Антисимметричность. Для каждого ребра (u, v): F(u, v) = -F(v, u).
3. Сохранение потока. Для каждой вершины (кроме S и T), количество входящего потока (отрицательного) равен количеству исходящего потока (положительного). Тоесть, алгебраическая сумма потоков для каждой вершины (кроме S и T) равна нулю.

В этом посте вы можете ознакомиться с реализацией поставленной проблемы.

Перейдем непосредственно к типичным задачам, которые сводятся к алгоритму нахождения максимального потока в сети. Часто выявить в таких задачах поток очень не просто.

В последнее время, особенно когда нечего делать, часто хочется включить какую-нибудь музыку для фона (Работаю я чаще в тишине). Искать и заполнять плеер каждый раз разными хорошими песнями меня дико раздражает. Лень взяла свое или фантазия иссякла, но мне надоело каждый раз составлять плейлист подобным образом, как, впрочем, и обычным шаффлом. Решено было попробовать то, что предлагает веб. Что я там нашел для себя, попробую рассказать. Если вы можете добавить вкусный url, предлагайте.

В настоящее время, в условиях роста информации, возникают задачи хранения и обработки данных очень большого объема. Поэтому эти данные обрабатывается сразу на нескольких серверах одновременно, которые образуют кластеры. Для упрощения работы с данными на кластерах и разрабатывают распределенные файловые системы. Мы подробно рассмотрим пример распределенной файловой системы Google File System, используемую компанией Google. (Статья является, фактически, вольным и урезанным переводом оригинальной статьи ).

Ещё одна задача про узников. На этот раз не такая теоретическая.

Есть 30 узников, пронумерованных от 1 до 30. Каждый знает все номера, в том числе свой. У них есть время на обсуждение алгоритма. Дальше их по одному заводят в комнату, где есть 30 пронумерованных коробок. В каждой коробке по одному ключу с номером какого-то узника (номер коробки и номер ключа в ней могут быть различными). Ключи по коробкам распределены совершенно случайно (т.е. все перестановки ключей в коробках равновероятны). Каждый узник по очереди открывает 15 коробок и смотрит, какие в них ключи, причём, открывая очередную коробку, он может сначала посмотреть, какой в ней ключ, а потом решить, какую открывать следующей. Если в одной из этих 15 коробок оказался ключ с его номером, то его отпускают, если нет — расстреливают. Комната и все коробки в ней после этого приводятся в изначальное состояние, т.е. следующие узники не получают никакой информации о том, что было с предыдущим узником.
Придумайте алгоритм, чтобы с вероятностью не меньше 30% выжили все узники.

PS Можно использовать калькулятор.

UPD Решение в комментах.

Рассказали мне недавно супер-задачу, потребовалось несколько дней чтобы решить.

Есть бесконечно много узников (счётное число), пронумерованных натуральными числами. Каждый узник знает все номера, в том числе свой. Узники умеют бесконечно быстро думать, и у них бесконечно много памяти. Сначала у них есть время на обсуждение алгоритма.
Их выстраивают по порядку, так что первый смотрит в спину второго, второй в спину третьего и т.д. На них одновременно надевают колпаки двух цветов. Каждый узник видит, какие колпаки надеты на узниках с большими номерами (первый видит все колпаки, кроме своего, второй — все, кроме своего и первого и т.д.). Никакой информацией они уже не обмениваются. Дальше каждый из них должен одновременно со всеми сказать, какой на нём колпак. Кто не угадает — того расстреливают. Как сделать так, чтобы лишь конечное число узников расстреляли?

PS Не хватает кармы, чтобы переместить в блог «Занимательные задачки». Спасибо за карму, перенёс в блог «Занимательные задачки».

UPD Решение в комментах.