Стохастические методы оптимизации в информатике

УДК 519.712 ВКК 32.811.7

С82

Ответственный редактор д. ф.-м. н., проф. О. Н. Граничин

Редакционная коллегия: Н. К. Кривулин (С.-Петерб. гос. ун-т),

Г. А. Леонов (С.-Петерб. гос. ун-т),

Б. Т. Поляк (ипу ран),

А. В. Соколов (ИПМИ КарНЦРАН),

А. П. Терехов (С.-Петерб. гос. ун-т),

М. К. Чирков (С.-Петерб. гос. ун-т),

П. С. Щербаков (ипу ран)

Печатается по постановлению

Редакционно-издателъского совета

математико-механического факультета

С.-Петербургского государственного университета

Стохастическая оптимизация в информатике. Том 8 (Вып. 2) / Под ред. О. Н. Граничина — СПб.: Издательство С.-Петербургского университета, 2012. — 160 с. ISSN 1992-2922

Издание выпускается ежегодно (том 1, ненумерованный, вышел в 2005 г., тома (вып.) 2-7 — в 2006—11 гг., том 8, вып. 1 — в 2012 г.) и содержит научные работы по стохастической оптимизации, особо выделяя приложения в информатике. Второй выпуск восьмого тома составлен из поступивших в редколлегию рукописей и материалов одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2012 г. на математико-механическом факультете С.-Петербургского университета под руководством профессора кафедры системного программирования О. Н. Граничина и организованных совместно с Лабораторией системного программирования и информационных технологий (СПРИНТ) СПбГУ, которая была создана при поддержке корпорации Intel.

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

ББК 32.811.7

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

Обратные связи, усреднение и рандомизация в управлении и извлечении знаний

О. Н. Граничин, д. ф.-м. н.

Санкт-Петербургский государственный университет

O1eg_granichin@mail.ru

Статья написана при подготовке к семинару "Рандомизация и усреднение в оценивании, оптимизации и управлении", предложенному автором совместно с А.Л. Фрадковым в рамках международной конференции IEEE MSC-2012. Цель семинара — объяснить ключевые результаты и приложения двух важных инструментов анализа и конструирования систем: рандомизации и усреднения. Оба эти инструмента позволяют упростить решения задач оценивания, оптимизации и адаптивного управления, в которых часто ресурсы ограничены, а данных недостаточно.

Ключевые слова: информация, сигналы, данные, знания, управления, обратные связи, усреднение, рандомизация.

Список литературы

[1] Фомин В.Н. Рекуррентное оценивание и адаптивная фильтрация. — М.: Наука. 1984. 288 с.

[2] Rzevski G. Modelling large complex systems using multi-agent technology // In Proc. of 13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing (SNPD 2012), 2012. P. 434-437.

[3] Винер Н. Кибернетика, или управление и связь в животном и машине. — М.: Наука. 1983. 344 с.

[4] Красовский А.А. Справочник по теории автоматического управления. — М.: Наука. 1987. 712 с.

[5] Фелъдбаум А.А. О проблемах дуального управления // В кн.: Методы оптимизации автоматических систем. — М.: Наука. 1972. С. 89-108.

[6] Владимирович А.Г., Граничин О.Н., Макаров А.А. Нестандартная машина Тьюринга // Стохастическая оптимизация в информатике. 2005. 1. С. 29-47.

[7] Амелина Н.О., Лада А.Н., Майоров И.В., Скобелев П.О., Царев А.В. Исследование моделей организации грузовых перевозок с применением мультиагентной системы для адаптивного планирования мобильных ресурсов в реальном времени // Проблемы управления. 2011. № 6. С. 31-37.

[8] Амелина Н.О., Фрадков А.Л. Приближенный консенсус в стохастической динамической сети с неполной информацией и задержками в измерениях // Автоматика и телемеханика. 2012. № 11. С. 6-29.

[9] Amelin К., Amelina N., Granichin О., Granichina О. Multi-agent stochastic systems with switched topology and noise // In: Proc. of 13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, (SNPD 2012), 2012. P. 438-443.

[10] Боголюбов Н.Н., Митропольский Ю.А. Асимптотические методы в теории нелинейных колебаний. — М.: Гостехиздат. 1955. 408 с.

[11] Gibbs J.W. Elementary Principles in Statistical Mechanics. — Woodbridge, Connecticut. 1902.

[12] Lebesgue H. Integrale, Longueur, Aire. — Universite de Paris. 1902.

[13] Ширяев АЛ. Вероятность. — M.: Наука. 1980. 574 с.

[14] Граничин О.Н., Поляк Б. Т. Рандомизированные алгоритмы оценивания и оптимизации при почти произвольных помехах. М.: Наука. 2003. 293 с.

[15] Fradkov A.L. Continuous-time averaged models of discrete-time stochastic systems: survey and open problems // Proc. of IEEE Conf. on Decision and Control. 2011. P. 2076-2081.

