Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен?
Случайные графы
莫斯科物理科学与技术学院課程信息
4,662 次近期查看
可分享的證書
完成後獲得證書
100% 在線
立即開始，按照自己的計劃學習。
可靈活調整截止日期
根據您的日程表重置截止日期。
完成時間大約為21 小時
俄語（Russian）
字幕：俄語（Russian）
可分享的證書
完成後獲得證書
100% 在線
立即開始，按照自己的計劃學習。
可靈活調整截止日期
根據您的日程表重置截止日期。
完成時間大約為21 小時
俄語（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 個練習
Задачи к семинару 130分鐘
Итоговые задания по неделе 130分鐘
完成時間為 4 小時
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
完成時間為 4 小時
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 個練習
Задачи к семинару 230分鐘
Итоговые задания по неделе 230分鐘
完成時間為 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 個練習
Задачи к семинару 330分鐘
Итоговые задания по неделе 330分鐘
完成時間為 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 個練習
Задачи к семинару 430分鐘
Итоговые задания по неделе 430分鐘
常見問題
我什么时候能够访问课程视频和作业？
我购买证书后会得到什么？
Is financial aid available?
完成课程后，我会获得大学学分吗？
還有其他問題嗎？請訪問 學生幫助中心。
