About this course: Издавна среди жителей Кёнигсберга была распространена такая загадка: как пройти по всем мостам через реку Преголя, не проходя ни по одному из них дважды. Многие кёнигсбержцы пытались решить эту задачу как теоретически, так и практически во время прогулок. Доказать или опровергнуть возможность существования такого маршрута никто не мог до 1736 года, когда выдающийся математик Леонард Эйлер не написал письмо своему другу с решением. Ответ был «нельзя». Так и родилась теория графов. Но что будет, если процесс, который описывает граф – случаен? Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Who is this class for: Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Created by: Moscow Institute of Physics and Technology
Taught by: Андрей Райгородский, профессор, доктор физико-математических наук
кафедра дискретной математики МФТИ
Taught by: Максим Жуковский, преподаватель
кафедра дискретной математики МФТИ
| Commitment | 6 недель исследования, 1-2 часов / неделю |
| Language | Russian |
| How To Pass | Pass all graded assignments to complete the course. |
| User Ratings |
Syllabus
WEEK 1
Две модели случайного графа
Случайный граф Эрдеша-Реньи: биномиальная модель и равномерная модель. Свойства случайного графа. Свойство связности. Пороговая вероятность для свойства связности. Пороговая вероятность для свойства связности. Возникновение гигантской компоненты в случайном графе.
15 videos, 4 readings, 1 practice quiz
- Video: История зарождения понятия случайного графа
- Video: Биномиальная модель случайного графа
- Video: Связность случайного графа на четырех вершинах
- Reading: Комментарий к лекции
- Video: Эволюция случайного графа
- Video: Равномерная модель случайного графа
- Reading: МФТИ
- Video: МФТИ
- Video: Пороговая вероятность для свойства связности: формулировка теоремы
- Video: Нижняя оценка вероятности связности: формулировка теоремы
- Video: Теорема о появлении гигантской компоненты в случайном графе
- Practice Quiz: Задачи к семинару 1
- Video: Задача о монотонности вероятности
- Video: Задача о промежуточных значениях вероятности
- Video: Задача о дополнительных ребрах
- Video: Задача об одном ребре
- Video: Задача о дереве
- Video: Задача о простом цикле
- Reading: Дополнительные задачи
- Reading: Конспект лекции
Graded: Итоговые задания по неделе 1
WEEK 2
Теорема о пороговой вероятности для свойства связности
Неравенство Маркова и Чебышева. Доказательство теоремы о пороговой вероятности для свойства связности случайного графа.
16 videos, 3 readings, 1 practice quiz
- Video: Вспомогательные утверждения из теории вероятностей
- Video: Напоминание теоремы о пороговой вероятности для свойства связности
- Video: Применение неравенства Чебышева
- Video: Оценивание математического ожидания
- Video: Оценивание дисперсии
- Video: Вероятность существования изолированной вершины
- Video: Разложение случайного графа на компоненты связности
- Video: Оценивание математического ожидания числа компонент связности
- Video: Представление оценки в виде суммы двух слагаемых
- Video: Предел первого слагаемого
- Video: Предел второго слагаемого
- Practice Quiz: Задачи к семинару 2
- Video: Задача о количестве изолированных вершин в случайном двудольном графе
- Video: Задача о существовании изолированной вершины в случайном двудольном графе
- Reading: Комментарий к задаче о существовании изолированной вершины в случайном двудольном графе
- Video: Задача об одной изолированной вершине
- Video: Задача о количестве вершин степени 1
- Video: Задача о связности случайного графа при большой вероятности проведения ребра
- Reading: Дополнительные задачи
- Reading: Конспект лекции
Graded: Итоговые задания по неделе 2
WEEK 3
Вероятностный метод
Хроматическое число, число независимости и кликовое число. Обхват графа. Теорема о существовании графа с большим обхватом и большим хроматическим числом.
15 videos, 3 readings, 1 practice quiz
- Video: Хроматическое число, число независимости и кликовое число
- Video: Обхват графа
- Video: Теорема о графе с большим обхватом и большим хроматическим числом: формулировка теоремы и идея доказательства
- Video: Введение случайности
- Video: Оценка математического ожидания числа циклов
- Video: Применение неравенства Маркова для оценивания обхвата
- Video: Оценка математического ожидания числа независимых множеств
- Video: Применение неравенства Маркова для оценивания числа независимости
- Video: Существование графа с большим хроматическим числом и малым количеством циклов
- Video: Модификация графа
- Reading: Замечание: существование длинных циклов
- Practice Quiz: Задачи к семинару 3
- Video: Задача о количестве 4-циклов в случайном двудольном графе
- Video: Задача об отсутствии циклов в равномерной модели
- Video: Задача о хроматическом числе случайного графа в равномерной модели
- Video: Задача об оценке числа независимости
- Video: Задача о хроматическом числе случайного графа с 5 ребрами
- Reading: Дополнительные задачи
- Reading: Конспект лекции
Graded: Итоговые задания по неделе 3
WEEK 4
Хроматическое число случайного графа
Оценки хроматического числа случайного графа G(n,p) при различных p=p(n).
14 videos, 3 readings, 1 practice quiz
- Video: Сравнение двух оценок хроматического числа
- Video: Доказательство теоремы
- Reading: Комментарий к лекции: тройка вместо двойки
- Video: Хроматическое число случайного графа без ребер
- Video: Хроматическое число сильно разреженного случайного графа
- Video: Доказательство того, что в случайном разреженном графе отсутствуют циклы
- Video: Хроматическое число случайного графа G(n,c/n)
- Video: Хроматическое число слабо разреженного графа
- Video: Точная асимптотика хроматического числа G(n,0.5)
- Video: Идея доказательства теоремы Боллобаша
- Video: Алгоритм покраски
- Practice Quiz: Задачи к семинару 4
- Video: Задача о хроматическом числе и обхвате случайного двудольного графа
- Video: Задача о хроматическом числа графа G(6,5)
- Video: Задача о древесных компонентах случайного графа
- Video: Задача об оценке хроматического числа случайного графа специального вида
- Reading: Дополнительные задачи
- Reading: Конспект лекции
Graded: Итоговые задания по неделе 4
WEEK 5
Алгоритмы на случайном графе
Жадный алгоритм раскраски. Жадное хроматическое число, жадное число независимости и жадное кликовое число. Теорема о жадном хроматическом числе и жадном числе независимости случайного графа.
11 videos, 3 readings, 1 practice quiz
- Video: Определение жадного алгоритма
- Video: Теорема о жадном хроматическом числе и жадном числе независимости случайного графа
- Video: Введение вспомогательного события
- Video: Разложение вспомогательного события в объединение событий
- Video: Оценка вероятности одного события
- Video: Завершение доказательства
- Video: Можно ли улучшить оценку?
- Practice Quiz: Задачи к семинару 5
- Video: Задача о жадном алгоритме покраски вершин дерева
- Video: Задача о жадном алгоритме покраски вершин случайного двудольного графа
- Video: Задача о жадном алгоритме покраски вершин пути
- Video: Задача о жадном алгоритме покраски вершин случайного графа с циклами
- Reading: Забытые графы в последней задаче
- Reading: Дополнительные задачи
- Reading: Конспект лекции
Graded: Итоговые задания по неделе 5
WEEK 6
Малые подграфы в случайном графе
Распределение малых подрафов в случайном графе: пороговые вероятности и Пуассоновская предельная теорема на пороге.
15 videos, 3 readings, 1 practice quiz
- Video: Постановка задачи
- Video: Сбалансированные и строго сбалансированные графы
- Video: Теорема о пороговой вероятности
- Video: Доказательство первого утверждения
- Video: Применение неравенства Чебышева
- Video: Представление дисперсии в виде суммы
- Video: Случай непересекающихся множеств
- Video: Два непересекающихся множества
- Video: Оценка суммы
- Video: Оценка каждого члена суммы
- Practice Quiz: Задачи к семинару 6
- Video: Задача о сбалансированных лесах
- Reading: Ошибка в перестановках деревьев
- Video: Задача о количестве автоморфизмов графа
- Video: Задача об одном подграфе на 4 вершинах и не менее 5 ребрах
- Video: Задача о треугольной компоненте
- Video: Задача о дисперсии количества полных графов на 5 вершинах
- Reading: Дополнительные задачи
- Reading: Конспект лекции
Graded: Итоговые задания по неделе 6
Итоговый тест
Заключительный экзамен, содержащий задачи по всем пройденным темам
1 reading
- Reading: Повторите пройденный материал перед прохождением итогового теста
Graded: Задания
FAQs
How It Works
Coursework
Each course is like an interactive textbook, featuring pre-recorded videos, quizzes and projects.
Help from Your Peers
Connect with thousands of other learners and debate ideas, discuss course material, and get help mastering concepts.
Certificates
Earn official recognition for your work, and share your success with friends, colleagues, and employers.
Creators
Moscow Institute of Physics and Technology
Московский физико-технический институт (неофициально известный как МФТИ или Физтех) является одним из самых престижных в мире учебных и научно-исследовательских институтов. Он готовит высококвалифицированных специалистов в области теоретической и прикладной физики, прикладной математики, информатики, биотехнологии и смежных дисциплин. Физтех был основан в 1951 году Нобелевской премии лауреатами Петром Капицей, Николаем Семеновым, Львом Ландау и Сергеем Христиановичем. Основой образования в МФТИ является уникальная «система Физтеха»: кропотливое воспитание и отбор самых талантливых абитуриентов, фундаментальное образование высшего класса и раннее вовлечение студентов в реальную научно-исследовательскую работу. Среди выпускников МФТИ есть Нобелевские лауреаты, основатели всемирно известных компаний, известные космонавты, изобретатели, инженеры.
Ratings and Reviews
Прошел курс исключительно из за лектора. Даже не знаю, пригодится ли мне на практике, но очень захватывающе изложено.
Хорошо составленный, интересный курс. Не слишком простой и не слишком сложный. Андрей Михайлович - один из лучших лекторов, которых я видел.
Райгородский рассказывает как боженька. Очень крутые лекции.
Coursera provides universal access to the world’s best education, partnering with top universities and organizations to offer courses online.
© 2017 Coursera Inc. All rights reserved.
BO
Курс хороший, но довольно трудный. Хотя в описании курса сказано:
"Курс построен так, что для его освоения будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей",
я не думаю, что это аккуратно описывает пререквизиты. Как минимум, нужно знание теории графов и довольно свободное владение
комбинаторикой и теорией вероятностей. Лекции идут в очень высоком темпе (для меня, по крайней мере), базовые вещи часто просто пропускаются.