[16] Меерков СМ. Об упрощении описания медленных марковских блужданий I, II // Автоматика и телемеханика. 1972. № 3. С. 6-75. № 5. С. 63-67.

[17] Ljung L. Analysis of recursive stochastic algorithms // IEEE Trans. Automat. Control. 1977. No. 4. P. 551-575.

[18] Кульчицкий О.Ю. Алгоритмы типа стохастической аппроксимации в контуре адаптации дискретной стохастической линейной динамической системы // Автоматика и телемеханика. Ч. 1-1983. №. 9. С. 102-118. Ч. П-1984. №. 3. С. 104-113.

[19] Кульчицкий О.Ю. Метод исследования сходимости алгоритмов адаптивной фильтрации, использующий стохастические функции Ляпунова // Пробл. передачи информ. 1985. № 4(21). С. 49-63.

[20] Деревицкий Д.П., Фрадков А.Л. Две модели для анализа динамики алгоритмов адаптации // Автоматика и телемеханика. 1974. № 1. С. 67-75.

[21] Деревицкий Д.П., Фрадков А.Л. Исследование дискретных адаптивных систем управления динамическими объектами с помощью непрерывных моделей // Изв. АН СССР. ТК. 1975. № 5. С. 93-99.

[22] Бернштейн СИ. Принципы теории стохастических дифференциальных уравнений // Тр. физ. мат. ин-та им. В.А. Стеклова. 1934.№. 5. С. 95-124.

[23] Kushner H.J. Convergence of recursive adaptive and identification procedures via weak convergence theory // IEEE Trans. Automat. Control. 1977. No. 6. P. 921-930.

[24] Граничин О.Н. 48-я и 49-я международные конференции "Принятие решений и управление" (IEEE CDC/CCC 2009 и CDC 2010) // Автоматика и телемеханика. 2011. №12. С. 173-178.

[25] Граничин О.Н. 48-50-я международные конференции "Принятие решений и управление" (IEEE CDC/CCC 2009, CDC 2010 и CDC-ECC 2011) // Стохастическая оптимизация в информатике. 2012. 8(1). С. 142-151.

[26] Соколов Б.В., Юсупов P.M. Неокибернетика — возможности и перспективы развития // Докл. на общем пленарном заседании 5-й науч. конф. "Управление и информационные технологии" (УИТ-2008). 2008. С. 1-15.

[27] Андриевский Б.Р., Матвеев А.С, Фрадков А.Л. Управление и оценивание при информационных ограничениях: к единой теории управления, вычислений и связи // Автоматика и телемеханика. 2010. № 4. С. 34-99.

[28] Граничин О.Н., Фомин В.Н. Метод динамического программирования в задаче минимаксного управления // Вестник Ленинградского университета. Сер. 1. 1986. Вып.1. С. 26-30.

[29] Sokolov V.F. Adaptive suboptimal control of a linear-system with bounded disturbance // Systems & Control Letters. 6(2). 1985. P. 93-98.

[30] Sokolov V.F. Adaptive suboptimal control in the case of constrained noise // Automation and remote control. 46(9). 1985. P.1131-1139.

[31] Campi M.C. Why is resorting to fate wise? A critical look at randomized algorithms in systems and control // European Journal of Control. 2010. 5. P. 419-430.

[32] Амелин К.С, Граничин О.Н. Новые рандомизированные алгоритмы в управлении и обработке данных // Стохастическая оптимизация в информатике. 7. 2010. С. 3-68.

[33] Граничин О.Н. Неасимптотическое доверительное множество для параметров линейного объекта управления при почти произвольных помехах // Автоматика и телемеханика. 2012. № 1. С. 24-35.

[34] Hoeffding W. Probability inequalities for sums of bounded random variables // J. Am. Stat. Assoc. 1963. 58. P. 13-30.

[35] Граничин О.Н., Молодцов С.Л. Создание гибридных сверхбыстрых компьютеров // Стохастическая оптимизация в информатике. 2. 2006. С. 219-253.

[36] Deutsch D. Quantum theory, the Church-Turing principle and the universal quantum computer // Proc. of the Royal Society of London. Ser. A. 400. 1985. P. 97-117.

[37] Metropolis N., Ulam S. The Monte Carlo Method // J. Amer. Statistical Assoc. 44. No. 247. 1949. P. 335-341.

[38] Ермаков СМ. Метод Монте-Карло и смежные вопросы. Сер. "Теория вероятностей и математическая статистика". — М.: Изд-во Наука. 1971. 471 с.

[39] Граничин О.Н., Халидов В.И. Рандомизированный подход к обнаружению разрывов функции // Стохастическая оптимизация в информатике. 1. 2005. С. 73-80.

