СОДЕРЖАНИЕ

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

Амелин К.С, Граничин О.Н. (СПбГУ) Новые рандомизированные
алгоритмы в управлении и обработке данных 
 ................................       3

Морозков М.А. (СПбГУ) Быстрый рандомизированный алгоритм
нахождения точного количества кластеров в большом множестве дан­
ных
   ....................................................................................................     69

Смирнов С.И. (СПбГУ) Квазирандомизированный метод решения
систем линейных уравнений 
 ............................................................     

Фильтрация

Амелин К.С. (СПбГУ) Технология программирования легкого БПЛА
для мобильной автономной группы
...................................................     93

Кривоконь Д.С, Вахитов А.Т. (СПбГУ) Нестационарная оптимиза­
ция с шагом предсказания в задаче отслеживания объекта при по­
мощи двух камер
   ............................................................................................................. 116

Понятский В.М. (ГУП "КБП", Тула) Идентификация нестационар­
ного динамического объекта методом инвариантного погружения на
закрепленном интервале
............................................................................................................. 128

Понятский В.М. (ГУП "КБП", Тула) Синтез интервального фильтра
Калмана на основе минимаксного подхода 
 ............................................................................................................. 142

Мультиагентные системы

Амелина Н.О. (СПбГУ) Мультиагентные технологии, адаптация, са­
моорганизация, достижение консенсуса 
 ............................................................................................................. 149

Парсегов С.Э. (ИПУ, Москва) Обобщенные линейные алгоритмы
управления формациями 
 ............................................................................................................. 186

Дискретные стохастические системы

Трубников В.Н., Чирков М.К. (СПбГУ) Условия представимости
обобщенных регулярных языков стохастическими автоматами
............................................................................................................. 204

Кривулин Н. К., Нев О.А. (СПбГУ) Асимптотические свойства век­
тора состояний обобщенной линейной стохастической системы с сим­
метричной матрицей
............................................................................................................. 232

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

Павленко Д.В. (СПбГУ) Сопоставление синтаксических элементов в системах
контроля версий 
 ............................................................................................................. 240

Шац В.Н. (СПб) Стохастический метод решения задач классифи­
кации и обучения 
 ............................................................................................................. 257

Abstracts   ................................................................................................................. 269

 

 

 

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

НИИ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ

СТОХАСТИЧЕСКАЯ ОПТИМИЗАЦИЯ В ИНФОРМАТИКЕ

Издается с 2005 года

ТОМ 7

Выпуск 1

Издательство С.-Петербургского университета , 2 0 11


УДК 519.712 ВКК 32.811.7

С82

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

ББК 32.811.7

©   Авторы статей, 2011


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

Новые рандомизированные алгоритмы в управлении и обработке данных

К. С. Амелин, аспирант,

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

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

Институт проблем машиноведения РАН

Oleg_granichin@mail.ru, konstantinamelin@mail.ru

Рандомизация во многих случаях позволяет "обогатить" данные наблю­дений и разработать "быстрые" алгоритмы, существенно сокращающие ко­личество операций и "подавляющие" влияние систематических ошибок (эф­фект смещения при произвольных помехах), точность которых обычно несу­щественно зависит от размерности данных.

Рандомизированный алгоритм не что иное, как процедура, при которой один или несколько шагов основаны на случайном выборе правила, т. е. при использовании рандомизированных алгоритмов на каком-то этапе вместо то­го, чтобы самим принять решение, мы призываем "судьбу" (случай) выбирать за нас. Но тогда естественно возникает вопрос: зачем прибегать к "судьбе" мудрому человеку? "Судьба" не является специалистом ни в чем, выбор де­лается случайно. Итак, почему от рандомизированных алгоритмов мооюет быть польза? Сознательное использование рандомизированных методов тре­бует ответов себе на этот вопрос, часть из которых обсуждается в статье.

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

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

86 наименований

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

Граничин О.Н., Хантулева Т.А. Гибридные системы и рандо­мизированные измерения в неравновесных процессах // Диф­ференциальные уравнения и процессы управления, электрон­ный журнал, per. №Р23275 от 07.03.97. №3. 2004.

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

Деревицкий Д.П., Фрадков А.Л. Прикладная теория дискрет­ных адаптивных систем управления. М.: Наука, 1981.

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

Kushner H.J., Yin G.G. Stochastic Approximation Algorithms and Applications. — New York: Springer-Verlag. 2002. 415 p.

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

Граничин О.Н. Неасимптотическое доверительное множество для параметров линейного объекта управления при почти про­извольных помехах // Автоматика и телемеханика. 2011.

Nemirovski A. Several NP-hard problems arising in robust stability analysis // J. Matrix Anal. Appl. 1993. Vol. 6. P. 99-105.

Braatz R.P., Young P.M., Doyle J.C., Morari M. Computational complexity of /л calculation // IEEE Trans. Autom. Control. 1994. Vol. 39. P. 1000-1002.

Blondel V.D., Tsitsiklis J.N. A survey of computational complexity results in systems and control // Automatica. 2000. Vol. 36. P. 1249-1274.

 

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

Metropolis N., Ulam S. The Monte Carlo Method // J. Amer. statistical assoc. 1949. Vol.  44. No. 247. P. 3354341.

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

Fisher R.A. The Design of Experiments. — Edinburgh: Oliver and Boyd, 1935.

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

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

Young P.С. Recursive Estimation and Time-Series Analysis. An Introduction. — Berlin-Heidelberg: Springer. 1984.

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

Граничин О.Н. Оценивание точки минимума неизвестной функции, наблюдаемой на фоне зависимых помех // Пробле­мы передачи информации. 1992. №2. С. 16-20.

Goldenshluger A.V., Polyak В. Т. Estimation of regression parameters with arbitrary noise // Mathematical Methods of Statistics. 1993. Vol. 2. No. 1. P. 18-29.

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

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

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

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

Spall J.C. Multivariate Stochastic Aproximation Using a Simultaneous Perturbation Gradient Aproximation // IEEE Trans. Automat. Contr. 1992. Vol. 37. No. 3. P. 332-341.

Chen H.-F., Duncan Т.Е., Pasik-Duncan B.A. Kiefer-Wolfowitz algorithm with randomized differences // IEEE Trans. Automat. Contr. 1999. Vol.   44. No. 3. P. 442-453.

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

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

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

Metropolis N., Rosenbluth A. W., Rosenbluth M. N., Teller A. Н., and Teller E. Equation of State Calculations by Fast Computer Machines // J. Chemical Physics. 21. 6. June 1953. P. 1087-1092.

Kirkpatrick S., Gelatt Jr. C. D., and Vecchi M. P. Optimization by Simulated Annealing // Science. 220. 1983. P. 671-680.

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

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

Holland J.H. Adaptation in natural and artificial systems. — University of Michigan Press. Ann Arbor. 1975.

 

Вапник В.Н., Червоненкис А.Я. Теория равномерной сходимо­сти частот появления событий к их вероятностям и задача по­иска оптимального решения по эмпирическим данным // Ав­томатика и телемеханика. №2. 1971.

Вапник В.Н., Червоненкис А. Я. Теория распознавания обра­зов. — М.: Наука. 1974.

Фомин В.Н. Математическая теория обучаемых опознающих систем. — Л.: Изд-во Ленингр. ун-та. 1976. 236 с.

