À propos de ce cours
4.9
63 notes
7 avis
Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей....
Globe

Cours en ligne à 100 %

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.
Calendar

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.
Clock

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

Approx. 22 heures pour terminer
Comment Dots

Russian

Sous-titres : Russian
Globe

Cours en ligne à 100 %

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.
Calendar

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.
Clock

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

Approx. 22 heures pour terminer
Comment Dots

Russian

Sous-titres : Russian

Programme du cours : ce que vous apprendrez dans ce cours

1

Section
Clock
3 heures pour terminer

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

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

2

Section
Clock
3 heures pour terminer

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

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

3

Section
Clock
3 heures pour terminer

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

Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом....
Reading
15 vidéos (Total 102 min), 3 lectures, 2 quiz
Video15 vidéos
Обхват графа2 min
Теорема о графе с большим обхватом и большим хроматическим числом: формулировка теоремы и идея доказательства5 min
Введение случайности5 min
Оценка математического ожидания числа циклов15 min
Применение неравенства Маркова для оценивания обхвата3 min
Оценка математического ожидания числа независимых множеств7 min
Применение неравенства Маркова для оценивания числа независимости6 min
Существование графа с большим хроматическим числом и малым количеством циклов1 min
Модификация графа6 min
Задача о количестве 4-циклов в случайном двудольном графе15 min
Задача об отсутствии циклов в равномерной модели1 min
Задача о хроматическом числе случайного графа в равномерной модели4 min
Задача об оценке числа независимости7 min
Задача о хроматическом числе случайного графа с 5 ребрами7 min
Reading3 lectures
Замечание: существование длинных циклов10 min
Дополнительные задачи10 min
Конспект лекции10 min
Quiz2 exercices pour s'entraîner
Задачи к семинару 310 min
Итоговые задания по неделе 318 min

4

Section
Clock
3 heures pour terminer

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

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

Enseignants

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

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

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

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

À propos de Moscow Institute of Physics and Technology

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

Foire Aux 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.

D'autres questions ? Visitez le Centre d'Aide pour les Etudiants.