Об этом курсе

Недавно просмотрено: 4,886
Сертификат, ссылками на который можно делиться с другими людьми
Получите сертификат по завершении
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мин

Рецензии

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

Посмотреть все отзывы

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

  • Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:

    • The course may not offer an audit option. You can try a Free Trial instead, or apply for Financial Aid.
    • The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
  • Оплатив сертификацию, вы получите доступ ко всем материалам курса, включая оцениваемые задания. После успешного прохождения курса на странице ваших достижений появится электронный сертификат. Оттуда его можно распечатать или прикрепить к профилю LinkedIn. Просто ознакомиться с содержанием курса можно бесплатно.

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

  • Да, Coursera предоставляет финансовую помощь учащимся, которые не могут оплатить обучение. Чтобы подать заявление, перейдите по ссылке 'Финансовая помощь' слева под кнопкой 'Зарегистрироваться' и заполните форму. Если его примут, вы получите уведомление. Подробнее

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