course language
course duration
for credit at your university
Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети. Прослушав этот курс, вы проникнетесь чрезвычайно красивой математической теорией и научитесь решать комбинаторные и алгоритмические задачи на случайных графах. Все эти знания позволят нам затем перейти к курсу веб-графов, в котором мы расскажем о самых современных приложениях вероятностно-графовых моделей и конструкций. Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети.
Для бесплатного просмотра доступны только часть материалов курса. Полный доступ откроется только после оплаты сертификации. Стоимость сертификации составляет 3600 рублей.
Курс состоит из 11 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.
https://www.mccme.ru/free-books/dubna/raigor-4.pdf
https://ium.mccme.ru/postscript/s12/gasnikov-raigorodskii.pdf
Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.
1 неделя. Две модели случайного графа
2 неделя. Теорема о пороговой вероятности для свойства связности
3 неделя. Вероятностный метод
4 неделя. Хроматическое число случайного графа
5 неделя. Алгоритмы на случайном графе
6 неделя. Малые подграфы в случайном графе
7 неделя. Пуассоновская предельная теорема для числа копий фиксированного графа
8 неделя. Мартингалы
9 неделя. Теорема о концентрации хроматического числа в четырех точках
10 неделя. Теорема о концентрации хроматического числа при постоянном p
11 неделя. Концентрация числа независимости
Итоговый тест
Знать:
‒ основные понятия и определения теории случайных графов
Уметь:
‒ применять различные методы теории случайных графов для решения задач
‒ анализировать свойства случайных графов и применять их в различных областях науки и техники
‒ работать с продвинутыми алгоритмами теории случайных графов
‒ проводить самостоятельные исследования в области теории случайных графов и представлять их результаты.
course language
course duration
for credit at your university
Доктор физико-математических наук
Position: Директор Физтех-школы прикладной математики и информатики, главный научный сотрудник - заведующий лабораторией продвинутой комбинаторики и сетевых приложений, заведующий лабораторией прикладных исследований МФТИ - Сбербанк, заведующий кафедрой дискретной математики ФИВТ, руководитель совместных исследовательских программ Яндекса и МФТИ, главный редактор журнала Moscow Journal of Combinatorics and Number Theory
Position: Преподаватель