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

Основная цель этого онлайн-курса — дать введение в разделы дискретной математики, важные для анализа данных.

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

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