up
  • Russian

    course language

  • 13 weeks

    course duration

  • 3 credit points

    for credit at your university

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

About

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

Для бесплатного просмотра доступны только видеолекции и тренировочные задания. Тесты на проверку откроются после оплаты сертификации. Стоимость сертификации составляет 2800 рублей.

Экзамус.

Уважаемые слушатели, Вы можете сдать экзамен с прокторингом, который будет проходить на курсе раз в 2-3 месяца. Рассылка о предстоящих экзаменах будет приходить Вам на почту заранее.

Ближайшие даты экзамена с 22 по 31 мая 2023 года.

 


 

Course program

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

Education results

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

Education directions

Similar courses