Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен?
Случайные графы
提供方
Случайные графы
莫斯科物理科学与技术学院
課程信息
3,110 次近期查看
100% 在線
立即開始，按照自己的計劃學習。
可靈活調整截止日期
根據您的日程表重置截止日期。
完成時間大約為24 小時
建議：6 недель исследования, 1-2 часов / неделю
俄語（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分鐘
關於 莫斯科物理科学与技术学院
Московский физико-технический институт (Физтех) является одним из ведущих вузов страны и входит в основные рейтинги лучших университетов мира. Институт обладает не только богатой историей – основателями и профессорами института были Нобелевские лауреаты Пётр Капица, Лев Ландау и Николай Семенов – но и большой научно-исследовательской базой.
Основой образования в МФТИ является уникальная «система Физтеха», сформулированная Петром Капицей: кропотливый отбор одаренных и склонных к творческой работе абитуриентов; участие в обучении ведущих научных работников; индивидуальный подход к отдельным студентам с целью развития их творческих задатков; воспитание с первых шагов в атмосфере технических исследований и конструктивного творчества с использованием потенциала лучших лабораторий страны.
Среди выпускников МФТИ — нобелевские лауреаты Андрей Гейм и Константин Новоселов, основатель компании ABBYY Давид Ян, один из авторов архитектурных принципов построения вычислительных комплексов Борис Бабаян и др.
常見問題
我什么时候能够访问课程视频和作业？
注册以便获得证书后，您将有权访问所有视频、测验和编程作业（如果适用）。只有在您的班次开课之后，才可以提交和审阅同学互评作业。如果您选择在不购买的情况下浏览课程，可能无法访问某些作业。
我购买证书后会得到什么？
您购买证书后，将有权访问所有课程材料，包括评分作业。完成课程后，您的电子课程证书将添加到您的成就页中，您可以通过该页打印您的课程证书或将其添加到您的领英档案中。如果您只想阅读和查看课程内容，可以免费旁听课程。
退款政策是如何规定的？
有助学金吗？
還有其他問題嗎？請訪問 學生幫助中心。