[40] Граничин О.Н., Шалимов Д.С, Аврос Р., Волкович 3. Рандомизированный алгоритм нахождения количества кластеров // Автоматика и телемеханика. 2011. №4. С. 86-98.

[41] Granichin О., Morozkov M., Volkovich Z. Necessary conditions for the confidence level of the randomized algorithm of finding the true number of clusters // Proc. of IEEE International Symposium on Intelligent Control. 2011. P. 1002-1007.

[42] Морозков М.А. Быстрый рандомизированный алгоритм нахождения точного количества кластеров в большом множестве данных // Стохастическая оптимизация в информатике. 7. 2011. С. 69-82.

[43] Morozkov M., Granichin О., Volkovich Z., Zhang X. Fast algorithm for finding true number of clusters. Applications to control systems // In Proc. of Chinese Control and Decision Conference (CCDC), 2012. P. 2013-2018.

[44] Avros R., Granichin O., Shalymov D., Volkovich Z., Weber G.-W. Randomized algorithm of finding the true number of clusters based on Chebychev polynomial approximation (Chapter 6) // Data Mining: Found, and Intell. Paradigms, D.E. Holmes, L.C. Jain (Eds.), Berlin Heidelberg: Springer-Verlag, ISRL 23. Vol. 1. 2012. P. 131-155.

[45] Растригин Л.А. Статистические методы поиска. М.: Наука. 1968. 376 с.

[46] Сушков Ю.А. Об одном способе организации случайного поиска // Исследование операций и статистическое моделирование. Изд-во Ленингр. гос. ун-та. 1972. 1. С. 180-185.

[47] Жиглявский А.А., Жилинскас А.Г. Методы поиска глобального экстремума. М.: Наука. 1991. 248 с.

[48] Metropolis N., Rosenbluth A.W., Rosenbluth M.N., Teller A.H., Teller E. Equation of state calculations by fast computer machines // J. Chemical Physics. 21. 6. June 1953. P. 1087-1092.

[49] Kirkpatrick S., Gelatt Jr.CD., Vecchi M.P. Optimization by simulated annealing // Science. 220. 1983. P. 671-680.

[50] Лопатин А.С. Метод отжига // Стохастическая оптимизация в информатике. 2005. 1. С. 133-149.

[51] Тихомиров А.С. О быстрых вариантах алгоритма отжига (simulated annealing) // Стохастическая оптимизация в информатике. 2009. 5. С. 65-90.

[52] Holland J.H. Adaptation in Natural and Artificial Systems. University of Michigan Press. Ann Arbor. 1975. 183 p.

[53] Fisher R.A. The Design of Experiments. Edinburgh: Oliver and Boyd. 1935.

[54] Алберт А. Регрессия, псевдоинверсия и рекуррентное оценивание. М.: Наука. 1977. 223 с.

[55] Лъюнг Л., Сёдерстрём Т. Идентификация систем: теория для пользователя. — М.: Наука. 1991. 431 с.

[56] Цыпкин Я.З. Информационная теория идентификации. М.: Наука. 1995. 336 с.

[57] Young P.С. Recursive Estimation and Time-Series Analysis. An Introduction. — Berlin-Heidelberg: Springer. 1984. 300 p.

[58] Граничин О.Н. Алгоритм стохастической аппроксимации с возмущением на входе для идентификации статического нестационарного дискретного объекта // Вестник Ленинградского университета. Сер. 1. Вып. 3. 1988. С. 92-93.

[59] Goldenshluger A.V., Polyak В. Т. Estimation of regression parameters with arbitrary noise // Mathematical Methods of Statistics. 1993. 2(1). P. 18-29.

[60] Амелин К.С, Граничин О.Н. Возможности рандомизации в алгоритмах предсказания калмановского типа при произвольных внешних помехах в наблюдении // Гироскопия и навигация. № 2(73). 2011. С. 38-50.

[61] Амелин К. С. Возможности рандомизации в алгоритме предсказания отклонения от курса легкого беспилотного летательного аппарата при произвольных внешних помехах в наблюдении // Стохастическая оптимизация в информатике. 7. 2011. С. 93-116.

[62] Граничин О.Н. Неминимаксная фильтрация при неизвестных ограниченных помехах в наблюдениях // Автоматика и телемеханика. 2002. № 9. С. 125-133.

[63] Granichin O.N. Linear Regression and Filtering under Nonstandard Assumptions (Arbitrary noise) // IEEE Trans. on Automat. Contr. 49(10). 2004. P. 1830-1835.

[64] Fedin D.S., Granichin O.N., Dedkov Yu.S., Molodtsov S.L. Method of measurements with random perturbation: Application in photoemission experiments // Review of Scientific Instruments. 79. 2008. 036103.

[65] Vakhitov A., Granichin O., Vlasov V. Adaptive control of SISO plant with time-varying coefficients based on random test perturbation // Proc. of the American Control Conference. 2010. P. 4004-4009.

