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

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

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

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

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

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