Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен?
Случайные графы
Московский физико-технический институтОб этом курсе
Недавно просмотрено: 2,312
Сертификат, ссылками на который можно делиться с другими людьми
Получите сертификат по завершении
100% онлайн
Начните сейчас и учитесь по собственному графику.
Гибкие сроки
Назначьте сроки сдачи в соответствии со своим графиком.
Прибл. 21 час на выполнение
Русский
Субтитры: Русский
Сертификат, ссылками на который можно делиться с другими людьми
Получите сертификат по завершении
100% онлайн
Начните сейчас и учитесь по собственному графику.
Гибкие сроки
Назначьте сроки сдачи в соответствии со своим графиком.
Прибл. 21 час на выполнение
Русский
Субтитры: Русский
от партнера
Московский физико-технический институт
Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира. Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой.
Программа курса: что вы изучите
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 практических упражнения
Задачи к семинару 130мин
Итоговые задания по неделе 130мин
4 ч. на завершение
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
4 ч. на завершение
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 практических упражнения
Задачи к семинару 230мин
Итоговые задания по неделе 230мин
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 практических упражнения
Задачи к семинару 330мин
Итоговые задания по неделе 330мин
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 практических упражнения
Задачи к семинару 430мин
Итоговые задания по неделе 430мин
Рецензии
Лучшие отзывы о курсе СЛУЧАЙНЫЕ ГРАФЫ
от партнера VV14 окт. 2016 г.
Хорошо составленный, интересный курс. Не слишком простой и не слишком сложный. Андрей Михайлович - один из лучших лекторов, которых я видел.
от партнера VT17 окт. 2016 г.
Прошел курс исключительно из за лектора. Даже не знаю, пригодится ли мне на практике, но очень захватывающе изложено.
Часто задаваемые вопросы
Когда я получу доступ к лекциям и заданиям?
Что я получу, оплатив сертификацию?
Is financial aid available?
Остались вопросы? Посетите Центр поддержки учащихся.