[66] Кривоконъ Д.С., Вахитов А. Т. Нестационарная оптимизация с шагом предсказания в задаче отслеживания объекта при помощи двух камер // Стохастическая оптимизация в информатике. 7. 2011. С. 117-128.

[67] Amelin K.S. Randomization in controls for the optimization of a small UAV flight under unknown arbitrary wind disturbances // Cybernetics and Physics. 1(2). 2012. P. 79-88.

[68] Граничин О.Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения // Вестник Ленинградского университета. Сер. 1. 1989. №1(4). С. 19-21.

[69] Spall J.C. Multivariate stochastic aproximation using a simultaneous perturbation gradient aproximation // IEEE Trans. Automat. Contr. 37(3). 1992. P. 332-341.

[70] Поляк Б. Т., Цыбаков А.Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации // Проблемы передачи информации. 1990. 26. С. 126-133.

[71] Chen H.-F., Duncan Т.Е., Pasik-Duncan В.A Kiefer-Wolfowitz Algorithm with Randomized Differences // IEEE Trans. Automat. Contr. 1999. 44(3). P. 442-453.

[72] Граничин О.Н. Рандомизированные алгоритмы стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2002. №2. С. 44-55.

[73] Граничин О.Н. Оптимальная скорость сходимости рандомизированных алгоритмов стохастической аппроксимации при произвольных помехах // Автоматика и телемеханика. 2003. № 2. С. 88-99.

[74] Граничин О.Н., Измакова О.А. Рандомизированный алгоритм стохастической аппроксимации в задаче самообучения // Автоматика и телемеханика. 2005. № 8. С. 52-63.

[75] Волкович Я.В., Граничин О.Н. Адаптивная оптимизация сервера, обрабатывающего очередь заданий // Стохастическая оптимизация в информатике. 1. 2005. С. 17-28.

[76] Граничин О.Н. Стохастическая оптимизация и системное программирование // Стохастическая оптимизация в информатике. 6. 2010. С. 3-44.

[77] Вахитов А.Т., Граничин О.Н., Гуревич Л.С. Алгоритм стохастической аппроксимации с пробным возмущением на входе в нестационарной задаче оптимизации // Автоматика и телемеханика. 2009. № 11. С. 70-79.

[78] Granichin 0., Gurevich L., Vakhitov A. Discrete-time minimum tracking based on stochastic approximation algorithm with randomized differences // In: Proc. of the Conference on Decision and Control. 2009. P. 5763-5767.

[79] Вахитов А.Т., Граничин О.Н., Панъшенсков М.А. Методы оценивания пропускной способности в распределенных системах // Нейрокомпьютеры: разработка, применение. 2009. № 11. С. 45-53.

[80] Antal С., Granichin О., Levi S. Adaptive autonomous soaring of multiple UAVs using SPSA // In: Proc. of the IEEE Conference on Decision and Control. 2010. P. 3656-3661.

[81] Граничин О.Н., Фомин В.Н. Адаптивное управление с использованием пробных сигналов // Автоматика и телемеханика. 1986. № 2. С. 100-112.

[82] Chen H.-F., Guo L. Convergence rate of least-squares stochastic systems // Int. Journal of Control. 1986. 44(5). P. 1459-1477.

[83] Campi M.G., Weyer E. Non-asymptotic confidence sets for the parameters of linear transfer functions // IEEE Trans. Automat. Control. 55(12). 2010. P. 2708-2720.

[84] Calafiore G.C., Fagiano L. Robust model predictive control: the random convex programming approach // Proc. of IEEE International Symposium on Intelligent Control. 2011. P. 222-227.

[85] Amelin K.S., Granichin O.N. Randomized controls for linear plants and confidence regions for parameters under external arbitrary noise // In: Proc. of the American Control Conference. 2012. P. 851-856.

[86] Amelin K., Amelina N., Granichin O., Granichina O. Two procedures with randomized controls for the parameters' confidence region of linear plant under external arbitrary noise // In: Proc. of IEEE International Symposium on Intelligent Control. 2012. P. 1226-1231.

[87] Amelin K., Amelina N., Granichin O., Granichina O. Combined procedure with randomized controls for the parameters' confidence region of linear plant under external arbitrary noise // In: Proc. of the IEEE Conference on Decision and Control. 2012.

[88] Tempo R., Calafiore G., Dabbene F. Randomized Algorithms for Analysis and Control of Uncertain Systems, with Applications. — London: Springer-Verlag. 2012.

[89] Calafiore G, Polyak В. Т. Stochastic algorithms for exact and approximate feasibility of robust LMIs // IEEE Trans. Autom. Control. 46. 2001. P. 1755-1759.

[90] Polyak B.T., Tempo R. Probabilistic robust design with linear quadratic regulators // Syst. Control Lett. 43. 2001. P. 343-353.

