Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен?
Offert par
Случайные графы
Institut de physique et de technologie de MoscouÀ propos de ce cours
4,142 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. 18 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. 18 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
Задачи к семинару 112 min
Итоговые задания по неделе 120 min
3 heures pour terminer
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
3 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
Задачи к семинару 210 min
Итоговые задания по неделе 218 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
Задачи к семинару 310 min
Итоговые задания по неделе 318 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
Задачи к семинару 48 min
Итоговые задания по неделе 414 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 ?
Access to lectures and assignments depends on your type of enrollment. If you take a course in audit mode, you will be able to see most course materials for free. To access graded assignments and to earn a Certificate, you will need to purchase the Certificate experience, during or after your audit. If you don't see the audit option:
- The course may not offer an audit option. You can try a Free Trial instead, or apply for Financial Aid.
- The course may offer 'Full Course, No Certificate' instead. This option lets you see all course materials, submit required assessments, and get a final grade. This also means that you will not be able to purchase a Certificate experience.
À 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.
Quelle est la politique de remboursement ?
Vous avez droit à un remboursement intégral jusqu'à deux semaines après la date de paiement ou (pour les cours qui viennent d'être lancés) jusqu'à deux semaines après le début de la première session du cours, selon la dernière de ces éventualités. Vous ne pouvez pas bénéficier d'un remboursement une fois votre Certificat de Cours obtenu, même si vous terminez le cours pendant la période de remboursement de deux semaines. Consultez notre Politique de remboursement complète.
Une aide financière est-elle possible ?
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.
