Компьютерные науки

Дискретный анализ и теория вероятностей

В программе представлено глубокое погружение в математические инструменты для анализа конечных и случайных систем. Объединены перечислительная комбинаторика, производящие функции, теория графов и теория вероятностей с демонстрацией их применения на классических задачах асимптотического анализа.
Студентов 1325 Выпускников 68 Для специалистов
690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
Объем
36 час.
Длительность
30 дней
Нагрузка в неделю
9 час.
Формат обучения
Дистанционно (самостоятельно)
Описание Этот цикл занятий охватывает ключевые разделы дискретной математики, необходимые для понимания сложных алгоритмов. Обучение начинается с перечислительной комбинаторики и асимптотического анализа, переходя к свойствам графов и хроматических чисел. Большой блок материалов посвящен вероятностным методам, включая схему Бернулли и предельные теоремы. Также рассматриваются специфические инструменты, такие как локальная лемма Ловаса и размерность Вапника-Червоненкиса. Учебный курс поможет ИТ-специалистам систематизировать представления о стохастических процессах.
Цели
  • Сформировать целостное представление о методах дискретного и асимптотического анализа.
  • Развить навыки использования вероятностных подходов при решении комбинаторных задач.
  • Систематизировать знания о свойствах графов и методах их раскраски.
  • Подготовить к использованию аппарата производящих функций для анализа рекуррентных соотношений.
Чему я научусь?
  • Применять методы перечислительной комбинаторики для решения прикладных задач.
  • Использовать аппарат производящих функций и линейных рекуррентных соотношений.
  • Оценивать хроматические числа графов и анализировать их структуру.
  • Вычислять вероятности событий и параметры распределений случайных величин.
  • Применять локальную лемму Ловаса и теорию Вапника-Червоненкиса в анализе данных.

Авторы

Райгородский Андрей Михайлович
Райгородский Андрей Михайлович
Доктор физико-математических наук. Профессор кафедры математической статистики и случайных процессов механико-математического факультета МГУ им. М. В. Ломоносова. Заведующий кафедрой Дискретной математики ФИВТ МФТИ.
Чему я научусь?
  • Применять методы перечислительной комбинаторики для решения прикладных задач.
  • Использовать аппарат производящих функций и линейных рекуррентных соотношений.
  • Оценивать хроматические числа графов и анализировать их структуру.
  • Вычислять вероятности событий и параметры распределений случайных величин.
  • Применять локальную лемму Ловаса и теорию Вапника-Червоненкиса в анализе данных.

Учебный план