[91] Поляк Б. Т., Щербаков П.С. Робастная устойчивость и управление. — М.: Наука. 2002. 303 с.

[92] Щербаков П. С. Генерирование устойчивых полиномов // Стохастическая оптимизация в информатике. 2009. 5. С. 65-90.

[93] Candes E., Romberg J., Тао Т. Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information // IEEE Trans. Inform. Theory. 2006. 52(2). P. 489-509.

[94] Donoho D. Compressed sensing // IEEE Trans. Inform. Theory. 2006. 52(4). P. 1289-1306.

[95] Барабанов А.Е., Граничин О.Н. Оптимальный регулятор линейного объекта с ограниченной помехой // Автоматика и телемеханика. 1984. № 5. С. 39-46.

[96] Кашин Б.С, Темляков В.И. Замечание о задаче сжатого измерения // Мат. заметки. 2007. 82. № 6. С. 829-837.

[97] Граничин О.Н. Рандомизация измерений и ^-оптимизация // Стохастическая оптимизация в информатике. 5. 2009. С. 3-23.

[98] Граничин О.Н., Павленко Д.В. Рандомизация данных и l_1-оптимизация // Компьютерные инструменты в образовании. 2010. №1. С. 5-13.

[99] Граничин О.Н., Павленко Д.В. Рандомизация получения данных и l_1-оптимизация (опознание со сжатием) (Обзор) // Автоматика и телемеханика. 2010. № 11. С. 3-28.

Рандомизация в задаче оценки глубины точки при помощи одной камеры на основе идеи асимптотического наблюдателя

Д. С. Кривоконь

А. Т. Вахитов, к. ф.-м. н.

Санкт-Петербургский государственный университет

dmitry00@gmail.com, alexander.vakhitov@gmail.com

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

Ключевые слова: рандомизация, оценка глубины точки, динамические системы.

Список литературы

[1] Klein G., Murray D. Parallel tracking and mapping for small AR workspaces // In: Proc. of the 6th IEEE and ACM International Symposium on Mixed and Augmented Reality. 2007. P. 225-234.

[2] Lucas B.D., Kanade T. An iterative image registration technique with an application to stereo vision // In: Proc. of the 7th International Joint Conference on Artificial intelligence. 1981.

[3] Horn B.K.P., Schunck B.G. Determining optical flow // Artificial intelligence. 1983. 17(1). P. 185-203.

[4] Lourakis M., Argyros A. The Design and Implementation of a Generic Sparse Bundle Adjustment Software Package Based on the Levenberg-marquardt Algorithm. Technical Report 340. Institute of Computer Science-FORTH. Heraklion. Crete. Greece. 2004.

[5] Zarrouati N., Aldea E., Rouchon P. S'0(3)-invariant Asymptotic Observers for Dense Depth Field Estimation Based on Visual Data and Known Camera Motion. arXiv preprint arXiv:1103.2539. 2011.

[6] Граничин О.Н. Процедура стохастической аппроксимации с возмущением на входе // Автоматика и телемеханика. 1992. №2. С. 97-104.

[7] Han M., Kanade T. Reconstruction of a scene with multiple linearly moving objects // In: Proc. of IEEE Conference on the Computer Vision and Pattern Recognition. 2000. P. 542-549.

[8] Sturm P. Structure and motion for dynamic scenes the case of points moving in planes // In: Proc. of the European Conference on Computer Vision. 2002. P. 507-509.

[9] Граничин О.Н. Об одной стохастической рекуррентной процедуре при зависимых помехах в наблюдении, использующей на входе пробные возмущения // Вестник Ленингр. ун-та. Сер. 1. 1989. Вып.1(4). С. 19-21.

[10] Spall J.C. Multivariate stochastic aproximation using a simultaneous perturbation gradient aproximation // IEEE Trans. Automat. Contr. 1992. 37(3). P. 332-341.

[11] Поляк Б. Т., Цыбаков А.Б. Оптимальные порядки точности поисковых алгоритмов стохастической аппроксимации // Проблемы передачи информации. 1990. № 2. С. 45-53.

[12] Granichin О., Gurevich L., Vakhitov A. Discrete-time minimum tracking based on stochastic approximation algorithm with randomized differences // In: Proc. of the Combined 48th IEEE Conf. on Decision and Control and 28th Chinese Control Conf. Shanghai. P.R. China. 2009. P. 5763-5767.

Дискретные системы

Обобщение метода Крылова для задач массового обслуживания

К. О. Видяева, аспирант

Санкт-Петербургский государственный университет

karina.vidyaeva@gmail.com

Рассматривается метод приближенного вычисления fc-минимального многочлена оператора. Подход использует вычисленные значения функционалов от итераций оператора. Обсуждаются особенности алгоритма при использовании метода Монте-Карло. Приводятся численные примеры использования метода в теории массового обслуживания.