Vidyasagar M. A Theory of Learning and Generalization. — New York: Springer. 1997.

Vidyasagar M. Statistical learning theory and randomized algorithms for control // IEEE Control Systems. 1998. No 12. P. 69-85.

Calafiore G.C., Campi M.C. The scenario approach to robust control design // IEEE Trans. Automat. Control. Vol. 51. No. 5. 2006. P. 742-753.

Tempo R., Calafiore C, Dabbene F. Randomized Algorithms for Analysis and Control of Uncertain Systems. — New York: Springer-Verlag. 2005.

Calafiore C, Dabbene F., Tempo R. Research on probabilistic methods for control system design // Automatica. Vol. 47. 2011. P. 1279-1293

Stengel R.F., Ray L.R. Stochastic robustness of linear time-invariant control systems // IEEE Trans. Autom. Control. 1991. Vol. 36. P. 82-87.

Khargonekar P.P., Tikku A. Randomized algorithms for robust control analysis have polynomial time complexity // Proc. of Conf. on Decision and Control. 1996. P. 3470-3475.

Barmish B.R., Lagoa CM. The uniform distribution: A rigorous justification for its use in robustness analysis // Math. Control, Signals, Syst. Vol. 10. 1997. P. 203-222.

 

Oishi Y., Kimura H. Randomized algorithms to solve parameter-dependent linear matrix inequalities and their computational complexity // Proc. of Conf. on Decision and Control. Orlando. USA. 2001. P. 2025-2030.

Calafiore G, Polyak B.T. Stochastic algorithms for exact and approximate feasibility of robust LMIs // IEEE Trans. Autom. Control. Vol. 46. 2001. P. 1755-1759.

Fujisaki Y., Dabbene F., Tempo R. Probabilistic robust design of LPV control systems // Automatica. Vol. 39. 2001. P. 1323-1337.

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

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

Kanev S., De Schutter В., Verhaegen M. The ellipsoid algorithm for probabilistic robust controller design // Proc. of Conf. on Decision and Control. Las Vegas. USA. 2002. P. 2248-2253.

Ishii H., Basar Т., Tempo R. Randomized algorithms for quadratic stability of quantized sampled-data systems // Automatica. Vol. 40. 2004. P. 839-846.

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

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

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

Avros R., Granichin О., 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. 2011. P. 131-155.

Granichin O., Morozkov M., Volkovich Z. Necessary conditions for the confidence level of the randomized algorithm of finding the true number of clusters // Proc. of IEEE Int. Symposium on Intelligent Control (MSC-2011). Denver. USA. 2011. P. 1002-1007.

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

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

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

Chen H.-F., Guo L. Convergence rate of least-squares stochastic systems // Int. J. of Control. 1986. Vol. 44. No. 5. P. 1459-1477.

Campi M.C., Weyer E. Non-asymptotic confidence sets for the parameters of linear transfer functions // IEEE Trans. Automat. Control. Vol. 55. No. 12. 2010. P. 2708-2720.

Calafiore G.C., Fagiano L. Robust model predictive control: the random convex programming approach // Proc. of IEEE Int. Symposium on Intel. Control. Denver. USA. 2011. P. 222-227.

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

Granichin O.N. Linear regression and filtering under nonstandard assumptions (Arbitrary noise) // IEEE Trans, on Automat. Contr. Vol.   49. Oct. 2004. No. 10. P. 1830-1835.

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

 

Vakhitov A., Granichin O., Vlasov V. Adaptive control of SISO plant with time-varying coefficients based on random test perturbation // Proc. of American Control Conf. 2010. Baltimore. USA. P. 4004-4009.

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

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

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

Candes E., Romberg J., Тао Т. Robust uncertainty principles: Exact signal reconstruction from highly incomplete frequency information // IEEE Trans. Inform. Theory. Feb. 2006. Vol. 52. No. 2. P. 489-509.

Donoho D. Compressed sensing // IEEE Trans. Inform. Theory. Apr. 2006. Vol.   52. No. 4. P. 1289-1306.

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

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

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

Вахитов А.Т., Граничин О.Н., Сысоев С.С. Точность оцени­вания рандомизированного алгоритма стохастической оптими­зации // Автоматика и телемеханика. 2006. № 4. С. 86-96.

Tang Q-Y., Chen H.F., Han Z-J. Convergence rates of Perturbation-Analysis-Robbins-Monro-Single-Run algorithms for single server queues // IEEE Trans, on Automatic Control. 1997. Vol. 42. No. 10. P. 1442-1447.

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

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

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

Александров А.Г., Орлов Ю.Ф. Конечно-частотная идентифи­кация: динамический алгоритм // Проблемы управления. 2009.

№ 4. С. 2-8.

Bai E.W., Nagpal K.M., Tempo R. Bounded-error parameter estimation: Noise models and recursive algorithms // Automatica. Vol. 32. 1996. P. 985-999.

Garulli A., Giarre L., Zappa G. Identification of approximated Hammerstein models in a worst-case setting // IEEE Trans. Autom. Control. Vol. 47. No. 7. Dec. 2002. P. 2046-2050.

Соколов В. Ф. Оценка качества робастной системы управления при неизвестных верхних границах возмущений и помехи из­мерений // Автоматика и телемеханика. Ж 9. 2010. С. 3-18.

Фомин В.Н. Методы управления линейными дискретными объектами. — Л.: Изд-во Ленингр. ун-та. 1985. 336 с.

 

 

Быстрый рандомизированный

алгоритм нахождения точного количества

кластеров в большом множестве данных

М. А. Морозков

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

mmorozkov@gmail.com

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

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

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

[1] Boyd S., Mattingley J., Grant M., Wang Y. Real-Time Embedded Convex Optimization. — Plenary Speech on IEEE MSC-2011. 2011. Denver. USA. 2011.

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

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

[4] Calafiore G.C., Campi M.C. The scenario approach to robust control design // IEEE Trans. Automat. Control. Vol. 51. No. 5. May 2006. P. 742-753.

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

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

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

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

[9] Hartigan J. Statistical theory in clustering // J. Classification. Vol. 2. 1985.

[10] Sugar C, James G. Finding the number of clusters in a data set: An information theoretic approach // J. of the American Statistical Association. Vol. 98. 2003. P. 750-763.

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

[12] Avros R., Granichin О., 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. 2011. P. 131-155.

[13] Granichin O., Morozkov M., Volkovich Z. Necessary conditions for the confidence level of the randomized algorithm of finding the true number of clusters // Proc. of 2011 IEEE Int. Symposium on Intelligent Control. (MSC-2011). Denver. USA. 2011. P. 1002-1007.

[14] Levine E., Domany E. Resampling method for unsupervised estimation of cluster validity // Neural Computation. Vol. 13. 2001. P. 2573-2593.

 [15] Jain А.К., Moreau J. V. Bootstrap technique in cluster analysis // Pattern Recognition. Vol. 20. 1987. P. 547-568.

[16] Cuevas A., Febrero M., Fraiman R. Estimating the number of clusters // Canadian J. of Statistics. Vol. 28(2). 2000. P. 367-382.

[17] Cuevas A., Febrero M., Fraiman R. Cluster analysis: a further approach based on density estimation // Computational Statistics and Data Analysis. Vol. 28. 2001. P. 441-459.

