Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен?
Случайные графы
Institut de physique et de technologie de MoscouÀ propos de ce cours
4,455 consultations récentes
Certificat partageable
Obtenez un Certificat lorsque vous terminez
100 % en ligne
Commencez dès maintenant et apprenez aux horaires qui vous conviennent.
Dates limites flexibles
Réinitialisez les dates limites selon votre disponibilité.
Approx. 21 heures pour terminer
Russe
Sous-titres : Russe
Certificat partageable
Obtenez un Certificat lorsque vous terminez
100 % en ligne
Commencez dès maintenant et apprenez aux horaires qui vous conviennent.
Dates limites flexibles
Réinitialisez les dates limites selon votre disponibilité.
Approx. 21 heures pour terminer
Russe
Sous-titres : Russe
Offert par
Institut de physique et de technologie de Moscou
Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира. Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой.
Programme du cours : ce que vous apprendrez dans ce cours
3 heures pour terminer
Две модели случайного графа
Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе.
3 heures pour terminer
15 vidéos (Total 94 min), 4 lectures, 2 quiz
15 vidéos
МФТИ1 min
История зарождения понятия случайного графа4 min
Биномиальная модель случайного графа12 min
Связность случайного графа на четырех вершинах3 min
Эволюция случайного графа6 min
Равномерная модель случайного графа3 min
Пороговая вероятность для свойства связности: формулировка теоремы14 min
Нижняя оценка вероятности связности: формулировка теоремы12 min
Теорема о появлении гигантской компоненты в случайном графе10 min
Задача о монотонности вероятности4 min
Задача о промежуточных значениях вероятности5 min
Задача о дополнительных ребрах3 min
Задача об одном ребре2 min
Задача о дереве4 min
Задача о простом цикле3 min
4 lectures
МФТИ10 min
Комментарий к лекции10 min
Дополнительные задачи10 min
Конспект лекции10 min
2 exercices pour s'entraîner
Задачи к семинару 130 min
Итоговые задания по неделе 130 min
4 heures pour terminer
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
4 heures pour terminer
16 vidéos (Total 132 min), 3 lectures, 2 quiz
16 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
3 lectures
Комментарий к задаче о существовании изолированной вершины в случайном двудольном графе10 min
Дополнительные задачи10 min
Конспект лекции10 min
2 exercices pour s'entraîner
Задачи к семинару 230 min
Итоговые задания по неделе 230 min
3 heures pour terminer
Вероятностный метод
Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом.
3 heures pour terminer
15 vidéos (Total 102 min), 3 lectures, 2 quiz
15 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
3 lectures
Замечание: существование длинных циклов10 min
Дополнительные задачи10 min
Конспект лекции10 min
2 exercices pour s'entraîner
Задачи к семинару 330 min
Итоговые задания по неделе 330 min
3 heures pour terminer
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
3 heures pour terminer
14 vidéos (Total 113 min), 3 lectures, 2 quiz
14 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
3 lectures
Комментарий к лекции: тройка вместо двойки10 min
Дополнительные задачи10 min
Конспект лекции10 min
2 exercices pour s'entraîner
Задачи к семинару 430 min
Итоговые задания по неделе 430 min
Avis
Meilleurs avis pour СЛУЧАЙНЫЕ ГРАФЫ
par VT17 oct. 2016
Прошел курс исключительно из за лектора. Даже не знаю, пригодится ли мне на практике, но очень захватывающе изложено.
Foire Aux Questions
Quand aurai-je accès aux vidéos de cours et aux devoirs ?
L’accès à des vidéos de cours et des devoirs dépend de votre type d’inscription. Si vous suivez un cours en mode auditeur libre, vous pourrez voir la plupart des contenus de cours gratuitement. Pour accéder aux devoirs notés et obtenir un certificat, vous devrez acheter une expérience de certificat, pendant ou après avoir assister au cours en tant qu’auditeur libre. Si vous ne visualisez pas l’option auditeur libre :
- Il est possible que le cours ne propose pas d’option auditeur libre. Vous pouvez en revanche accéder à un essai gratuit ou faire une demande d'aide financière.
- Le cours propose peut-être « Cours complet, aucun certificat » à la place. Cette option vous permet de voir tous les contenus de cours, de soumettre les évaluations requises et d'obtenir une note finale. Cependant, vous ne pourrez pas acheter une expérience de certificat.
À quoi ai-je droit si j'achète le Certificat ?
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.
Is financial aid available?
Oui, Coursera fournit une Aide Financière aux étudiants n'ayant pas les moyens d'acquitter les frais. Pour en faire la demande, cliquez sur le lien Aide Financière situé sous le bouton S'inscrire ci-contre à gauche. Vous serez invité(e) à déposer une demande et vous serez averti(e) si elle est acceptée. En savoir plus.
D'autres questions ? Visitez le Centre d'Aide pour les Etudiants.