Ключевые слова: fe-минимальный многочлен оператора, спектр линейного оператора, метод Монте-Карло, стационарный режим.

Список литературы

[1] Ермаков СМ., Видяева К. О. Об оценке спектра линейного оператора // Вестник СПбГУ. Сер. 1. Вып. 1. 2012. С. 11-18.

[2] Гантмахер Ф.Р. Теория матриц. — Изд. 4-е, дополненное. Москва: Наука. 1988. 548 с.

[3] Ермаков СМ. Метод Монте-Карло в вычислительной математике. Вводный курс. — СПб: "Невский Диалект". Москва: "Бином". 2009. 192 с.

Математический анализ процесса работы с М FIFO-очередями

А. В. Драц,

А. В. Соколов д. ф.-м. н.

ПетрГУ, ИПМИ КарНЦ РАН, Петрозаводск

adeon88@mail.ru, avs@krc.karelia.ru

В работе построена математическая модель поведения М очередей в памяти одного уровня, когда на нечетном шаге возможно включение в одну из очередей, а на нечетном — исключение. Вычислена вероятность исключения из пустой очереди и средний размер очередей после N шагов.

Ключевые слова: FIFO-очереди, динамические структуры данных, математическое моделирование.

Список литературы

[1] Кнут Д. Искусство программирования для ЭВМ. — М.: Мир. 2001. Т. 1. - 411 с.

[2] Амелина Н.О. Мультиагентные технологии, адаптация, самоорганизация, достижение консенсуса // Стохастическая оптимизация в информатике. 7(1). 2011. С. 149-185.

[3] Боллапрагада В., Мэрфи К., Уайт У. Структура операционной системы Cisco IOS. — М.: Вильяме, 2002. — 208 с.

Статистический анализ ошибок при численном решении систем квазилинейных уравнений

Д. А. Фиделъман,

В. Б. Христинин, к. ф.-м. н.

Санкт-Петербургский государственный университет

shirytian@gmail.com

Работа посвящена статистическому анализу ошибок, которые возникают при численном решении систем линейных и квазилинейных уравнений, в зависимости от параметров устойчивости, а также исследованию поведения статистических характеристик решения в зависимости от возмущения начальных условий по заданному вероятностному закону. Рассуждения приводятся на примере решения уравнений акустики.

Ключевые слова: системы квазилинейных уравнений, статистический анализ.

Список литературы

[1] Андерсон Д., Таннехилл Дж., Плетчер Р. Вычислительная гидромеханика и теплообмен. — М.: Мир. 1990. № 1. 384 с.

[2] Гребенюков К.А., Христинин В.Б. Изменение распределения ошибки наблюдения при движении самолета // Математические модели. Теория и приложения. Сборник статей. — СПб.: НИИХ СПбГУ. 2007. № 8. С. 94-103.

[3] Годунов С.К. Уравнения математической физики. — М.: Наука. 1971. 416 с.

[4] Тюрин Ю.Н., Макаров А. Анализ данных на компьютере. — М.: Финансы и статистика. 1995. 384 с.

Информационные системы

Алгоритмы сопоставления и слияния абстрактных синтаксических деревьев

Д. В. Павленко, аспирант

Санкт-Петербургский государственный университет

dmit00@gmail.com

Задачи сопоставления и слияния — ключевые задачи области систем контроля версий. Использование семантики сопоставляемых файлов позволяет более наглядно представлять разницу между их содержимым а также сливать разные версии одного и того же файла, автоматически разрешая конфликты. При этом основой алгоритма слияния, как правило, является алгоритм сопоставления. В работе предлагается алгоритм сопоставления абстрактных синтаксических деревьев.

Ключевые слова: система контроля версий, слияние, diff3, абстрактное синтаксическое дерево.

Список литературы

[1] Sanjeev Kh., Keshav К., Pierce В. С. A Formal Investigation of Diff3 // In: Proc. of the 27th Int. Conf. FSTTCS'07. 2007. P. 485-496.

[2] Lindholm T. A 3-way Merging Algorithm for Synchronizing Ordered Trees — the 3DM-merging and Differencing Tool for XML. 2001.

[3] Chen Y.-F., Doughs F., Huang H. TopBlend: an efficient implementation of HtmlDiff in Java // In: Proc. of WebNet. 2000. P. 88-94.

[4] Jacobson G., Vo K.-P. Heaviest Increasing/Common Subsequence Problem // In: Proc. 3rd Annual Symp. of Combinatorial Pattern Matching. 64. 1992.

[5] Asklund U. Identifying conflicts during structural merge // In: Proc. of the Nordic Workshop on Programming Environment Research. 1994. P. 231-242.

[6] Tai K.-C. The tree-to-tree correction problem // Journal of the ACM. 26(3). 1979. P. 422-433.

