Магистратура
2020/2021
Современные методы принятия решений: статистические методы и анализ сложных сетей
Лучший по критерию «Полезность курса для расширения кругозора и разностороннего развития»
Статус:
Курс обязательный (Математические методы моделирования и компьютерные технологии)
Направление:
01.04.02. Прикладная математика и информатика
Кто читает:
Департамент прикладной математики
Когда читается:
1-й курс, 1-4 модуль
Формат изучения:
с онлайн-курсом
Прогр. обучения:
Математические методы моделирования и компьютерные технологии
Язык:
русский
Кредиты:
10
Контактные часы:
144
Программа дисциплины
Аннотация
В последние десятилетия статистические методы, развитые изначально в механике, нашли широкое применение в целом ряде областей науки, как смежных с физикой (биофизика, химическая физика, астрофизика и космология), так и на, первый взгляд, далеких от нее (теория вероятностей, компьютерные науки, количественная география, науки об обществе). Идеи статистического описания, связывающего крупномасштабное коллективное поведение систем с простыми микроскопическими свойствами их элементов, оказывается чрезвычайно плодотворной, в частности, для понимания ряда задач компьютерных наук, таких как теория алгоритмов, задачи перечисления объектов, вычислительные задачи на решетках и больших случайных графах. Курс сочетает обсуждение базовых принципов и понятий статистической теории, таких как равновесие, энтропия, температура, фазовые переходы, самоподобие, параметры порядка, лежащих на стыке теоретической механики и теории вероятностей, с разбором широкого круга конкретных прикладных задач, иллюстрирующих применение этих базовых принципов. В курсе рассматриваются: • теория случайных блужданий как простейший пример возникновения коллективного поведения и самоподобия в статистических системах; • основы равновесной статистики: понятие о равновесии, температуре, распределении Гиббса, статистической сумме; • понятие энтропии, его механический и теоретико-вероятностный смысл, принцип роста энтропии; • фазовые переходы, теория перколяции, понятие о геометрических фазовых переходах, параметры порядка, масштабирование (скейлинг), критические индексы; • системы случайных логических уравнений, переход совместность-несовместность, особенности поведения вблизи точки перехода; • неравновесные марковские процессы, кинетическое уравнение, применение к задачам трафика (однополосного дорожного движения), понятие о фазовых переходах в неравновесных системах; • случайные сети, формирование гигантского кластера в случайных сетях, тесные миры, динамические модели сетей (преимущественное присоединение), динамические процессы на сетях (распространение сигналов, эпидемий); Курс в большой степени основан на недавнем учебнике: Дж. Сетна "Статистическая механика: энтропия, параметры порядка, теория сложности" (Корнельский университет, США), на курсе С.Реднера в Бостонском университете и курсе "Statistical Mechanics: Algorithms and Computations", читаемом в Эколь Нормаль в Париже.
Цель освоения дисциплины
- знакомство с основнымиметодамистатистической механикии теории сложных сетей, а такжеи их приложений к проблемам физики конденсированного состояния, биофизики, вычислительной математики, социальных наук
- практическиенавыкирешения задач статистической механики, анализа сложных сетей и компьютерного моделирования
Планируемые результаты обучения
- знать основные принципы и методы статистической механики
- знать основные понятия теории сложных сетей
- применять полученные знания для решения учебных задач и интерпретировать результаты на языке статистической механики
- владеть навыками применения методов анализа и моделирования сложных сетей.
Содержание учебной дисциплины
- Статистический подход к прогнозированию и принятию решений.Предмет и метод статистической физики. Возникновение простого коллективного поведения в системах с большим числом частиц.Динамический и статистический подходы. Задача прогнозирования погоды. Эффекты конечного размера в малых системах. Бросание монетки. Задача перколяции. Случайные графы, модель Эрдоша-Реньи. Модели Изинга и Шеллинга. Биномиальное распределение. Сходимость к нормальному распределению. Центральная предельная теорема. Флуктуации. Случайные блуждания, броуновское движение, диффузия, уравнение диффузии.Универсальность, скейлинговое поведение, анализ размерностей.Распределение Пуассона. Понятие о микроканоническом ансамбле.
- Эргодичность и динамический хаос.Устойчивость решения дифференциальных уравнений. Критерии устойчивости. Экспоненты Ляпунова. Примеры устойчивых и неустойчивых отображений. Динамический хаос. Аттракторы. Удвоение периода. Понятие об эргодичности.Гамильтонова формулировка механики. Теорема Лиувилля.
- Температура, энтропия и статитистические ансамбли.Микроканонический ансамбль и законы сохранения. Энтропия. Возрастание энтропии в микроканоническом ансамбле. Понятие о мягких и жестких ограничениях. Канонический ансамбль.Температура.Тепловое равновесие. Распределение Гиббса. Статистическая сумма. Термодинамические потенциалы и их использование для
- Статистическая физика конденсированного состоянияФизика реальных газов и жидкостей. Конфигурационный интеграл. Высокотемпературная (майеровская) диаграммная техника. Парные корреляционные функции. Уравнение Орнштейна-Цернике. Задача классификации конденсированных фаз. Спонтанное нарушение симметрии. Параметры порядка. Пространство параметра порядка. Топологическая классификация дефектов. Возмущения в конденсированных средах. Голдстоуновские моды. Примеры: магнетики, кристаллы, жидкие кристаллы, сверхтекучесть
- Фазовые переходыПонятие о фазовых переходах. Скачкообразные и непрерывные фазовые переходы (переходы первого и второго рода).Фазовые переходы в задачеперколяции, в сетях Эрдоша-Реньи, в модели Изинга. Кипение, кристаллизация, ферромагнитный переход.Метастабильные состояния в скачкообразных переходах, спинодаль и бинодаль. Зародышеобразование. Динамика фазового расслоения. Непрерывные фазовые переходы.Универсальность. Аномальные флуктуации. Масштабная инвариантность. Скейлинг. Среднеполевая теория Ландау. Критерий Гинзбурга. Понятие о ренорм-группе, физические причины универсальности. Скейлинговые функции, коллапс, конечномерное масштабирование. Самоорганизующаяся критичность (self-organized criticality)
- Основные понятия, определения и методы анализа сложных сетейВведение в теорию сложных сетей. Определения и примеры сложных сетей. Основные понятия в теории сетей. Свойства и метрики анализа сетей. Топологические свойства сетей. Распределение степеней связности, коэффициент кластеризации, ассортативность, диаметр, кратчайшие пути. Представление сети в компьютерном эксперименте. Понятие к-ядра графа, диады и триады в графах, мотивы.
- Случайные сети и компьютерное моделирование сложных систем.Модель Эрдеша-Реньи (Erdos-Renyi). Распределение Бернулли и Пуассона. Функция распределения степеней. Фазовые переходы, возникновение связанной компоненты. Диаметр и коэффициент кластеризации. Конфигурационная модель. Модель Барабаши-Альберта (Barabasi-Albert). Предпочтительное присоединение. Уравнение в непрерывном приближении. Временная эволюция степеней узлов. Распределение степеней узлов. Средняя длина пути и коэффициент кластеризации. Модели "малого мира". Модель Watts-Strogats. Однопараметрическая модель. Переход от регулярного графа к случайному. Изменения коэффициента кластеризации и средней длины пути.Модели экспоненциальных случайных графов и их физический смысл. Методы Монте-Карло моделирования экспоненциальных-случайных графов. Фазовые переходы и нарушение симметрии.
- Спектральные свойства сложных сетей.Матрица смежности. Матрица Лапласа. Процесс физической диффузии. Уравнение диффузии. Диффузия на сетях. Дискретный оператор Лапласа и матрица Лапласа, решение уравнения диффузии на графе. Случайные блуждания на графе. Спектр сети. Максимальное собственное значение матрицы смежности. Алгебраическая связность. Полукруговой закон.
- Поиск сообществ в сетиПонятие сообщества в сети. Плотность связей. Метрики. Разделение графа на части. Разрезы в графе. Задача нахождения минимально разреза в графе.Агломеративные и разделяющие алгоритмы. Корреляционная матрица. Кластеризация. Понятие промежуточности ребер. АлгоритмыГирвина-Ньюмана. Спектральные методы. Оптимизация модулярности. Классификация алгоритмов нахождения сообществ.
- Модели распространения эпидемий в сетях.Модели распространения эпидемии в сети. Модель SI, SISв приближении среднего поля. Degree block approximation.
Элементы контроля
- Контрольная работа 2
- Экзамен 1
- Экзамен 2
- Работа студента на практических занятиях, выполнение домашних заданий
- Контрольная работа 1
- Экзамен 1
- Экзамен 2
- Работа студента на практических занятиях, выполнение домашних заданий
- Оценка за онлайн-курс