[18] Volkovich Z., Barzily Z., Morozensky L. A statistical model of cluster stability // Pattern Recognition. Vol. 41. 2008. P. 2174-2188.

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

[20] Sharma P., Salapaka S., Beck С. A scalable approach to combinatorial library design for drug discovery // J. of Chemical Information and Modeling. Vol. 48. No. 1. 2008. P. 27-41.

[21] Aloise D., Deshpande A., Hansen P., Popat P. NP-hardness of euclidean sum-of-squares clustering // Mach. Learn. Vol. 7. No. 2. 2009. P. 245-248.

[22] Cortes J., Martinez S., Karatas Т., Bullo F. Coverage control for mobile sensing networks: variations on a theme // Proc. of Mediterranean Conf. on Control and Automation. 2002.

[23] Sheu J.B. A fuzzy clustering-based approach to automatic freeway incident detection and characterization // Fuzzy Sets Syst. Vol. 128. No. 3. 2002. P. 377-388.

[24] Sharma P., Salapaka S., Beck C. Entropy based algorithm for combinatorial optimization problems with mobile sites and resources // Proc. of American Control Conf. 2008. P. 1255-1260.

[25] Xu Y., Salapaka S., Beck CL. Dynamic maximum entropy algorithms for clustering and coverage control // Proc. of IEEE Conf. on Decision and Control (CDC-49). 2010. P. 1836-1841.

 

 

Квазирандомизированный метод решения систем линейных уравнений

С И. Смирнов, аспирант

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

q4ality@gmail.com

Как известно, решение задач о нахождении корня уравнения F (ж) = 0 и точки экстремума функции G (у), когда значения функций F и G могут быть получены со случайными помехами, возможно с помощью методов стохасти­ческой аппроксимации.

Большой прикладной интерес представляет случай, когда упомянутые значения вычисляются с помощью методов Монте-Карло. В частности, ес­ли требуется решить большую систему линейных алгебраических уравнений, то вычислительную работу можно уменьшить за счет рандомизации или кон­струирования несмещенных оценок суммы квадратов невязок (случайный вы­бор к уравнений из п, где к <С п). В обоих случаях моделируется случайный процесс, решающий поставленную задачу. Представляет большой интерес ис­пользовать технику Квази-Монте-Карло метода (КМК) при моделировании.

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

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

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

[1] Sabelfeld К., Mozartova N. Sparsified Randomization Algorithms for large systems of linear equations and a new version of the Random Walk on Boundary method // Monte Carlo Methods Appl. 2009. Vol. 15. No. 3. P. 257-284.

[2] Drineas P., Kannan R. Fast Monte Carlo algorithms for approximate matrix multiplication // Proc. of 42nd IEEE Symposium of Foundations of Computer Science. 2001. P. 452-459.

 

 [3] Drineas P., Drinea E., Huggins P.S. An experimental evalution of Monte Carlo algorithms for singular value decompositions // Lecture notes in computer science. 2003. Vol. 2563. P. 279-296.

[4] Bockek LA. Calculation of the Ritz and Galerkin coefficients by the Monte-Carlo method // USSR Computational Mathematics and Mathematical Physics. 1967. Vol. 7. No. 1. P. 231-239.

[5] Ермаков С. М. Параметрически разделимые алгоритмы // Вестник СПбГУ. 2010. Сер. 1. Вып. 4. С. 25-32.

[6] Chen X., White H. Asymptotic properties of some projection-based Robbins-Monro procedures in a Hilbert space // Studies in Nonlinear Dynamics and Econometrics. 2002. Vol. 6. P. 1-53.

[7] Golub G.H., van Loan C.F. Matrix computations. — JHU. 1996. 3rd edition.

[8] Gyorfi L. Stochastic approximation from ergodic sample for linear regression // Z.Wahrscheinlichkeitstheorie verw. Gebiete. 1980. Vol. 54. P. 47-55.

 

 


Фильтрация

Технология программирования легкого БПЛА для мобильной группы

К. С. Амелин, аспирант

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

konstantinamelin@gmail.com

Рассматривается технология создания программ для автопилота легко­го беспилотного летательного аппарата (БПЛА). Описывается трехуровневая архитектура легкого БПЛА, который оснащен стандартными исполнитель­ными механизмами, автопилотом, бортовым микрокомпьютером, и в кото­ром основным датчиком ориентирования в геодезической системе координат является навигационная система с модулями ГЛОНАС/GPS. Анализируют­ся возможности создания адаптивного управления группой БПЛА за счет применения мультиагентных технологий, а также исследуются методики со­здания программы автопилота легкого БПЛА и построения алгоритмов опти­мизации полета. В упрощенной математической модели предполагается, что на динамику полета БПЛА оказывает неконтролируемое влияние ветер, а на­блюдения производятся с неизвестными, но ограниченными ошибками в си­стеме навигации. Предлагается рандомизированный алгоритм, отфильтровы­вающий такие почти произвольные ошибки в наблюдении. Работоспособность нового алгоритма при нерегулярных помехах в наблюдениях иллюстрирует­ся примерами имитационного моделирования в сравнении с традиционными подходами.

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

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

[1] Виттих В.А., Скобелев П.О. Метод сопряженных взаимодей­ствий для управления распределением ресурсов в реальном масштабе времени // Автометрия. 2009. Т. 45. № 2. С. 84-86.

[2] Сайт по беспилотным летательным аппаратам /bpla.ru/

[3] Сечин А.Ю., Дракин М.А., Киселева А.С. Беспилотный ле­тательный аппарат: применение в целях аэрофотосъемки для картографирования. — М.:"Ракурс". 2011.

[4] Калман Р.Е., Бъюси Р. С. Новые результаты в линейной филь­трации и теории предсказания // Труды американского обще­ства инженеров-механиков. Техническая механика. 1961. Т. 83. Сер. Д. № 1. С. 123-141.

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

[6] Kibzun A.I., Кап Yu.S Stochastic Programming Problems with Probability and Quantile Functions. — Chichester: Wiley. 1996.

[7] Панков А.Р., Семенихин К.В. Минимаксная идентификация обобщенной неопределенно-стохастической линейной модели // Автоматика и телемеханика. 1998. № 11. С. 158-171.

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

[9] Степанов О.А., Осипов А.В., Васильев В.Н. Открытые муль-тиагентные системы для оперативной обработки информации в процессах принятия решений // Автометрия. 2002. №6. С. 45-61.

[10] Амелин К. С. Легкий беспилотный летательный аппарат для автономной группы // Стохастическая оптимизация в инфор­матике. Т. 6. 2010. С. 117-126.

 

[11] Амелин К.С, Антал Е.И., Васильев В.И., Граничина И.О. Адаптивное управление автономной группой беспилотных ле­тательных аппаратов // Стохастическая оптимизация в ин­форматике. Вып. 5. 2009. С. 157-166.

[12] Амелин К.С, Граничин О.И. Мультиагентное сетевое управле­ние группой легких БПЛА // Нейрокомпьютеры: разработка, применение. 2011. № 6. С. 64-72.

[13] Интернет ресурс проекта Paparazzi /paparazzi.enac.fr/.

