Об этом курсе

Недавно просмотрено: 3,892

Сертификат, ссылками на который можно делиться с другими людьми

Получите сертификат по завершении

100% онлайн

Начните сейчас и учитесь по собственному графику.

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.

Прибл. 18 часа на выполнение

Русский

Субтитры: Русский

Сертификат, ссылками на который можно делиться с другими людьми

Получите сертификат по завершении

100% онлайн

Начните сейчас и учитесь по собственному графику.

Гибкие сроки

Назначьте сроки сдачи в соответствии со своим графиком.

Прибл. 18 часа на выполнение

Русский

Субтитры: Русский

от партнера

Логотип Московский физико-технический институт

Московский физико-технический институт

Программа курса: что вы изучите

Неделя
1

Неделя 1

3 ч. на завершение

Две модели случайного графа

3 ч. на завершение
15 видео ((всего 94 мин.)), 4 материалов для самостоятельного изучения, 2 тестов
15 видео
МФТИ1мин
История зарождения понятия случайного графа4мин
Биномиальная модель случайного графа12мин
Связность случайного графа на четырех вершинах3мин
Эволюция случайного графа6мин
Равномерная модель случайного графа3мин
Пороговая вероятность для свойства связности: формулировка теоремы14мин
Нижняя оценка вероятности связности: формулировка теоремы12мин
Теорема о появлении гигантской компоненты в случайном графе10мин
Задача о монотонности вероятности4мин
Задача о промежуточных значениях вероятности5мин
Задача о дополнительных ребрах3мин
Задача об одном ребре2мин
Задача о дереве4мин
Задача о простом цикле3мин
4 материала для самостоятельного изучения
МФТИ10мин
Комментарий к лекции10мин
Дополнительные задачи10мин
Конспект лекции10мин
2 практического упражнения
Задачи к семинару 112мин
Итоговые задания по неделе 120мин
Неделя
2

Неделя 2

3 ч. на завершение

Теорема о пороговой вероятности для свойства связности

3 ч. на завершение
16 видео ((всего 132 мин.)), 3 материалов для самостоятельного изучения, 2 тестов
16 видео
Напоминание теоремы о пороговой вероятности для свойства связности2мин
Применение неравенства Чебышева9мин
Оценивание математического ожидания10мин
Оценивание дисперсии10мин
Вероятность существования изолированной вершины5мин
Разложение случайного графа на компоненты связности2мин
Оценивание математического ожидания числа компонент связности15мин
Представление оценки в виде суммы двух слагаемых5мин
Предел первого слагаемого10мин
Предел второго слагаемого9мин
Задача о количестве изолированных вершин в случайном двудольном графе8мин
Задача о существовании изолированной вершины в случайном двудольном графе17мин
Задача об одной изолированной вершине4мин
Задача о количестве вершин степени 14мин
Задача о связности случайного графа при большой вероятности проведения ребра8мин
3 материала для самостоятельного изучения
Комментарий к задаче о существовании изолированной вершины в случайном двудольном графе10мин
Дополнительные задачи10мин
Конспект лекции10мин
2 практического упражнения
Задачи к семинару 210мин
Итоговые задания по неделе 218мин
Неделя
3

Неделя 3

3 ч. на завершение

Вероятностный метод

3 ч. на завершение
15 видео ((всего 102 мин.)), 3 материалов для самостоятельного изучения, 2 тестов
15 видео
Обхват графа2мин
Теорема о графе с большим обхватом и большим хроматическим числом: формулировка теоремы и идея доказательства5мин
Введение случайности5мин
Оценка математического ожидания числа циклов15мин
Применение неравенства Маркова для оценивания обхвата3мин
Оценка математического ожидания числа независимых множеств7мин
Применение неравенства Маркова для оценивания числа независимости6мин
Существование графа с большим хроматическим числом и малым количеством циклов1мин
Модификация графа6мин
Задача о количестве 4-циклов в случайном двудольном графе15мин
Задача об отсутствии циклов в равномерной модели1мин
Задача о хроматическом числе случайного графа в равномерной модели4мин
Задача об оценке числа независимости7мин
Задача о хроматическом числе случайного графа с 5 ребрами7мин
3 материала для самостоятельного изучения
Замечание: существование длинных циклов10мин
Дополнительные задачи10мин
Конспект лекции10мин
2 практического упражнения
Задачи к семинару 310мин
Итоговые задания по неделе 318мин
Неделя
4

Неделя 4

3 ч. на завершение

Хроматическое число случайного графа

3 ч. на завершение
14 видео ((всего 113 мин.)), 3 материалов для самостоятельного изучения, 2 тестов
14 видео
Доказательство теоремы11мин
Хроматическое число случайного графа без ребер5мин
Хроматическое число сильно разреженного случайного графа4мин
Доказательство того, что в случайном разреженном графе отсутствуют циклы6мин
Хроматическое число случайного графа G(n,c/n)10мин
Хроматическое число слабо разреженного графа9мин
Точная асимптотика хроматического числа G(n,0.5)5мин
Идея доказательства теоремы Боллобаша7мин
Алгоритм покраски10мин
Задача о хроматическом числе и обхвате случайного двудольного графа10мин
Задача о хроматическом числа графа G(6,5)5мин
Задача о древесных компонентах случайного графа14мин
Задача об оценке хроматического числа случайного графа специального вида3мин
3 материала для самостоятельного изучения
Комментарий к лекции: тройка вместо двойки10мин
Дополнительные задачи10мин
Конспект лекции10мин
2 практического упражнения
Задачи к семинару 48мин
Итоговые задания по неделе 414мин

Рецензии

Лучшие отзывы о курсе СЛУЧАЙНЫЕ ГРАФЫ
Посмотреть все отзывы

Часто задаваемые вопросы

  • Зарегистрировавшись на сертификацию, вы получите доступ ко всем видео, тестам и заданиям по программированию (если они предусмотрены). Задания по взаимной оценке сокурсниками можно сдавать и проверять только после начала сессии. Если вы проходите курс без оплаты, некоторые задания могут быть недоступны.

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

Остались вопросы? Посетите Центр поддержки учащихся.