Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен?
от партнера
Случайные графы
Московский физико-технический институтОб этом курсе
Недавно просмотрено: 4,886
Сертификат, ссылками на который можно делиться с другими людьми
Получите сертификат по завершении
100% онлайн
Начните сейчас и учитесь по собственному графику.
Гибкие сроки
Назначьте сроки сдачи в соответствии со своим графиком.
Прибл. 18 часов на выполнение
Русский
Субтитры: Русский
Сертификат, ссылками на который можно делиться с другими людьми
Получите сертификат по завершении
100% онлайн
Начните сейчас и учитесь по собственному графику.
Гибкие сроки
Назначьте сроки сдачи в соответствии со своим графиком.
Прибл. 18 часов на выполнение
Русский
Субтитры: Русский
от партнера
Московский физико-технический институт
Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира. Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой.
Программа курса: что вы изучите
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мин
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 ч. на завершение
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мин
3 ч. на завершение
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
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мин
Рецензии
Лучшие отзывы о курсе СЛУЧАЙНЫЕ ГРАФЫ
от партнера VT17 окт. 2016 г.
Прошел курс исключительно из за лектора. Даже не знаю, пригодится ли мне на практике, но очень захватывающе изложено.
Часто задаваемые вопросы
Когда я получу доступ к лекциям и заданиям?
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 предоставляет финансовую помощь учащимся, которые не могут оплатить обучение. Чтобы подать заявление, перейдите по ссылке 'Финансовая помощь' слева под кнопкой 'Зарегистрироваться' и заполните форму. Если его примут, вы получите уведомление. Подробнее
Остались вопросы? Посетите Центр поддержки учащихся.