[14] Punin Y.O., Shtukenberg A.G., Smetannikova O.G., Amelin K.S. Plagioclase twin associations from the basic volcanic rocks of the Kamchatka, Russia: growth conditions and formation mechanisms // European Journal of Mineralogy. 2010. No. 1. P. 139-145.

[15] Allen M.J. Autonomous soaring for improved endurance of a small uninhabited air vehicle // 43rd AIAA Aerospace Sciences Meeting and Exhibit (AIAA 2005). Reno. Nevada. 2005. P. 1025.

[16] Reichmann H. Cross-Country Soaring. — Minnesota: Soaring Society of America. 1978.

[17] Edwards D.J. Implementation Details and Flight Test Results of an Autonomous Soaring Controller. — NC State Univ.

[18] Antal G, Granichin O., Levi S. Adaptive autonomous soaring of multiple UAVs using simultaneous perturbation stochastic approximation // IEEE Conf. on Decision and Control (CDC-49). Atlanta. USA. 2010. P. 3656-3661.

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

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

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

 

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

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

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

[25] Granichin О., Gurevich L., Vakhitov A. Discrete-time minimum tracking based on stochastic approximation algorithm with randomized differences // Proc. of IEEE Conf. on Decision and Control (CDC-48). 2009. Shanghai. P.R. China. P. 5763-5767.

[26] Granichin O., Vakhitov A., Vlasov V. Adaptive control of SISO plant with time-varying coefficients based on random test perturbation // Proc. of American Control Conf. (ACC-2010) 2010. Baltimore. MD. USA. P. 4004-4009.

[27] Granichin O.N. Linear regression and filtering under nonstandard assumptions (Arbitrary noise) // IEEE Trans, on Automat. Contr. Vol. 49. Oct. 2004. No. 10. P. 1830-1835.

[28] Граничин О.И. Оценивание параметров линейной регрессии при произвольных помехах // Автоматика и телемеханика. 2002. №1. С. 30-41.

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

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

[31] Levy L.J. Применение фильтра Калмана в навигационной ап­паратуре // GPS World. USA. Сентябрь 1997.

 

 

Нестационарная оптимизация с шагом предсказания в задаче отслеживания объекта при помощи двух камер

Д. С. Кривоконъ,

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

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

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

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

Ключевые    слова:    нестационарная   оптимизация,   отслеживание   объекта, стерео-камера.

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

[1] Поляк Б. Т. Введение в оптимизацию. — М.: Наука. 1983.

[2] Robbins H., Monro S. A stochastic approximation method // Annals of Mathematical Statistics. 1951. Vol. 22. No. 3. P. 400-407.

[3] Kiefer J., Wolfowitz J. Stochastic estimation of the maximum of a regression function. // Annals of Mathematical Statistics. 1952. Vol. 23. No. 3. P. 462-466.

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

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

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

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

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

[9] Попков А. Ю. Градиентные методы для нестационарных задач безусловной оптимизации // Автоматика и телемеханика. 2005. № 6. С. 883-891.

[10] Kushner H.J., Yin G.G. Stochastic Approximation Algorithms and Applications. — New York: Springer-Verlag. 2002.

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

[12] Gurevich L., Vakhitov A. SPSA Algorithm for Tracking. // Proc. 12th Int. Student Olympiad on Automatic Control. 2008. P. 52-57.

[13] Фомин B.H. Методы управления линейными дискретными объектами. — Л.: Изд-во Ленингр. ун-та. 1985.

[14] Матвеев А.С, Якубович В.А. Абстрактная теория оптималь­ного управления. — СПбГУ. 1994.

[15] Zisserman A., Hartley R. Multiple View Geometry in Computer Vision. — Cambridge University Press. 2004.

[16] Mikic I., Santini S., Jain R. Video processing and integration from multiple cameras. // Proc. of the Image Understanding Workshop. Morgan-Kaufman. 1998. P. 183-187.

[17] She S. Navigation System for Autonomous Mobile Robot — a Simultaneous Localization and Mapping Approach, [online] www.ietymec.org/papers/U16.pdf

[18] Sibley G., Sukhatme G., Matthies L. The iterated sigma point kalman filter with applications to long range stereo // Proc. of Robotics: Science and Systems. 2006.

[19] Kahl F., Hartley R. Multiple-view geometry under the Ll-Norm. // IEEE Trans, on Pattern Analysis and Machine Intelligence. 2008. Vol. 30. No. 9.

 

 

Идентификация нестационарного динамического объекта методом инвариантного погружения на закрепленном интервале

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

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

kbkedr@tula.net, pwmru@rambler.ru

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

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

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

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

[2] Медич Дж. Статистически оптимальные линейные оценки и управление. - М., Энергия. 1973.

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

[4] Понятский В.М. Оценка экспериментальных характери­стик летательного аппарата методом инвариантного по­гружения // Первая Всероссийская научно-техническая конференция кФундаментальные основы баллистического проектированиян>.23-26 июня 2008 г.: Сборник материалов — Санкт-Петербург. БГТУ. 2008. Т. 1 С. 29-33

[5] Понятский В.М., Оберман М.С. Программа для идентифи­кации методом фильтрации Калмана параметров линейной нестационарной модели динамического объекта // Труды меж­дународной конференции "Третьи Окуневские чтения". Ч.З. — СПб.:БГТУ, 2003.

 

 

Синтез  интервального фильтра Калмана на основе минимаксного подхода

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

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

kbkedr@tula.net, pwmru@rambler.ru

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

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

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

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

[2] Толпегин О.В. Дифференциально-игровые методы управления движением беспилотных летательных аппаратов. - СПб. БГ-ТУ. 2009. - 244 с.

[3] Кумков СИ. Разработка совместного Российского - ISO стан­дарта (методики) обработки измерительной информации в условиях неопределенности ошибок измерений и малого чис­ла наблюдений (на основе методов интервального анализа) // Доклады Всероссийского Совещания по интервальному ана­лизу и его приложениям "ИНТЕРВАЛ-06", 1 - С.-Пб, Санкт-Петербургский государственный университет. 2006. С. 63-67, http://www.ict.nac.ru/interval/Conferences/Interval-06.

 

 

Мулътиагентные системы

Мультиагентные технологии, адаптация, самоорганизация, достижение консенсуса

Н. О. Амелина, аспирант

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

leishe@mail.ru

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

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

 

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

[1] Shoham Y., Leyton-Brown K. Multiagent Systems: Algorithmic, Game-Theoretic and Logical Foundations — London: Cambridge University Press. 2009. 513 p.

[2] Официальный сайт НПК "Генезис знаний" http://www.kg.ru/.

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

[4] Murray R.M., Astrom K.J., Boyd S.P., Brockett R.W., Stein G. Future directions in control in an information-rich world // IEEE Control Systems. 2003. Vol. 23. No. 2. P. 20-33.

[5] Городецкий В.И., Грушинский М.С., Хабалов А.В. Многоагент-ные системы (обзор) // Новости искусственного интеллекта. 1998. №2. С. 64-116.

[6] Скобелев П. О. Открытые мультиагентные системы для опера­тивной обработки информации в процессах принятия решений // Автометрия. 2002. № 6. С. 45-61.

[7] Maes P. Agent that reduce work and information overload // Communication of the ACM. July 1994. Vol. 37. No. 7. P. 30-40.

