наверх

Дополнительные главы теории случайных графов

4 сентября - 31 декабря 2019 г.
Курс уже начался
46 дней
До конца записи
  • 12 недель

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

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

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

Курс посвящен двум основным моделям случайного графа – равномерной и биномиальной. Курс разделен на три части. В первой мы изучим взаимосвязь упомянутых моделей. Во второй поговорим о свойствах биномиального случайного графа, выразимых на языке первого порядка и, наконец, в третьей части опишем изменение основных свойств случайного графа при увеличении вероятности проведения ребра.

О курсе

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


 

Требования

В результате обучения студент должен:
знать:
- определения двух моделей случайного графа и их взаимосвязи;
- асимптотическое поведение вероятностей свойств случайного графа, выразимых на языке первого порядка;
- динамику свойств случайного графа при росте p;
уметь:
- применять изученные методы для решения задач, связанных с различными моделями случайных графов;
- доказывать все изученные в курсе теоремы.
 

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

1.    Монотонные свойства
Две модели случайных множеств и случайных графов. Случайные процессы на графах. Монотонные свойства и пороговые вероятности. Асимптотческая эквивалентность двух моделей. Пороговая вероятность для свойства содержать фиксированный подграф.
2.    Логические законы
Логика первого порядка. Законы нуля или единицы. Игра Эренфойхта. Свойства расширений. Законы нуля или единицы для плотного графа. Законы нуля или единицы для сильно разреженного графа. Законы нуля или единицы для разреженного графа.
3.    Эволюция случайного графа
p=o(1/n): ацикличность случайного графа и размер копмпонент; p=c/n: возникновения гигантской компоненты; пороговая вероятность связности
 

Результаты обучения

В результате обучения студент должен:
знать:
- определения двух моделей случайного графа и их взаимосвязи;
- асимптотическое поведение вероятностей свойств случайного графа, выразимых на языке первого порядка;
- динамику свойств случайного графа при росте p;
уметь:
- применять изученные методы для решения задач, связанных с различными моделями случайных графов;
- доказывать все изученные в курсе теоремы.
 

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


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

сертификат об окончании курса

Сертификат

По данному курсу возможно получение сертификата.

Стоимость прохождения процедур оценки результатов обучения с идентификацией личности - 1800 Р.

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