Рандомизация для задач анализа информации и управления в реальном времени

профессор О. Н. Граничин

Весна 2011, 4 курс, кафедра Системного программирования

1. Введение. Трудности задач анализа информации и управления в реальном времени

1.1. Процесс получения данных и управления

1.2. Неопределенности

1.3. Байесовский подход

1.4. Недостаточность разнообразия исходных данных. Изменчивость данных со временем

1.5. Ограничениями по ресурсам в условиях реального времени

1.6. Пример обработки заданий сервером

1.7. Пример балансировки нагрузки в вычислительной сети

2. Рандомизированные алгоритмы

2.1. «Провалы» детерминированных подходов

2.2. Понятие рандомизированного алгоритма

2.3. Парадигма рандомизированного подхода

2.4. Пример вычисления по Методу Монте-Карло площади «подграфика»

2.5. Пример состоятельности рандомизированного алгоритма в задаче обнаружения сигнала на фоне почти произвольных помех

3. Сценарный подход

4. Понятие функционала среднего риска. Метод эмпирического функционала

5. Приближение одной случайной величины с помощью семейства других

6. Байесовское оценивание

7. Метод максимального правдоподобия. Достижимая точность оценивания

8. Метод стохастической аппроксимации

8.1. Алгоритм Роббинса-Монро

8.2. Процедура Кифера-Вольфовица

9. Рандомизированные алгоритмы стохастической аппроксимации (SPSA)

9.1. Алгоритмы с двумя измерениями

9.2. Алгоритм с одним измерением

9.3. Состоятельность при почти произвольных помехах

9.4. Оптимальная минимаксная скорость сходимости

9.5. Алгоритмы с постоянным размером шага

9.6. Пример оптимизации работы сервера

10. Линейные задачи. Оценки МНК. Теорема Гаусса-Маркова

11. Рекуррентные модификации МНК

12. Фильтр Винера-Колмогорова

13. Фильтр Калмана-Бьюси

14. Compressive Sensing

15. Алгоритмы обучения и самообучения. Кластеризация

16. Заключение. Перспективы стохастического программирования

Литература:

1. Граничин О.Н. Стохастическая оптимизация и системное программирование // Стохастическая оптимизация в информатике, т.6, вып. 1, с. 3-44 (Лекции 1-3)

2. Граничин О.Н., Поляк Б.Т. «Рандомизированные алгоритмы оптимизации и оценивания при почти произвольных помехах», М.:Наука, 2003. 291 с. (Лекции 2, 4-13, 15)

3. Граничин О.Н. Введение в методы стохастической оптимизации и оценивания. Учебное пособие. СПб.: Изд-во С.-Петерб. университета, 2003, 131с. (Лекции 2, 4-13, 15)

4. Граничин О.Н., Павленко Д.В. Pандомизация получения данных и l_1-оптимизация // Автоматика и телемеханика, 2010, № 11, с. 3 -28 (Лекция 1)

5. Граничин О.Н., Шалымов Д.С., Аврос Р., Волкович З. Pандомизированный алгоритм нахождения количества кластеров // Автоматика и телемеханика, 2011 (Лекции 2, 15)

Дополнительная:

6. Кушнер Дж, Ин Г. «Stochastic Approximation and Recursive Algorithms and Applications »
7. Спал Д. «Стохастическая оптимизация»
8. Borkar V. “Stochastic Approximation”

9. Campi M. “Selected Topics In Probability”