[8] Cohen P.R., Morgan J.L., Pollack M. Intentions in Communica­tion - Bradford Books. MIT Press. 1990. 508 p.

[9] Тарасов В.Б. Агенты, многоагентные системы, виртуальные со­общества: стратегическое направление в информатике и искус­ственном интеллекте // Новости искусственного интеллекта. 1998. № 2. С. 5-63.

[10] Граничина И.О. Мультиагентная система для распределения заказов // Управление большими системами. Спец. выпуск 30.1 "Сетевые модели в управлении". 2010. С. 549-566.

[11] Виттих В.А., Скобелев П.О. Метод сопряженных взаимодей­ствий для управления распределением ресурсов в реальном масштабе времени // Автометрия. 2009. Т. 45. № 2. С. 84-86.

 

[12] Каляев И.А., Гайдук А.Р., Капустян С.Г. Распределенные си­стемы планирования действий коллективов роботов. — М.: Янус-К. 2002. 292 с.

[13] Амелин К.С, Антал Е.И., Васильев В.И., Граничина И.О. Адаптивное управление автономной группой беспилотных ле­тательных аппаратов // Стохастическая оптимизация в ин­форматике. Вып. 5. 2009. С. 157-166.

[14] Antal С, Granichin О., Levi S. Adaptive autonomous soaring of multiple UAVs using SPSA // Proc. of IEEE Conf. on Decision and Control (CDC-49). 2010. Atlanta. USA. P. 3656-3661.

[15] Амелин К. С, Граничин О.И. Мультиагентное сетевое управле­ние группой легких БПЛА // Нейрокомпьютеры: разработка, применение. 2011. № 6. С. 64-72.

[16] Фрадков А.Л. Кибернетическая физика: принципы и примеры - СПб.: Наука. 2003. 208 с.

[17] Olfati-Saber R., Murray R.M. Consensus problems in networks of agents with switching topology and time-delays // IEEE Trans. Automatic Control. Sept. 2004. Vol. 49. P. 1520-1533.

[18] Ren W., Beard R.W. Distributed Consensus in Multi-vehicle Cooperative Control: Theory and Applications — Communication and Control Engineering Series. — Springer Verlag. New York. 2007. 319 p.

[19] Агаев Р.П., Чеботарев П.Ю. Сходимость и устойчивость в за­дачах согласования характеристик (обзор базовых результа­тов) // Управление большими системами. Спец. выпуск 30.1 "Сетевые модели в управлении". 2010. С. 470-505.

[20] Fax A., Murray R.M. Information flow and cooperative control of vehicle formations // IEEE Trans. Automat. Contr. Sept. 2004. Vol. 49. P. 1465-1476.

[21] Tanner H.G., Jadbabaie A., Pappas G. J. Flocking in fixed and switching networks // IEEE Trans. Autom. Contr. 2007. Vol. 52. No. 5. P. 863-868.

 

[22] Li W. Stability analysis of swarms with general topology // IEEE Trans. Syst. Man. Cybern. B. 2008. Vol. 38. No. 4. P. 1084-1097.

[23] Гершгорин С.A. Uber die abgrenzung der eigenwerte einer matrix // Изв. АН СССР, отд. физ.-мат. наук. 1931. С. 749-754.

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

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

[26] Деревицкий Д.П., Фрадков А.Л. Прикладная теория дискрет­ных адаптивных систем управления. — М.: Наука. 1981. 216 с.

[27] Fradkov A.L. Continuous-time averaged models of discrete-time stochastic systems: survey and open problems // Proc. of IEEE Conf. on Decision and Control (CDC-50). Orlando. USA. 2011.

[28] Гелиг А.Х., Леонов Г.А., Якубович В.А. Устойчивость нелиней­ных систем с неединственным состоянием равновесия. — М.: Наука. 1978. 400 с.

[29] Huang M. Stochastic Approximation for Consensus with General Time-Varying Weight Matrices // Proc. of IEEE Conf. on Decision and Control (CDC-49). 2010. Atlanta. USA. P. 7449-7454.

[30] Armbruster D., Mikhailov A.S., Kaneko K. (eds.) Networks of Interacting Machines: Production Organization in Complex Industrial Systems and Biological Cells — World Scientific. Singapore. 2005. 267 p.

[31] Glashenko A., Inozemtzev S., Grachev I., Skobelev P. Magenta Technology: case studies of Magenta i-scheduler for road transportation // Proc. of Int. Conf. on Autonomous Agents and Multi Agent Systems (AAMAS-6). Hawaii. 2007. P. 1385-1392.

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

 

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

[34] Friedrich Т.A., Sauerwald Т.В., Vilenchik D.C. Smoothed analysis of balancing networks // Random Structures and Algorithms. Aug. 2011. Vol. 39. No. 1. P. 115-138.

[35] Li H. Load balancing algorithm for heterogeneous P2P systems based on Mobile Agent // Proc. of ICEICE 2011. 2011. P. 1446-1449.

[36] Kechadi M.-T., Savvas I.K. Dynamic task scheduling for irregular network topologies // Parallel Computing. 2005. Vol. 31. No. 7. P. 757-776.

[37] Катуева Я.В. Балансировка загрузки несимметричного вы­числительного комплекса при решении задачи статистическо­го оценивания // Информатика и системы управления. 2006. № 2(12). С. 88-93.

[38] Костенецкий П. С, Лепихов А.В., Соколинский Л.Б. Техноло­гии параллельных систем баз данных для иерархических мно­гопроцессорных сред // Автоматика и телемеханика. 2007. № 5. С. 112-125.

[39] Gilly К., Juiz С, Puigjaner R. An up-to-date survey in web load balancing // World Wide Web. 2011. Vol. 14. No. 2. P. 105-131.

[40] Granichin O., Vakhitov A., Vlasov V. Adaptive control of SISO plant with time-varying coefficients based on random test perturbation // Proc. of American Control Conf. (ACC-2010). 2010. Baltimore. USA. P. 4004-4009.

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

[42] Granichin О., Gurevich L., Vakhitov A. Discrete-time minimum tracking based on stochastic approximation algorithm with randomized differences // Proc. of IEEE Conf. on Decision and Control (CDC-48). 2009. Shanghai. P.R. China. P. 5763-5767.

 

 

Обобщенные линейные алгоритмы управления формациями

С. Э. Парсегов, аспирант

Институт проблем управления РАН, Москва

parsegov@ipu.ru

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

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

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

[1] Ren W., Beard R. W., Atkins E.M. A survey of consensus problems

in multi-agent coordination // Proc. American Control Conf. 2005. Vol. 3. P. 1859-1864.

[2] Pavone M., Frazzoli E. Decentralized policies for geometric pattern formation and path coverage // ASME Journal on Dynamic Systems, Measurement, and Control. 2007. Vol. 129. No. 5. P. 633-643.

[3] Ramirez J.L.,Pavone M., Frazzoli E. and Miller D. W. Distributed Control of Spacecraft Formations via Cyclic Pursuit: Theory and Experiments // AIAA Journal of Guidance, Control, and Dynamics. 2010. Vol. 33. No. 5. P. 1655-1669.

[4] Петрикевич Я.И. Линейные алгоритмы управления геометри­ческим расположением объектов в многоагентной системе // Управление большими системами. Спец. выпуск 30.1 "Сетевые модели в управлении". — М.: ИПУ РАН. 2010. С. 665-680.

