наверх

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

 width=
Запись на курс закрыта
Подпишитесь на новости и узнайте дату следующего запуска
  • 8 недель

    длительность курса

  • 2 зачётных единицы

    для зачета в своем вузе

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

О курсе

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

Формат

Курс состоит из 7 учебных недель и экзамена. Для успешного решения большинства задач из тестов достаточно освоить материал, рассказанный на лекциях. На семинарах разбираются и более сложные задачи, которые смогут заинтересовать слушателя, уже знакомого с основами теории графов.

Требования

Для освоения материала будет достаточно математики школьного уровня, базовых знаний комбинаторики и теории вероятностей.

Программа курса

1 неделя. Две модели случайного графа
2 неделя. Теорема о пороговой вероятности для свойства связности
3 неделя. Вероятностный метод
4 неделя. Хроматическое число случайного графа
5 неделя. Алгоритмы на случайном графе
6 неделя. Малые подграфы в случайном графе
7 неделя. Итоги
8 неделя. Итоговый тест

Жуковский Максим Евгеньевич


Должность: Преподаватель

Райгородский Андрей Михайлович

Доктор физико-математических наук
Должность: Заведующий кафедрой Дискретной математики ФИВТ, научный руководитель бакалавриата кафедры «Анализ данных», руководитель отдела теоретических и прикладных исследований Яндекса, главный редактор журнала Moscow Journal of Combinatorics and Number Theory

Похожие курсы