Дискретная математика: подсчеты, графы, случайные блуждания

Мы начнем с краткого введения в комбинаторику, раздел математики, изучающий подсчеты. Основы комбинаторики критически важны для всех, кто работает в анализе данных или в Computer Science. В качестве примеров использования комбинаторики мы обсудим вопросы о подсчете размера пространства признаков и об оценке времени работы программ на Python.

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

Наконец, в третьей части курса НИУ ВШЭ мы обсудим комбинаторную структуру, наиболее часто встречающуюся в анализе данных — графы. Графы встречаются повсюду, как в анализе данных, так и в обычной жизни, и мы увидим это на разнообразных примерах. Мы дадим необходимые сведения из теории графов, а в конце курса выполним проект, а именно построим несложную рекомендательную систему, основанную на случайных блужданиях в графах.

Курс проходит на внутренней платформе НИУ ВШЭ. 

Курс длится 6 недель. Каждая неделя содержит видеолекции, тестовые задания и материалы для самостоятельного изучения. В конце курса вас ждет прикладной проект.

1. Базовые подсчеты

Предположим, что нам нужно пересчитать некоторые объекты. Можно ли сделать что-то лучше, чем просто перечислить объекты и пересчитать их один за другим? Нужно ли нам полностью выписать наши данные, чтобы понять, достаточно ли их для обучения нашей модели? Можем ли мы оценить, какое время будет работать алгоритм без того, чтобы реализовывать и запускать его? Все эти вопросы изучает раздел математики, который называется комбинаторика. Мы начнем изучать эту область математики, что позволит нам отвечать на перечисленные выше вопросы в простых случаях.

2. Продвинутые подсчеты

Мы рассмотрели несколько стандартных постановок комбинаторики, что уже позволит решать многие задачи о подсчетах. Мы преследуем две цели. Во-первых, мы подробно обсудим более сложные постановки в комбинаторике. Мы подробно обсудим числа сочетаний. Мы рассмотрим еще одну новую стандартную постановку комбинаторики — сочетания с повторениями. Во-вторых, мы попрактикуемся в решении задач на подсчеты. Для этого мы в частности разберем примеры решений нескольких задач.

3. Дискретная вероятность

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

4. Основы теории графов

Графы представляют собой одну из самых часто встречающихся комбинаторных моделей. Они возникают везде, где у нас есть какие-то соотношения между парами объектов. С другой стороны, у графов есть нетривиальные общие свойства, которые, таким образом, оказываются полезными в самых разных практических ситуациях. На этой неделе мы начнем обсуждение графов. Мы обсудим базовые параметры и обходы модели, а также специальный класс — двудольные графы.

5. Деревья и ориентированные графы

Обсудим  все основные понятия, связанные с графами. Также мы обсудим графы без циклов, ориентированные графы, которые моделируют практические ситуации, в которых отношения между объектами несимметричны. 

6. Проект: случайные блуждания в графах

Научимся применять полученные знания для построения рекомендательной системы. Сначала обсудим общую постановку и рассмотрим наш основной инструмент — случайные блуждания на графах. Затем используем случайные блуждания для предсказания связей в графах, взятых из практики.

- Умение работать в анализе данных или в Computer Science

- Применение комбинаторных моделей 

- Построение несложной рекомендательной системы