[5] Щербаков П. С. Управление формациями: схема Ван Лоуна и другие алгоритмы // Управление большими системами. Спец. выпуск 30.1 "Сетевые модели в управлении". — М.: ИПУ РАН. 2010. С. 681-696.

[6] Поляк Б. Т., Цыпкин Я.З. Устойчивость и робастная устойчи­вость однотипных систем // Автоматика и телемеханика. 1996. № 11. С. 91-104.

[7] Нага S., Hayakawa Т., Sugata H. Stability analysis of linear systems with generalized frequency variables and its applications to formation control // Proc. Decision and Control Conf. 2007. P. 1459-1466.

[8]  Воеводин В.В., Кузнецов Ю.А. Матрицы и вычисления. — М.: Наука. 1984. 320 с.


 

 

Дискретные стохастические системы

Условия представимости обобщенных регулярных языков стохастическими автоматами

В. Н. Трубников,

М. К. Чирков, д. ф.-м. н.

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

vakh08@mail.ru

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

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

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

[1] Чирков М.К., Пономарева А.Ю. Стационарные детерминиро­ванные и вероятностные автоматы (Теория автоматных моде­лей) - СПб.: Изд. СПбГУ. 2008. 248 с.

[2] Трубников В.Н., Чирков М.К. Об эквивалентном преобразова­нии R-нечетких автоматов в стохастические // Стохастическая оптимизация в информатике. Том 6 (Выи 1). — СПб.: Изд. СПбГУ. 2010. С. 184-202.

[3] Чирков М.К., Наср Я. О стохастических и нестохастических минимальных формах стохастических автоматов // Теория и приложения дискретных систем. — СПб.: Изд. СПбГУ. 1995. С. 37-67.

[4] Masakazu N., Namio H. Fuzzy events realized by probabilistic automata // Inform, and Control. Vol. 12. No. 15. 1968. P. 284-303.

[5] Шестаков А.А., Чирков М.К. Обобщенные конечные автома­ты: Поведенческая эквивалентность и проблемы оптимизации.

-   Апатиты: Изд. КНЦ РАН. 1992. 160 с.

[6] Чирков М.К., Кабаве М. Абстрактный анализ обобщенных ко­нечных автоматов // Теория и приложения дискретных систем.

-   СПб.: Изд. СПбГУ. 1995. С. 3-36.

[7] Чирков М.К., Кабаве М. Абстрактный синтез обобщенных ко­нечных автоматов // Математическое моделирование дискрет­ных систем. - СПб.: Изд. СПбГУ. 1995. С. 3-37.

 

 

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

Н. К. Кривулин, д. ф.-м. н.

О. А. Нев

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

nkk@math.spbu.ru, nevolga@gmail.com

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

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

 

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

[1] Heidergott В., Olsder G.J., van der Woude J. Max-Plus at work. — Princeton: Princeton University Press, 2006.

[2] Маслов В.П., Колокольцев В.Н. Идемпотентный анализ и его применение в оптимальном управлении.—М.:Физматлит. 1994.

[3] Кривулин Н.К. Методы идемпотентной алгебры в задачах мо­делирования и анализа сложных систем. — СПб.: Изд-во С-Петерб. ун-та. 2009.

[4] Olsder G.J., Resing J.A.C., De Vries R.E., Keane M.S., Hooghiemstra G. Discrete event systems with stochastic processing times // IEEE Trans. Automat. Contr. 1990. Vol. 35. No. 3. P. 299-302.

[5] Jean-Marie A. Analytical computation of Lyapunov exponents in stochastic event graphs // Performance Evaluation of Parallel and Distributed Systems. Solution Methods: Proc. 3rd QMIPS Workshop. Amsterdam: CWI Tracts. Vol. 106. 1994. P. 309-341.

[6] Кривулин Н.К. Скорость роста вектора состояний обобщенной линейной стохастической системы с симметричной матрицей // Зап. науч. семин. ПОМИ. 2007. Т. 341. С. 134-141.

[7] Кривулин Н.К. О вычислении скорости роста вектора состоя­ний обобщенной линейной стохастической системы второго по­рядка // Вестн. С.-Петерб. ун-та. Сер. 1. 2008. Вып. 1. С. 38-48.

[8] Кривулин Н.К. Вычисление показателя Ляпунова обобщенных линейных систем с показательным распределением элементов переходной матрицы // Вестн. С.-Петерб. ун-та. Сер. 1. 2009. Вып. 2. С. 37-47.

[9] Кривулин Н.К. Вычисление показателя Ляпунова для одной модели стохастической системы с синхронизацией // Стоха­стическая оптимизация в информатике. 2010. Т. 6. С. 171-183.

[10] Кривулин Н.К. Вычисление средней скорости роста вектора состояний стохастической системы с синхронизацией событий // Вестн. С.-Петерб. ун-та. Сер. 1. 2011. Вып. 1. С. 109-116.

 

 

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

Сопоставление синтаксических элементов в системах контроля версий

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

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

dmit10@gmail.com

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

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

[1] http://en.wikipedia.org/wiki/Subversion.

[2] http://en.wikipedia.org/wiki/Git.

[3] http://en.wikipedia.org/wiki/Mercurial.

[4] Лап S., Heung-Yeung S., Nan-Ning Zh. Stereo matching using belief propagation // IEEE Trans, on Pattern Analysis and Machine Intelligence. 2003. Vol. 25. P. 787-800.

[5] Boykov Y., Veksler O., Zabih R. Markov random fields with efficient approximations // In IEEE conf. on Computer Vision and Pattern Recognition (CVPR). 1998. P. 648-655.

[6]  Samson Ch. Proof of Hammersley-Clifford Theorem. 2008.

[7] Yedidia J.S., Freeman W.T., Weiss Y. Understanding belief propagation and its generalizations // Exploring Artificial Intelligence in the New Millennium. Science & Technology Books. 2003. Chap. 8. P. 239-236.

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

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

 

 

Стохастический метод решения задач классификации и обучения

В. Н. Шац, д. т. н.

Санкт-Петербург

vlnash@mail.ru

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

Ключевые слова: информационная среда, задачи классификации, расшире­ние исходной информации, стохастический алгоритм.

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

[1] Браверман Э. М., Мучник И. Б. Структурные методы обработ­ки эмпирических данных. — М.: Наука. 1983. 496 с.

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

[3] Прикладная статистика: Классификация и снижение размер­ности: Справ, изд. / Под ред. С.А. Айвазяна. — М.: Финансы и статистика. 1989. 607 с.

[4] Материалы "круглого стола". Информационный подход в меж­дисциплинарной перспективе // Вопросы философии. 2010. №2. С. 84-112.

[5] Величковский Б.М. Когнитивнвая наука: Основы психологии познания: в 2 т. — Т.1. — М.: Смысл. 2006. 448 с.

[6] Шац В.Н. О модели воздействия информации на группу // Социология: методология, методы, математическое моделиро­вание. 2010. №30. С. 181-194.

[7] Шац В.Н. Вычислительная модель модуля нервной системы // Сборник научных трудов научно-технической конференции "Нейроинформатика-2011" . Ч. 2. 2011. С. 229-238.

