Об этом курсе
4.9
Оценки: 63
Рецензии: 7
100% онлайн

100% онлайн

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

Гибкие сроки

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

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

Предполагаемая нагрузка: 6 недель исследования, 1-2 часов / неделю...
Доступные языки

Русский

Субтитры: Русский...
100% онлайн

100% онлайн

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

Гибкие сроки

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

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

Предполагаемая нагрузка: 6 недель исследования, 1-2 часов / неделю...
Доступные языки

Русский

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

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

Неделя
1
Часов на завершение
3 ч. на завершение

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

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

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

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

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

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

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

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

Преподавателя

Avatar

Андрей Райгородский

профессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Avatar

Максим Жуковский

преподаватель
кафедра дискретной математики МФТИ

О Moscow Institute of Physics and Technology

Московский физико-технический институт (неофициально известный как МФТИ или Физтех) является одним из самых престижных в мире учебных и научно-исследовательских институтов. Он готовит высококвалифицированных специалистов в области теоретической и прикладной физики, прикладной математики, информатики, биотехнологии и смежных дисциплин. Физтех был основан в 1951 году Нобелевской премии лауреатами Петром Капицей, Николаем Семеновым, Львом Ландау и Сергеем Христиановичем. Основой образования в МФТИ является уникальная «система Физтеха»: кропотливое воспитание и отбор самых талантливых абитуриентов, фундаментальное образование высшего класса и раннее вовлечение студентов в реальную научно-исследовательскую работу. Среди выпускников МФТИ есть Нобелевские лауреаты, основатели всемирно известных компаний, известные космонавты, изобретатели, инженеры....

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

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

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

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