About this Course
1,606 recent views

100% online

Start instantly and learn at your own schedule.

Flexible deadlines

Reset deadlines in accordance to your schedule.

Approx. 23 hours to complete

Suggested: 6 недель исследования, 1-2 часов / неделю...

Russian

Subtitles: Russian

100% online

Start instantly and learn at your own schedule.

Flexible deadlines

Reset deadlines in accordance to your schedule.

Approx. 23 hours to complete

Suggested: 6 недель исследования, 1-2 часов / неделю...

Russian

Subtitles: Russian

Syllabus - What you will learn from this course

Week
1
3 hours to complete

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

15 videos (Total 94 min), 4 readings, 2 quizzes
15 videos
Связность случайного графа на четырех вершинах3m
Эволюция случайного графа6m
Равномерная модель случайного графа3m
Пороговая вероятность для свойства связности: формулировка теоремы14m
Нижняя оценка вероятности связности: формулировка теоремы12m
Теорема о появлении гигантской компоненты в случайном графе10m
Задача о монотонности вероятности4m
Задача о промежуточных значениях вероятности5m
Задача о дополнительных ребрах3m
Задача об одном ребре2m
Задача о дереве4m
Задача о простом цикле3m
4 readings
МФТИ10m
Комментарий к лекции10m
Дополнительные задачи10m
Конспект лекции10m
2 practice exercises
Задачи к семинару 112m
Итоговые задания по неделе 120m
Week
2
3 hours to complete

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

16 videos (Total 132 min), 3 readings, 2 quizzes
16 videos
Оценивание математического ожидания10m
Оценивание дисперсии10m
Вероятность существования изолированной вершины5m
Разложение случайного графа на компоненты связности2m
Оценивание математического ожидания числа компонент связности15m
Представление оценки в виде суммы двух слагаемых5m
Предел первого слагаемого10m
Предел второго слагаемого9m
Задача о количестве изолированных вершин в случайном двудольном графе8m
Задача о существовании изолированной вершины в случайном двудольном графе17m
Задача об одной изолированной вершине4m
Задача о количестве вершин степени 14m
Задача о связности случайного графа при большой вероятности проведения ребра8m
3 readings
Комментарий к задаче о существовании изолированной вершины в случайном двудольном графе10m
Дополнительные задачи10m
Конспект лекции10m
2 practice exercises
Задачи к семинару 210m
Итоговые задания по неделе 218m
Week
3
3 hours to complete

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

15 videos (Total 102 min), 3 readings, 2 quizzes
15 videos
Введение случайности5m
Оценка математического ожидания числа циклов15m
Применение неравенства Маркова для оценивания обхвата3m
Оценка математического ожидания числа независимых множеств7m
Применение неравенства Маркова для оценивания числа независимости6m
Существование графа с большим хроматическим числом и малым количеством циклов1m
Модификация графа6m
Задача о количестве 4-циклов в случайном двудольном графе15m
Задача об отсутствии циклов в равномерной модели1m
Задача о хроматическом числе случайного графа в равномерной модели4m
Задача об оценке числа независимости7m
Задача о хроматическом числе случайного графа с 5 ребрами7m
3 readings
Замечание: существование длинных циклов10m
Дополнительные задачи10m
Конспект лекции10m
2 practice exercises
Задачи к семинару 310m
Итоговые задания по неделе 318m
Week
4
3 hours to complete

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

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

Top reviews from Случайные графы

By VVOct 15th 2016

Хорошо составленный, интересный курс. Не слишком простой и не слишком сложный. Андрей Михайлович - один из лучших лекторов, которых я видел.

By VTOct 18th 2016

Прошел курс исключительно из за лектора. Даже не знаю, пригодится ли мне на практике, но очень захватывающе изложено.

Instructors

Avatar

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

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

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

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

About Moscow Institute of Physics and Technology

Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира. Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой. Основой образования в МФТИ является уникальная «система Физтеха», сформулированная Петром Капицей: кропотливый отбор одаренных и склонных к творческой работе абитуриентов; участие в обучении ведущих научных работников; индивидуальный подход к отдельным студентам с целью развития их творческих задатков; воспитание с первых шагов в атмосфере технических исследований и конструктивного творчества с использованием потенциала лучших лабораторий страны. Среди выпускников МФТИ — нобелевские лауреаты Андрей Гейм и Константин Новоселов, основатель компании ABBYY Давид Ян, один из авторов архитектурных принципов построения вычислительных комплексов Борис Бабаян и др....

Frequently Asked Questions

  • Once you enroll for a Certificate, you’ll have access to all videos, quizzes, and programming assignments (if applicable). Peer review assignments can only be submitted and reviewed once your session has begun. If you choose to explore the course without purchasing, you may not be able to access certain assignments.

  • When you purchase a Certificate you get access to all course materials, including graded assignments. Upon completing the course, your electronic Certificate will be added to your Accomplishments page - from there, you can print your Certificate or add it to your LinkedIn profile. If you only want to read and view the course content, you can audit the course for free.

More questions? Visit the Learner Help Center.