№ Занятия
Экзамен экстерном Внимание! Экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите подтвердить свои знания по данному курсу без его изучения или поверить свои знания по нему. Экзамен экстерном можно сдать только один раз. 90 мин
1 Основы перечислительной комбинаторики Числа сочетания (с повторениями и без повторений), числа размещения (с повторениями и без повторений), перестановки. Бином... Числа сочетания (с повторениями и без повторений), числа размещения (с повторениями и без повторений), перестановки. Бином Ньютона и биномиальные коэффициенты. Полиномиальная формула и полиномиальные коэффициенты. Формула включений и исключений. ещё
Основы перечислительной комбинаторики тест для курса Дискретный анализ и теория вероятностей 60 мин
2 Обобщенная функция Мёбиуса и асимптотики Простейшие комбинаторные тождества. Знакопеременные тождества. Использование формулы включений и исключений для доказательства тождеств. Функция Мёбиуса и... Простейшие комбинаторные тождества. Знакопеременные тождества. Использование формулы включений и исключений для доказательства тождеств. Функция Мёбиуса и формула обращения Мёбиуса. Подсчет числа циклических последовательностей. Элементарные оценки факториалов, биномиальных коэффициентов и пр. Понятие об энтропии. Неравенство Чернова. Формула Стирлинга (б/д). Асимптотики для биномиальных коэффициентов и пр. ещё
Обобщенная функция Мёбиуса и асимптотики тест для курса Дискретный анализ и теория вероятностей 60 мин
3 Деревья и унициклические графы "Основные понятия теории графов. Перечисление деревьев на n вершинах (формула Кэли): подход с производящими функциями
Деревья и унициклические графы тест для курса Дискретный анализ и теория вероятностей 60 мин
4 Разбиение чисел на слагаемые Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Рекуррентные соотношения для функций разбиения. Харди-Рамануджана... Задачи о разбиениях чисел на слагаемые. Упорядоченные и неупорядоченные разбиения. Рекуррентные соотношения для функций разбиения. Харди-Рамануджана (б/д). ещё
Разбиение чисел на слагаемые тест для курса Дискретный анализ и теория вероятностей 60 мин
5 Производящие функции и линейные рекуррентные соотношения Линейные рекуррентные соотношения с постоянными коэффициентами. Степенные ряды и производящие функции. Применение степенных рядов и производящих... Линейные рекуррентные соотношения с постоянными коэффициентами. Степенные ряды и производящие функции. Применение степенных рядов и производящих функций для доказательства комбинаторных тождеств. Применение степенных рядов и производящих функций для решения рекуррентных соотношений. Числа Каталана, Стирлинга, Бернулли и др. Их применения. ещё
Производящие функции и линейные рекуррентные соотношения тест для курса Дискретный анализ и теория вероятностей 60 мин
6 Хроматические числа графов и Кнезеровский граф Хроматические числа графов. Гипотеза Кнезера. Теорема Ловаса.
Хроматические числа графов и Кнезеровский граф тест для курса Дискретный анализ и теория вероятностей 60 мин
7 Классическое определение вероятности, схема Бернулли и их применение к числам Рамсея Классическое определение вероятности. Геометрические вероятности. Парадокс Бертрана. Условные вероятности. Независимость событий. Формулы полной вероятности и Байеса.... Классическое определение вероятности. Геометрические вероятности. Парадокс Бертрана. Условные вероятности. Независимость событий. Формулы полной вероятности и Байеса. Схема Бернулли. Полиномиальная схема. Схема серий. Случайные блуждания. Понятие о случайном графе. Перколяция. Метод Монте-Карло. ещё
Классическое определение вероятности, схема Бернулли и их применение к числам Рамсея тест для курса Дискретный анализ и теория вероятностей 60 мин
8 Локальная лемма Ловаса. Начала теории вероятностей Числа Рамсея. Раскраски гиперграфов.
9 Локальная лемма Ловаса. Теория вероятностей Покрытие графов линейными лесами.
Локальная лемма Ловаса. Теория вероятностей тест для курса Дискретный анализ и теория вероятностей 60 мин
10 Распределения случайных величин Дискретные и абсолютно непрерывные распределения. Основные виды распределений: биномиальное, геометрическое, пуассоновское, гипергеометрическое, равномерное, нормальное, показательное, гамма-распределение,... Дискретные и абсолютно непрерывные распределения. Основные виды распределений: биномиальное, геометрическое, пуассоновское, гипергеометрическое, равномерное, нормальное, показательное, гамма-распределение, хи-квадрат, Стьюдента, Фишера и пр. Числовые характеристики распределений: математическое ожидание, дисперсия, моменты, факториальные моменты. Совместные распределения. Ковариация и корреляция. Независимость и некоррелированность случайных величин. Понятие о вариационном ряде. Распределения, математические ожидания, дисперсии и ковариации порядковых статистик. ещё
Распределения случайных величин тест для курса Дискретный анализ и теория вероятностей 60 мин
11 Предельные теоремы Неравенства Маркова и Чебышёва. Закон больших чисел для схемы Бернулли. Закон больших чисел в форме Чебышёва.... Неравенства Маркова и Чебышёва. Закон больших чисел для схемы Бернулли. Закон больших чисел в форме Чебышёва. Закон больших чисел в форме Хинчина. Неравенство Колмогорова. Усиленный закон больших чисел. Предельные теоремы Муавра-Лапласа для схемы Бернулли (локальная и интегральная). ещё
12 Предельные теоремы (продолжение) "Предельная теорема Пуассона для схемы серий. Производящие и характеристические функции. Центральная предельная теорема (различные формулировки
Предельные теоремы (продолжение) тест для курса Дискретный анализ и теория вероятностей 60 мин
13 Размерность Вапника-Червоненкиса Понятие о выборке и выборочном пространстве. Точечное оценивание параметров. Несмещенность, состоятельность и пр. Методы моментов и... Понятие о выборке и выборочном пространстве. Точечное оценивание параметров. Несмещенность, состоятельность и пр. Методы моментов и максимального правдоподобия. Доверительное оценивание. Методы построения доверительных интервалов. ещё
Размерность Вапника-Червоненкиса тест для курса Дискретный анализ и теория вероятностей 60 мин
Тренировочный экзамен Внимание! Тренировочный экзамен экстерном не обязательный для сдачи. При желании вы можете его пройти, если хотите проверить свои знания курса перед сдачей экзамена. Тренировочный экзамен можно сдавать сколько угодно один раз. 90 мин
Экзамен 60 мин

Какой документ я получу?

Сертификат

Выдаётся автоматически после успешного завершения программы.

Удостоверение о повышении квалификации

Выдается при наличии среднего специального или высшего образования (необходимые документы).

Стоимость программы

690 ₽ 1 200 ₽
или любая сумма на ваше усмотрение
Вы можете оплатить любую сумму, чтобы поддержать наш проект и авторов программы. Объем услуг не зависит от размера вашей оплаты.
^