À propos de ce cours
4.9
63 notes
7 avis
100 % en ligne

100 % en ligne

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.
Dates limites flexibles

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.
Heures pour terminer

Approx. 23 heures pour terminer

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

Russe

Sous-titres : Russe
100 % en ligne

100 % en ligne

Commencez dès maintenant et apprenez aux horaires qui vous conviennent.
Dates limites flexibles

Dates limites flexibles

Réinitialisez les dates limites selon votre disponibilité.
Heures pour terminer

Approx. 23 heures pour terminer

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

Russe

Sous-titres : Russe

Programme du cours : ce que vous apprendrez dans ce cours

Semaine
1
Heures pour terminer
3 heures pour terminer

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

Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе....
Reading
15 videos (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
Semaine
2
Heures pour terminer
3 heures pour terminer

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

Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа....
Reading
16 videos (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
Semaine
3
Heures pour terminer
3 heures pour terminer

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

Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом....
Reading
15 videos (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
Semaine
4
Heures pour terminer
3 heures pour terminer

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

Оценки хроматического числа случайного графа G(n,p) при различных p=p(n)....
Reading
14 videos (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

Avatar

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

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

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

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

À propos de Moscow Institute of Physics and Technology

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

Foire Aux Questions

  • Une fois que vous êtes inscrit(e) pour un Certificat, vous pouvez accéder à toutes les vidéos de cours, et à tous les quiz et exercices de programmation (le cas échéant). Vous pouvez soumettre des devoirs à examiner par vos pairs et en examiner vous-même uniquement après le début de votre session. Si vous préférez explorer le cours sans l'acheter, vous ne serez peut-être pas en mesure d'accéder à certains devoirs.

  • Lorsque vous achetez un Certificat, vous bénéficiez d'un accès à tout le contenu du cours, y compris les devoirs notés. Lorsque vous avez terminé et réussi le cours, votre Certificat électronique est ajouté à votre page Accomplissements. À partir de cette page, vous pouvez imprimer votre Certificat ou l'ajouter à votre profil LinkedIn. Si vous souhaitez seulement lire et visualiser le contenu du cours, vous pouvez accéder gratuitement au cours en tant qu'auditeur libre.

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