Аспирантский семинар: Параллельное моделирование дискретных событий, алгоритмы кластеризации в моделях случайных графов, оптимальная остановка случайных последовательностей

Место: Факультет компьютерных наук, Кочновский проезд, д. 3, ауд. 205
Время: 22 сентября, 18:10 – 19:30 

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

Первый доклад

Тема:  Анализ глобального времени в алгоритмах параллельного моделирования дискретных событий
Докладчик:  Лилия Зиганурова, аспирантка второго года обучения, базовая кафедра «Прикладные информационно-коммуникационные средства и системы» ВЦ РАН (МИЭМ)

Основной объект исследования — это алгоритмы синхронизации при параллельном дискретно-событийном моделировании. Различают два типа алгоритмов: консервативные и оптимистические. В основе этих алгоритмов лежит концепция виртуального времени, поэтому многие свойства алгоритмов могут быть изучены на простых моделях эволюции профиля локальных виртуальных времен (ЛВВ) параллельных процессов. Мы строим такие модели для разных алгоритмов на разных коммуникационных сетях и смотрим на такие показатели как скорость роста профиля времен и ширина профиля. Эти показатели могут быть интерпретированы как эффективность и степень синхронизации в различных алгоритмах соответственно. Также проводится аналогия между ростом профиля ЛВВ и другими физическими моделями роста, что позволяет применять инструменты статистической физики при изучении алгоритмов и делать выводы об их эффективности.
 

Второй доклад

Тема:  Алгоритмы кластеризации в моделях случайных графов
Докладчик:  Максим Казаков, аспирант второго года обучения, кафедра прикладной математики и информатики факультета информатики, математики и компьютерных наук (Нижний Новгород)

Задача выявления сообществ в сети представляет серьезный практический интерес, особенно для сетей большого размера. Для решения задачи предложено большое количество различных алгоритмов кластеризации на графах и их модификаций. Однако теоретический анализ данных алгоритмов и их свойств (в том числе асимптотических) представлен в литературе довольно слабо. Интересным направлением в данной теме является анализ алгоритмов кластеризации в моделях случайных графов с предопределенной (“посеянной”) кластерной структурой. В докладе будут представлены результаты работ по данной теме. 
 

Третий доклад

Тема: Верхняя и нижняя границы урезанной цены в задаче об оптимальной остановке (дискретное время, конечный горизонт)
Докладчик:  Евгений Ясонов, аспирант четвертого года обучения, кафедра компьютерной безопасности (МИЭМ)

Задача об оптимальной остановке случайных последовательностей возникает в задачах статистики (задача последовательного различения двух простых гипотез), техники (задача о разладке), финансовой математики (расчет американского опциона) и ряде других.

В классической постановке этой задачи предполагается, что распределение вероятностей наблюдаемой последовательности известно. Как правило, наблюдателю неизвестен явный вид этого вероятностного распределения (например, в задаче расчёта опционов на неполном рынке). Поэтому многими авторами рассматривается минимаксная (максиминная) постановка задачи об оптимальной остановке. Впервые она была рассмотрена Ф. Риделем в статье "Optimal Stopping with Multiple Priors" для случаев конечного и бесконечного горизонтов. В ней доказано, что нижняя цена оптимальной остановки удовлетворяет рекуррентному соотношению беллмановского типа, а также установлены оптимальные правила остановки и двойственность для решения этой задачи.

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