[8] Шац В.Н. Непрерывно ветвящаяся цепь как модель биологи­ческой цепи нейронов // Труды одиннадцатой национальной конференции по искусственному интеллекту с международным участием КИИ-2008. Т. 1. - М.: ЛЕНАНД. 2008. С. 164-170.

[9] Asuncion A., Newman D.J. UCI Machine Learning Repository. — Irvine CA: University of California, School of Information and Computer Science. 2007.

[10] Вапник В.Н., Червоненкис А.Я. Теория распознавания образов (статистические проблемы обучения). — М.: Наука. 1974. 416 с.

 

 

ABSTRACTS

Randomized Algorithms

New Randomized Algorithms in Control and Data Processing

K. S Amelin, O. N. Granichin

Saint Petersburg State University

Oleg_granichin@mail.ru, konstantinamelin@mail.ru

Key words: randomized algorithms, optimization and estimation, control.

Randomization allows one to enrich the observation data and design speedy algorithms significantly reducing the number of operations and annihilating systematic errors (the bias effect of an arbitrary noise). Their accuracy usually weakly depends on the data dimension.

A randomized algorithm is nothing but a procedure where one or more steps are based on a random rule, that is, when using a randomized algorithm, at some stage instead of making a decision ourselves we call on fate to choose for us. But then, a question arises naturally: why should resorting to fate be any wise? Fate is not an expert of anything, all it does is choosing by chance. So, why should randomized be any good? A conscious use of randomized methods demands to question ourselves about this issue, and this paper contains some answers on this question. An exposition of randomized algorithms and their application are given.

Bibliogr.: 86 refs.

 

 

Fast Algorithm for Finding True Number of Clusters in a Large Data Set

M. A. Morozkov

Saint Petersburg State University

mmorozkov@gmail.com

Key words: clustering, randomized algorithms, adaptive control, optimi­zation, machine learning.

One of the most difficult problems in cluster analysis is the identifica­tion of the number of groups in a given data set. In this paper we propose a randomized approach in the rate distortion framework and devise the corresponding randomized algorithm. The fundamental ideas of novel scenario approach are used in order to significantly reduce the computational cost. Having the ability to determine the true number of groups in a data set and perform clustering online, we outline several applications to control systems and decision-making problems that can essentially benefit from the considered algorithm. Simulation results show considerable improvement of the rate of convergence under the guaranteed level of probability.

Bibliogr.: 25 refs.

 

 

Quasirandomized Method for Solving of Linear Equation Systems

S. I. Smirnov

Saint Petersburg State University

q4ality@gmail.com

Key words: system of linear algebraic equations, Monte Carlo method, Quasi-Monte Carlo method, stochastic approximation.

As it is known, finding a root of the equation F (x) = 0 or extrema of the function G (x) from the measurements of F and G corrupted by random noise can be implemented via use of stochastic approximation methods.

Of the great applied interest is the case where the above-mentioned values are calculated by the Monte-Carlo method. In particular, if it is required to solve a large system of the linear algebraic equations, it is possible to reduce computational burden by using randomization or designing unbiased estimates for the sum of squares of the adjustments (we choose к random equations from n, where к <С n). Specifically, Quasi-Monte Carlo (QMC) methods might be very useful in simulations.

In this paper we present stochastic approximation algorithms for solving large systems of linear algebraic equations and discuss the advan­tages of using QMC for these problems.

Bibliogr.: 9 refs.

 

 

Filtering

Software Engineering of Unmanned Aerial Vehicle for Mobil Autonomous Group

K. S Amelin

Saint Petersburg State University

konstantinamelin@mail.ru

Key words: unmanned aerial vehicles, UAV, navigation system, autopilot, actuators, autonomous group of UAV, software engineering.

The control system architecture for an unmanned aerial vehicle (UAV) is considered which guarantees its proper functioning in an autonomous UAV group. The prototype of this newly created UAV is described. Flight optimization approaches are described.

Bibliogr.: 31 refs.

 

 

Non-stationary Optimization with Prediction Step for Object Tracking with Two Cameras

D. S. Krivokon, A. T Vakhitov

Saint Petersburg State University

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

Key words: non-stationary optimization, object tracking, stereo-camera.

The paper presents an application of a non-stationary randomized optimization method with prediction step to the problem of tracking an object from noisy readings of the two calibrated perspective cameras. Over the examples, the algorithm outperforms previously proposed non-stationary randomized optimization. The paper contains both theo­retical justification and simulation.

Bibliogr.: 19 refs.

 

 

Identification of Non-stationary Dynamic Plant by a Method of Invariant Immersing on the Fixed Interval

V. M. Ponyatskiy

KBP, Tula

kbkedr@tula.net, pwmru@rambler.ru

Key words: identification, dynamic plant, parameters, discrepancy, sig­nal, noise, model, reverse time.

A nonlinear method of invariant embedding is used in this paper for identification of non-stationary dynamic plants. With the proposed approach, the initial conditions for the estimated parameters can be refined via use of identification algorithms in reverse time. An inverse time estimation algorithm for the non-stationary parameters of a dyna­mic plant is designed and analyzed.

Bibliogr.: 5 refs.

 

Synthesis of the Interval Kalman Filter on the Basis of the Minimax Approach

V. M. Ponyatskiy

KBP, Tula

kbkedr@tula.net, pwmru@rambler.ru

Key words: dynamic plant, filtering, signal, noise, estimation.

An approach is proposed to interval Kalman filter both in continuous and discrete time. The interval Kalman filter is designed and compared to the conventional Kalman filter. The analysis of the results shows that the minimax filter provides a better accuracy of estimation while retaining the properties of the cojventional Kalman filter.

Bibliogr.: 3 refs.

 

 

Multi-Agent Systems

Multi-agent Technology, Adaptation, Self-organization, Consensus

N. O. Amelina

Saint Petersburg State University

leishe@mail.ru

Key words: multi-agent systems, multi-agent control, self-organization, adaptation, consensus, workload balancing network.

The paper presents a brief introduction to the multi-agent technolo­gy which focuses on the two important fields, namely, multi-agent systems in computer science and multi-agent control in a new control theory. Multi-agent technology is also deeply connected with decentra­lized and parallel computation, network communications and other related areas. The considerations are supplied by examples of self-organization and adaptation in a logistic problem and network workload balancing algorithm.

Bibliogr.: 42 refs.

 

 

Generalized Linear Algorithms for Formation Control

S. E. Parsegov

Institute of Control Sciences of RAS, Moscow

parsegov@ipu.ru

Key words: multi-agent systems, formation control.

In recent years, a new framework for systems to be handled appeared which is based on decentralized cooperative control using simple, identi­cal, cooperating subsystems named agents. Such systems are referred to as multi-agent systems. In this paper, some linear algorithms that extend and generalize the known results for formation control are propos­ed. As the first step, the algorithms of allocation of a group of agents on a segment are considered, stability criteria and convergence analysis results are presented.

Bibliogr.: 8 refs.

 

Discrete Stochastic Systems

Representing Conditions

of Generalized Regular Languages

by Stochastic Automata

V. N. Trubnikov,

M. K. Tchirkov

Saint Petersburg State University

vakh08@mail.ru

Key words: stochastic finite automata, generalized regular languages, representation of generalized languages by automata, synthesis of auto­mata in accordance with a regular expression of language.