[7] Chawathe S.S., Rajaraman A., Garcia-Molina H., Widom J. Change detection in hierarchically structured information // In: Proc. of the Int. Conf. ACM SIGMOD. 1996. P. 493-504.

[8] Mateusz P. Augsten N. RTED: a robust algorithm for the tree edit distance // In: Proc. of the VLDB Endowment. 5(4). 2001. P. 334-345.

[9] Zhang K., Statman R., Shasha D. On the editing dis- tance between unordered labeled trees // Information Processing Letters. 42. 1992. P. 133-139.

[10] Demaine E.D., Mozes S., Rossman В., Weimann 0. An optimal decomposition algorithm for tree edit distance // ACM Transactions on Algorithms. 6. 2009.

[11] Dulucq S., Touzetee H. Analysis of tree edit distance algorithms // In: Proc. of the 14th Annual Symp. on Combinatorial Pattern Matching. 2003.

[12] Wang Y., DeWitt D., Cai J.-Y. X-Diff: an effective change detection algorithm for XML documents // In: Proc. 19th Int. Conf. on Data Engineering. 2003. P. 519-530.

[13] Yang S., Bhowmick S., Dewey C. BioDIFF: an effective fast change detection algorithm for biological annotations // In: Proc. of the 12th Int. Conf. on Database Systems for Advanced Applications. 2007. P. 275-287.

[14] Parr T. The Definitive ANTLR Reference: Building Domain-Specific Languages. Pragmatic Bookshelf. 2007.

[15] Munkres J. Algorithms for the assignment and transportation problems // Journal of the Society for Industrial and Applied Mathematics. 1957. P. 32-38.

[16] Амелин К.С, Граничин О.Н. Новые рандомизированные алгоритмы в управлении и обработке данных // Стохастическая оптимизация в информатике. 7. 2011. С. 3-48.

[17] Рахитов А.Т, Гуревич Л. С, Павленко Д.В. Обзор алгоритмов стереозрения // Стохастическая оптимизация в информатике. 4. 2008. С. 151-169.

Использованием линейных матричных неравенств для определения области допустимых значений фильтра Калмана

В. М. Понятский, к. т. н., доцент

ГУП "Конструкторское бюро приборостроения", Тула

kbkedr@tula.net, pwmru@rambler.ru

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

Ключевые слова: динамический объект, параметры.

Список литературы

[1] Сейдж Э.П., Мелса Дж.Л. Теория оценивания и ее применение в связи и управлении. — М.: Связь, 1976.

[2] Баландин Д.В., Коган М.М. Синтез законов управления на основе линейных матричных неравенств. — М.: Физматлит, 2007.

[3] Понятский В.М. Проектирование фильтра Калмана на основе линейных матричных неравенств // Материалы XI международной научной конференции Современные проблемы математики, механики, информатики (19-21 сентября 2011 г.) - Тула: ТулГУ. 2011.

[4] Понятский В.М. Повышение помехоустойчивости системы управления вращающегося летательного аппарата // Проблемы совершенствования робототехнических и интеллектуальных систем летательных аппаратов. М.: МАИ. 2005.

[5] Кузьмин С. 3. Основы теории цифровой обработки радиолокационной информации — М.:Сов. Радио. 1974.- 432 с.

[6] Корсун В.П., Кралин В.В., Мотуз Г.И. Проектирование фильтра кскользящегоа сглаживания квадратичной траектории // Артиллерийское и стрелковое вооружение. 2008. Вып. 4. С. 15-23.

Исследование динамического объекта с помощью конечно—частотного метода идентификации по результатам испытаний

В. М. Понятский, к. т. н., доцент

ГУП "Конструкторское бюро приборостроения", Тула

kbkedr@tula.net, pwmru@rambler.ru

Рассмотрены вопросы оценки коэффициентов линейного динамического объекта в условиях пассивного эксперимента с помощью метода конеч-но?частотной идентификации. Результаты моделирования показывают, что для получения оценок коэффициентов линейной модели выбор частот входного сигнала должен быть ближе к значению сопрягающих частот объекта.

Ключевые слова: идентификация, динамический объект, модель, оценка, параметры.

Список литературы

[1] Александров А.Г. Идентификатор динамических процессов ИДП-1 на базе сигнального процессора ADSP - 21990 // Материалы V Международной конференции "Идентификация систем и задачи управления" М.: ИПУ. 2006. С. 2102-2109.

[2] Амелин К.С, Граничин О.Н. Новые рандомизированные алгоритмы в управлении и обработке данных // Стохастическая оптимизация в информатике. 7. 2011. С. 3-48.

[3] Понятский В.М., Замотаев И.В., Киселев В.Б. Идентификация нестационарного динамического объекта с использованием метода инвариантного погружения // Материалы VII Международной конференции "Идентификация систем и задачи управления". М.: ИПУ. 2008.

Гибридные компьютеры

Нелинейные динамические системы как основа новых интеллектуальных систем

