Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен?
Случайные графы
莫斯科物理科学与技术学院課程信息
3,604 次近期查看
可分享的證書
完成後獲得證書
100% 在線
立即開始，按照自己的計劃學習。
可靈活調整截止日期
根據您的日程表重置截止日期。
完成時間大約為18 小時
俄語（Russian）
字幕：俄語（Russian）
可分享的證書
完成後獲得證書
100% 在線
立即開始，按照自己的計劃學習。
可靈活調整截止日期
根據您的日程表重置截止日期。
完成時間大約為18 小時
俄語（Russian）
字幕：俄語（Russian）
提供方
莫斯科物理科学与技术学院
Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира. Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой.
教學大綱 - 您將從這門課程中學到什麼
完成時間為 3 小時
Две модели случайного графа
Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе.
完成時間為 3 小時
15 個視頻 （總計 94 分鐘）, 4 個閱讀材料, 2 個測驗
15 個視頻
МФТИ1分鐘
История зарождения понятия случайного графа4分鐘
Биномиальная модель случайного графа12分鐘
Связность случайного графа на четырех вершинах3分鐘
Эволюция случайного графа6分鐘
Равномерная модель случайного графа3分鐘
Пороговая вероятность для свойства связности: формулировка теоремы14分鐘
Нижняя оценка вероятности связности: формулировка теоремы12分鐘
Теорема о появлении гигантской компоненты в случайном графе10分鐘
Задача о монотонности вероятности4分鐘
Задача о промежуточных значениях вероятности5分鐘
Задача о дополнительных ребрах3分鐘
Задача об одном ребре2分鐘
Задача о дереве4分鐘
Задача о простом цикле3分鐘
4 個閱讀材料
МФТИ10分鐘
Комментарий к лекции10分鐘
Дополнительные задачи10分鐘
Конспект лекции10分鐘
2 個練習
Задачи к семинару 112分鐘
Итоговые задания по неделе 120分鐘
完成時間為 3 小時
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
完成時間為 3 小時
16 個視頻 （總計 132 分鐘）, 3 個閱讀材料, 2 個測驗
16 個視頻
Напоминание теоремы о пороговой вероятности для свойства связности2分鐘
Применение неравенства Чебышева9分鐘
Оценивание математического ожидания10分鐘
Оценивание дисперсии10分鐘
Вероятность существования изолированной вершины5分鐘
Разложение случайного графа на компоненты связности2分鐘
Оценивание математического ожидания числа компонент связности15分鐘
Представление оценки в виде суммы двух слагаемых5分鐘
Предел первого слагаемого10分鐘
Предел второго слагаемого9分鐘
Задача о количестве изолированных вершин в случайном двудольном графе8分鐘
Задача о существовании изолированной вершины в случайном двудольном графе17分鐘
Задача об одной изолированной вершине4分鐘
Задача о количестве вершин степени 14分鐘
Задача о связности случайного графа при большой вероятности проведения ребра8分鐘
3 個閱讀材料
Комментарий к задаче о существовании изолированной вершины в случайном двудольном графе10分鐘
Дополнительные задачи10分鐘
Конспект лекции10分鐘
2 個練習
Задачи к семинару 210分鐘
Итоговые задания по неделе 218分鐘
完成時間為 3 小時
Вероятностный метод
Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом.
完成時間為 3 小時
15 個視頻 （總計 102 分鐘）, 3 個閱讀材料, 2 個測驗
15 個視頻
Обхват графа2分鐘
Теорема о графе с большим обхватом и большим хроматическим числом: формулировка теоремы и идея доказательства5分鐘
Введение случайности5分鐘
Оценка математического ожидания числа циклов15分鐘
Применение неравенства Маркова для оценивания обхвата3分鐘
Оценка математического ожидания числа независимых множеств7分鐘
Применение неравенства Маркова для оценивания числа независимости6分鐘
Существование графа с большим хроматическим числом и малым количеством циклов1分鐘
Модификация графа6分鐘
Задача о количестве 4-циклов в случайном двудольном графе15分鐘
Задача об отсутствии циклов в равномерной модели1分鐘
Задача о хроматическом числе случайного графа в равномерной модели4分鐘
Задача об оценке числа независимости7分鐘
Задача о хроматическом числе случайного графа с 5 ребрами7分鐘
3 個閱讀材料
Замечание: существование длинных циклов10分鐘
Дополнительные задачи10分鐘
Конспект лекции10分鐘
2 個練習
Задачи к семинару 310分鐘
Итоговые задания по неделе 318分鐘
完成時間為 3 小時
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
完成時間為 3 小時
14 個視頻 （總計 113 分鐘）, 3 個閱讀材料, 2 個測驗
14 個視頻
Доказательство теоремы11分鐘
Хроматическое число случайного графа без ребер5分鐘
Хроматическое число сильно разреженного случайного графа4分鐘
Доказательство того, что в случайном разреженном графе отсутствуют циклы6分鐘
Хроматическое число случайного графа G(n,c/n)10分鐘
Хроматическое число слабо разреженного графа9分鐘
Точная асимптотика хроматического числа G(n,0.5)5分鐘
Идея доказательства теоремы Боллобаша7分鐘
Алгоритм покраски10分鐘
Задача о хроматическом числе и обхвате случайного двудольного графа10分鐘
Задача о хроматическом числа графа G(6,5)5分鐘
Задача о древесных компонентах случайного графа14分鐘
Задача об оценке хроматического числа случайного графа специального вида3分鐘
3 個閱讀材料
Комментарий к лекции: тройка вместо двойки10分鐘
Дополнительные задачи10分鐘
Конспект лекции10分鐘
2 個練習
Задачи к семинару 48分鐘
Итоговые задания по неделе 414分鐘
常見問題
我什么时候能够访问课程视频和作业？
讲座和作业的访问权限取决于您的注册类型。如果您以旁听模式参加课程，则可以免费查看大多数课程资料。要访问评分作业并获得证书，您需要在旁听期间或之后购买证书体验。如果看不到旁听选项：
- 课程可能不提供旁听选项。您可以尝试免费试用，也可以申请助学金。
- 课程可能会改为提供'完整课程，没有证书'。通过此选项，您可以查看所有课程材料、提交所要求的作业，以及获得最终成绩。这也意味着您将无法购买证书体验。
我购买证书后会得到什么？
您购买证书后，将有权访问所有课程材料，包括评分作业。完成课程后，您的电子课程证书将添加到您的成就页中，您可以通过该页打印您的课程证书或将其添加到您的领英档案中。如果您只想阅读和查看课程内容，可以免费旁听课程。
退款政策是如何规定的？
您可在付款后两周内，或者在课程第一个班次开课后（对于已启动的课程）两周内，获得全额退款，以其中较晚者为准。获得课程证书后，您便无法再退款；即使您在两周的退款期内完成了课程，也是如此。请阅读我们完整的退款政策。
有助学金吗？
是的，Coursera 可以向无法承担学费的学生提供助学金。点击左侧‘注册’按钮下的‘助学金’链接即可申请助学金。您可以根据屏幕提示完成申请，申请获批后会收到通知。了解详情。
還有其他問題嗎？請訪問 學生幫助中心。