The paper presents analysis and substantiation of necessary and sufficient conditions for the representation of generalized regular langua­ges defined over the field of real numbers by stochastic finite automata. A stochastic automaton satisfying these conditions is designed from a regular expression of the generalized language. An example is given.

Bibliogr.: 7 refs.

 

 

Asymptotic Properties of State Vector

in a Generalized Linear Stochastic Dynamical

System with Symmetric Matrix

N. K. Krivulin, O. A. Nev

Saint Petersburg State University

nkk@math.spbu.ru, nevolga@gmail.com

Key words: stochastic dynamical system, Lyapunov exponent, idempotent semiring, convergence in distributions.

The paper examines stochastic dynamical systems described by a linear vector equation with second-order symmetric matrix in an idempotent semi-ring with operations of maximum and addition. It is assumed that the diagonal of the matrix consists of a nonnegative random variable and zero, whereas both off-diagonal elements are equal to a nonnegative constant. A problem of calculating the mean asymptotic growth rate of system state vector (the Lyapunov exponent) is consider­ed. The solution includes change of variables resulting in new random variables that appear to be more suitable for analysis than the random coordinates of the state vector. Furthermore, for the new random variab­les, corresponding sequences of one-dimensional probability distributions are constructed and their convergence is examined. The Lyapunov ex­ponent is calculated as the mean value of the limiting distribution for one of the sequences.

Bibliogr.: 10 refs.

 

Information Systems

Syntax Elements Matching in Version Control Systems

D. V. Pavlenko

Saint Petersburg State University

dmit10@gmail.com

 

The paper presents a formulation of the matching problem for file syntax elements. Solution of this problem facilitates better description of the modifications performed over the stored file contents and efficient solution of the conflict problem.

Bibliogr.: 9 refs.

 

Stochastic Method of Solving Problems of Classification and Training

V. N. Shats

St. Petersburg vlnash@mail.ru

Key words: information environment, classification problem, expansion of initial information, stochastic algorithm.

A stochastic method is proposed for the solution of classification and training problems. A continuous mapping of the set of points represented by objects with noisy data is considered, which generates a matrix that, under certain conditions, retains the properties of the objects in the original matrix. This mapping is implemented as a conti­nuous multivariable function obtained in the information environment theory developed by the author. By varying random parameters of this function, an ensemble of matrices can be obtained. These enrich the initial information and reduce the corresponding problem to statistical evaluation of the deterministic solutions for individual matrices compu­ted through a uniform algorithm.

Bibliogr.: 10 refs.

 

Содержание

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

Амелин К.С, Граничин О.Н. (СПбГУ) Новые рандомизированные
алгоритмы в управлении и обработке данных   .............................................       3

Морозков М.А. (СПбГУ) Быстрый рандомизированный алгоритм
нахождения точного количества кластеров в большом множестве дан­
ных   .................................................................................................................     69

Смирнов С.И. (СПбГУ) Квазирандомизированный метод решения
систем линейных уравнений   .........................................................................     

Фильтрация

Амелин К.С. (СПбГУ) Технология программирования легкого БПЛА
для мобильной автономной группы................................................................     93

Кривоконь Д.С, Вахитов А.Т. (СПбГУ) Нестационарная оптимиза­
ция с шагом предсказания в задаче отслеживания объекта при по­
мощи двух камер   ........................................................................................... 116

Понятский В.М. (ГУП "КБП", Тула) Идентификация нестационар­
ного динамического объекта методом инвариантного погружения на
закрепленном интервале................................................................................... 128

Понятский В.М. (ГУП "КБП", Тула) Синтез интервального фильтра
Калмана на основе минимаксного подхода   .................................................. 142

Мультиагентные системы

Амелина Н.О. (СПбГУ) Мультиагентные технологии, адаптация, са­
моорганизация, достижение консенсуса   ...................................................... 149

Парсегов С.Э. (ИПУ, Москва) Обобщенные линейные алгоритмы
управления формациями   ............................................................................... 186

Дискретные стохастические системы

Трубников В.Н., Чирков М.К. (СПбГУ) Условия представимости
обобщенных регулярных языков стохастическими автоматами..................... 204

Кривулин Н. К., Нев О.А. (СПбГУ) Асимптотические свойства век­
тора состояний обобщенной линейной стохастической системы с сим­
метричной матрицей......................................................................................... 232

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

Павленко Д.В. (СПбГУ) Сопоставление синтаксических элементов в системах
контроля версий   ............................................................................................ 240

Шац В.Н. (СПб) Стохастический метод решения задач классифи­
кации и обучения   ........................................................................................... 257

Abstracts   ............................................................................................................. 269

 


List of abstracts

Randomized Algorithms

Amelin K.S., Granichin O.N. (SPbSU) New randomized algorithms in
control and data processing   ............................................................................. 269

Morozkov M.A. (SPbSU) Fast algorithm for finding true number of
clusters in a large data set   ................................................................................ 270

Smirnov S.I. (SPbSU) A quasirandomized method for solving systems
of linear equations   .......................................................................................... 2T1

Filtering

Amelin K.S. (SPbSU) Software engeneering of unmanned aerial vehicle
for mobile autonomous group   ......................................................................... 2T2

Krivokon D.S., Vakhitov A.T. (SPbSU) Non-stationary optimization
with prediction step for object tracking with two cameras................................... 2T3

Ponyatskiy V.M. (KBP, Tula) Identification of non-stationary dynamic
plants by a method of invariant embedding over a fixed interval........................ 2T4

Ponyatskiy V.M. (KBP, Tula) The minimax approach to the design of
the interval Kalman filter   ................................................................................. 2T5

Multi-Agent Systems

Amelina N.O. (SPbSU) Multi-agent technology, adaptation, self-organi­
zation, consensus   ........................................................................................... 2T6

Parsegov S.E. (ICS R.AS, Moscow) Generalized linear algorithms for
formation control   ............................................................................................ 2T7

Discrete Stochastic Systems

Trubnikov V.N., Tchirkov M.K. (SPbSU) Representability conditions of
generalized regular languages by stochastic automata   ...................................... 2T8

Krivulin N.K., Nev O.A. (SPbSU) Asymptotic properties of state vector
in a generalized linear stochastic dynamical system with symmetric
matrix................................................................................................................. 2T9

Information Systems

Pavlenko D.V. (SPbSU) Syntax element matching in version control
systems.............................................................................................................. 280

Shats V.N. (SPb) A stochastic method for classification and training  .281

 


Научное    издание

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

Том 7 Выпуск 1

Печатается без издательского редактирования

Обложка художника Е. А. Соловьевой Оригинал-макет О. Н. Граничина

Подписано в печать 30.10.11. Формат 60 х 84/1 Бумага офсетная. Печать офсетная. Усл. печ. л. 17,75. Тираж: 100 экз. Заказ №

Издательство СПбГУ. 199004, С.-Петербург, В.О., 6-я линия, 11/21

Тел. (812) 328-96-17; факс (812) 328-44-22

E-mail: editor@unipress.ru

www.unipress.ru

По вопросам реализации обращаться по адресу:

С.-Петербург, В.О., 6-я линия, д. 11/21, к. 21

Телефоны: 328-77-63, 325-31-76

E-mail: post@unipress.ru

Типография Издательства СПбГУ 199061, С.-Петербург, Средний пр., 41