Е. Н. Бендерская, к. т. н.

Санкт-Петербургский государственный политехнический университет

helen.bend@gmail.com

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

Ключевые слова: нелинейная динамическая система, хаотическая динамика, распознавание образов, интеллектуальные задачи, искусственный интеллект.

Список литературы

[1] Журавлев Ю.И., Рязанов В.В., Сенъко О.В. Распознавание. Математические методы. Программная система. Практические применения — М.: Фазис. 2006. 176 с.

[2] Журавлев Ю.И. Корректные алгебры над множествами некорректных (эвристических) алгоритмов. Часть III // Кибернетика. 1978. № 2. С. 35-43.

[3] Журавлев Ю.И. Об алгебраическом подходе к решению задач распознавания или классификации // Проблемы кибернетики. 1978. Т. 33. С. 5-68.

[4] Галушкин А.И. Нейронные сети. Основы теории. — М.: Изд-во Горячая Линия-Телеком. 2011. 496 с.

[5] Колесников А.А. Синергетическая теория управления. — М.: Энергоатомиздат. 1994. 344 с.

[6] Колесников А.А. Синергетические методы управления сложными системами: Теория системного синтеза. — М.: КомКнига. 2006. 240 с.

[7] Потапов А. С. Распознавание образов и машинное восприятие. — СПб.: Политехника. 2007. 552 с.

[8] Андриевский Б.Р., Фрадков А.Л. Управление хаосом: методы и приложения. П. Приложения // Автоматика и телемеханика. 2004. № 4. С. 3-34.

[9] Андриевский Б.Р., Фрадков А.Л. Управление хаосом: методы и приложения. I. Методы // Автоматика и телемеханика. 2003. № 5. С. 3-45.

[10] Benderskaya E.N. Nonlinear trends in modern artificial intelligence: a new perspective // Beyond AI: Interdisciplinary Aspects of Artificial Intelligence. Topics in Intelligent Engineering and Informatics. Spriger. 2012. 4. P. 113-124.

[11] Граничин О.Н., Sysoev S.S. On some characteristics of computers of new generation // In: Proc. of the Int. Conf. Physics and Control, St. Petersburg, Russia, 2003. 3. P. 804-807.

[12] Граничин О.Н., Молодцов С.Л. Создание гибридных сверхбыстрых компьютеров // Стохастическая оптимизация в информатике. 2006. № 2. С. 219-253.

[13] Граничин О.Н. Характеристики перспективных принципиально новых компьютерных устройств и систем // Механика, управление и информатика. 2011. № 5. С. 147-161.

[14] Владимирович А.Г., Граничин О.Н., Макаров А.А. Нестандартная машина Тьюринга // Стохастическая оптимизация в информатике. 2005. № 1. С. 29-47.

[15] Granichin O.N., Vasil'ev V.I. Computational model based on evolutionary primitives. Turing machine generalization // International Journal of Nanotechnology and Molecular Computation. 2010. 2. № 2. P. 30-43.

[16] Граничин О.Н., Васильев В.И. Гибридная модель процесса вычислений: обобщение концепции машины Тьюринга // Нейрокомпьютеры: разработка, применение, 2010, № 6. С. 51-58.

[17] Бендерская Е.Н., Жукова СВ. Решение задач кластеризации с использованием хаотической нейронной сети // Нейроинформатика-2005. VII Всероссийская научно-техническая конференция. Сборник научных трудов. Ч. 1. М.: МИФИ. 2005. С. 54-60.

[18] Бендерская Е.Н., Жукова СВ. Осцилляторные нейронные сети с хаотической динамикой в задачах кластерного анализа // Нейрокомпьютеры: разработка, применение. 2011. № 7. С. 74-86.

[19] Benderskaya E.N., Zhukova S. V. Clustering by chaotic neural networks with mean field calculated via Delaunay triangulation // Lecture Notes in Computer Science. Spriger. LNAI. 2008. 5271. P. 400-416.

[20] Пиковский А., Розенблюм М., Курте Ю. Синхронизация. Фундаментальное нелинейное явление. — М.: Техносфера. 2002. 496 с.

ABSTRACTS

Randomized Algorithms

Close Loops, Averaging and Randomization in Control and Data Mining

O. N. Granichin

Saint Petersburg State University

O1eg_granichin@mail.ru

Key words: information, signals, data, knowledge, control, feedback, averaging, randomization.

This article is based on the materials prepared for the workshop “Randomization and Averaging in Estimation, Optimization and Control” which was proposed by the author together with A.L. Fradkov at the international conference IEEE MSC-2012. The purpose of the workshop was to explain the key results and applications of the two important tools for system analysis and design, namely, randomization and averaging. These tools can largely facilitate the numerical solutions of various estimation, optimization and adaptive control problems, which are typically formulated under limited resources and insufficient data.

Bibliogr.: 99 refs.