Случайные графы

Теория случайных графов находится на стыке теории графов и теории вероятностей. Наука появилась в середине ХХ века, и она сразу же привлекла огромное внимание как со стороны чистых математиков, так и со стороны прикладников. В курсе мы изучим как основы теории случайных графов, так и настоящие ее жемчужины. Мы научимся воспринимать многие сложные системы как "случайные графы". Среди них – интернет, социальные сети (Фейсбука, Вконтакте), биологические, межбанковские сети.

Для бесплатного просмотра доступны только часть материалов курса. Полный доступ откроется только после оплаты сертификации. Стоимость сертификации составляет 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 неделя.  Концентрация числа независимости
Итоговый тест

Знать: 
‒ основные понятия и определения теории случайных графов
Уметь:
‒ применять различные методы теории случайных графов для решения задач
‒ анализировать свойства случайных графов и применять их в различных областях науки и техники
‒ работать с продвинутыми алгоритмами теории случайных графов
‒ проводить самостоятельные исследования в области теории случайных графов и представлять их результаты.