N	Оглавление	Страницы
1	Обзор теории интеллектуального анализа данных на базе нейронных сетей Ерофеева Виктория Александровна	3-17
2	Использование алгоритма типа стохастической аппроксимации для поиска оптимального шага протокола локального голосования при достижении дифференцированного консенсуса в мультиагентной сети со стоимостными ограничениями на топологию Иванский Юрий Владимирович	18-38
3	Метрика для эвристических алгоритмов решения задачи вершинной минимизации автоматов Мельникова Е. А., Тренина М. А.	39-43
4	Эвристические алгоритмы генерации матриц бинарного отношения на состояниях канонических автоматов Софонова Н. В., Дудников В. А.	44-55
5	Вычисление диапазонов выходов линейных систем с внешним возмущением Щербаков Павел Сергеевич	56-64

Обзор теории интеллектуального анализа данных на базе нейронных сетей

Ерофеева В. А., аспирант

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

v.erofeeva@spbu.ru

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

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

их классификация и математическая постановка задачи обучения распознаванию образов.

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

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

[1] Айзерман М. А., Браверман Э. М., Розоноэр Л. И. Метод потенциальных функций в теории обучения машин. – М.: Наука. 1970.

[2] Цыпкин Я. З. Адаптация, обучение и самообучение в автоматических системах // Автоматика и телемеханика. 1966. №1. C. 23–61.

[3] Цыпкин Я. З. Основы теории обучающихся систем. – М.: Наука. 1970.

[4] Якубович В. А. Некоторые общие теоретические принципы построения обучаемых опознающих систем // Вычислительная техника и вопросы программирования. 1965. С. 3–71.

[5] Якубович В. А. Рекуррентные конечносходящиеся алгорифмы решения систем неравенств // ДАН СССР. 1966. Т. 166. №6. С.1308–1312.

[6] Фомин В.Н. Математическая теория обучаемых опознающих систем. – Л.: ЛГУ. 1976.

[7] Abramson N., Braverman D. Learning to Recognize Patterns in a Random Environment // IRE Transactions on Information Theory. 1962. Vol. 8. Issue 5. P. 58–63.

[8] Abramson N., Braverman D., Sebastian G. Pattern Recognition and Machine Learning // IEEE Transactions on Information Theory. 1963. Vol. 9. Issue 4. P. 257–261.

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

[10] Вапник В. Н. Восстановление зависимостей по эмпирическим данным. – М.: Наука. 1979.

[11] Воронцов К. В. Обзор современных исследований по проблеме качества обучения алгоритмов // Таврический вестник информатики и математики. 2004. №1. С. 5–24.

[12] Дюк В. А., Флегонтов А. В., Фомина И. К. Применение технологий интеллектуального анализа данных в естественнонаучных, технических и гуманитарных областях // Известия РГПУ им. А.И. Герцена. 2011. №138. С. 77–84.

[13] Пятецкий-Шапиро Г. Data Mining и перегрузка информацией // Вступительная статья к книге: Анализ данных и процессов / А. А. Барсегян, М. С. Куприянов, И. И. Холод, М. Д. Тесс, С. И. Елизаров. З-е изд. перераб. и доп. – СПб.: БХВ-Петербург. 2009. С. 13.

[14] McCulloch W. S., Pitts W. A logical calculus of the ideas immanent in nervous activity // The bulletin of mathematical biophysics. 1943. Vol. 5. Issue 4. P. 115–133.

[15] Hebb D. O. The Organization of Behavior: A Neuropsychological Theory. – New York:Psychology Press. 1949.

[16] Колмогоров А. Н. О представлении непрерывных функций нескольких переменных в виде суперпозиций непрерывных функций одной переменной и сложения // ДАН СССР. 1957. Т. 114, Вып. 5. С. 953–956.

[17] Арнольд В. И. О представлении непрерывных функций трех переменных суперпозициями непрерывных функций двух переменных // Математический сборник. 1959. Т. 48. №1. С. 3–74.

[18] Hecht-Nielsen R. Kolmogorovs mapping neural network existence theorem // IEEE First Annual International Conference on Neural Networks. San Diego. 1987. Vol. 3. P. 11–13.

[19] Rosenblatt F. The perceptron: a probabilistic model for information storage and organization in the brain // Psychological Review. 1958. Vol. 65. P. 386–408.

[20] Rosenblatt F. Principles of Neurodynamics. – New York:Spartan. 1962.

[21] Widrow B., Hoff M. E. Adaptive switching circuits // WESCON Conference. 1960. Vol. 4. P. 96–104

[22] Steinbuch K. Die lernmatrix // Kybernetik (Biological Cybernetics). 1961. Vol. 1. P. 36–45.

[23] Rosenblatt F. Perceptron simulation experiments // Investigative Reporters and Editors Conference. 1960. Vol. 48. №3. P. 301–309.

[24] Joseph R. G. On predicting perceptron performance // Investigative Reporters and Editors Conference. 1960. №2. P. 71–72.

[25] Глушков В. М. Теория обучения единого класса дискретных перцептронов // Журнал вычислительной математики и физики. 1962. Т. 2. Вып. 2. С. 317–335.

[26] Minsky M., Papert S. Perceptrons. – Massachusetts:MIT Press. 1969.

[27] Kohonen T. Correlation matrix memories // IEEE Transactions on Computers. 1972. Vol. C-21. Issue 4. P. 353–359.

[28] Anderson J. A. A simple neural network generating an interactive memory // Mathematical Biosciences. 1972. Vol.14. P. 197–220.

[29] Grossberg S. Adaptive pattern classification and universal recoding: I. Parallel development and coding of neural feature detectors // Biological Cybernetics. 1976. Vol. 23. P. 121–134.

[30] Kohonen T. Self-organized formation of topologically correct feature maps // Biological Cybernetics. 1982. Vol. 43. P. 59–69.

[31] Kohonen T. The self-organizing map // Neurocomputing. 1998. Vol. 21. P. 1–6.

[32] Hopfield J. J. Neural networks and physical systems with emergent collective computational abilities // Proc. of the National Academy of Science. USA. 1982. Vol. 79. P. 2554–2558.

[33] Fukushima K., Miyake S., and Ito. T. Neocognitron: A neural network model for a mechanism of visual pattern recognition // IEEE Transactions on Systems, Man, and Cybernetics. 1983. Vol. 13. P. 826–834.

[34] Hubel D. H., Wiesel T. N. Receptive fields, binocular interaction and functional architecture in the cat’s visual cortex // Journal of Physiology. 1962. Vol. 160. P. 106–54.

[35] Hopfield J. J. and Tank D. W. Neural computation of decisions in optimization problems // Biological Cybernetics. 1985. Vol.52. P. 141-152.

[36] Rumelhart D., Hinton G., Williams R. Learning representations by backpropagating errors // Nature. 1986. Vol. 323. P. 533–536.

[37] Галушкин А. И. Нейронные сети: основы теории. – М. : Горячая линия- Телеком. 2010.

[38] Granichin O., Volkovich V., Toledano-Kitai D. Randomized Algorithms in Automatic Control and Data Mining. – Berlin, Heidelberg:Springer. 2015.

[39] Измакова О. А. Рандомизированные алгоритмы самообучения для настройки ассоциативных нейронных сетей // Стохастическая оптимизация в информатике. 2005. Т. 1. №1-1. С. 81–102.

[40] Хайкин C. Нейронные сети: полный курс, 2-е издание. – М.: Вильямс. 2008.

[41] Бендерская Е. Н., Никитин К. В. Рекуррентная нейронная сеть как динамическая система и подходы к ее обучению // Научно-технические ведомости Санкт-Петербургского государственного политехнического университета. Информатика. Телекоммуникации. Управление. 2013. №4. С. 29.

[42] Бендерская Е. Н., Граничин О. Н. Использование сложности входного образа в управлении структурной сложностью интеллектуальной системы // 5-я Российская мультиконференция по проблемам управления. Санкт-

Петербург. 2012. C. 276–280.

[43] Angelini L., Carlo F., Marangi C., Pellicoro M., Nardullia M., Stramaglia S. Clustering Data by Inhomogeneous Chaotic Map Lattices // Physical Review Letters. 2000. No. 85. P. 78–102.

[44] Бендерская Е. Н., Толстов А. А. Реализация осцилляторной хаотической нейронной сети с применением технологии NVIDIA CUDA для решения задач кластеризации // Информационно-управляющие системы. 2014. № 4. С. 94–101.

[45] Борисюк Г. Н., Борисюк Р. М., Казанович Я. Б., Лузянина Т. Б., Турова Т. С., Цымбалюк Г. С. Осцилляторные нейронные сети. Математические результаты и приложения // Математическое моделирование. 1992. Т. 4. №1. C. 3–43.

[46] Бендерская Е. Н., Новиков А. В. Применение процессов синхронизации в осцилляторных сетях для решения задач кластеризации // СПИСОК-2013: Материалы всероссийской научной конференции по проблемам информатики. Санкт-Петербург. 2013. С. 129–138.

[47] LeCun Y. et al. Backpropagation Applied to Handwritten Zip Code Recognition // Neural Computation. 1989. Vol. 1. Issue 4. P. 541–551.

[48] Hinton G. E., Osindero S., Teh Y.-W. A fast learning algorithm for deep belief nets // Neural Computation. 2006. Vol. 18. Issue 7. P. 1527–1554.

[49] Schmidhuber J. Deep Learning in Neural Networks: An Overview // Neural Networks. 2015. Vol. 61. P. 85–117.

[50] Mikolov T., Karafiat M., Burget L., Cernocky J., Khudanpur S. Recurrent neural network based language model // 11th Annual Conference of the International Speech Communication Association. Japan. 2010. P. 1045–1048.

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

Иванский Ю. В., аспирант

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

ivanskiy.yuriy@gmail.com

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

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

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

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

[1] Ren W., Beard R. Consensus seeking in multiagent systems under dynamically changing interaction topologies // IEEE Transactions on Automatic Control 2005. Vol. 50 Issue 5. P. 655–661.

[2] Bullo F., Cort´es J., Martine, S. Distributed control of robotic networks: a mathematical approach to motion coordination algorithms. — Princeton University Press. 2009.

[3] Чеботарев П.Ю., Агаев Р.П. Согласование характеристик в многоагентных системах и спектры лапласовских матриц орграфов // Автоматика и телемеханика. 2009. № 3. С. 136–151.

[4] Lewis F.L., Zhang H., Hengster-Movric K., Das A. Cooperative Control of Multi-Agent Systems: Optimal and Adaptive Design Approaches

(Communications and Control Engineering). — Springer. P. 307. 2014.

[5] Granichin O., Skobelev P., Lada A., Mayorov I. and Tsarev A. Comparing adaptive and non-adaptive models of cargo transportation in multiagent system for real time truck scheduling // In: Proc. of the 4th International Conference on Computational Intelligence. Р. 282–285

(Evolutionary Computation Theory and Applications, ECTA’2012, October 5–7, 2012, Barcelona, Spain).

[6] Amelina N., Fradkov A., Jiang Y., and Vergados D.J. Approximate consensus in stochastic networks with application to load balancing // IEEE Transactions on Information Theory. April 2015. Vol. 61. Issue 4. P. 1739–1752.

[7] Granichin O., Amelina N. Simultaneous perturbation stochastic approximation for tracking under Unknown but bounded disturbances

// IEEE Transactions on Automatic Control. Vol. 60. Issue 6. June 2015. P. 1653–1658.

[8] Amelina N., Granichin O., Granichina O., Ivanskiy Y., and Jiang Y. Differentiated consensuses in a stochastic network with priorities // Proc. of 2014 IEEE Multi-conference on Systems and Control. October 8–10. 2014. Antibes/Nice, France. P. 264–269.

[9] Amelina N., Granichin O., Jiang Y., and Granichina O. Differentiated consensuses in decentralized load balancing problem with randomized topology, noise, and delays // Proc. of 53rd IEEE Conference on Decision and Control. December 15–17. 2014. Los Angeles, USA. P. 6969–6974.

[10] Dovrolis C., Ramanathan P. A case for relative differentiated services and the proportional differentiation model // IEEE Network. 1999. Vol. 56. No. 7. P. 3315–3326.

[11] Yuming J., Chen-Khong T., and Chi-Chung K. A probabilistic priority scheduling discipline for multi-service networks // Computer Communications. 2002. Vol. 25. No. 13. P. 1243–1254.

[12] Амелина Н.О. Достижение консенсуса автономной группой беспилотных самолетов // Стохастическая оптимизация в информатике. Т. 6. С. 127–132, 2010.

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

[14] Амелина Н.О. Балансировка загрузки узлов децентрализованной вычислительной сети при неполной информации // Нейрокомпьютеры: разработка, применение. №. 6. 2011. С. 56–63.

[15] Амелина Н.О., Фрадков А.Л. Мультиагентная система для задачи балансировки загрузки сети при неполной информации // Сборник трудов межд. научно-практической конференции “Управление большими системами-2011”. T. 3. 2011. С. 201–209.

[16] Амелина Н.О., Фрадков А.Л. Метод усредненных моделей в задаче достижения консенсуса // Стохастическая оптимизация в информатике. Т. 8. 2012. С. 3–39.

[17] Амелина Н.О. Диспетчеризация сети с переменной топологией при помехах и задержках в измерениях // Вестник СПбГУ. Сер. 1: Математика. Механика. Астрономия. 2012. №. 2. С. 11–5.

[18] Амелин К.С., Амелина Н.О., Граничин О.Н., Корявко А.В. Применение алгоритма локального голосования для достижения консенсуса в децентрализованной сети интеллектуальных агентов // Нейрокомпьютеры: разработка, применение. №. 11. 2012. С. 039–047.

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

[20] Amelina N., Fradkov A., and Amelin K. Approximate consensus in multi-agent stochastic systems with switched topology and noise // Proc. of MSC IEEE 2012. October 3–5. 2012. Dubrovnik. Croatia. P. 445–450.

[21] Amelin K., Amelina N., Granichin O., Granichina O. Multi-agent stochastic systems with switched topology and noise // Proc. of 13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, SNPD 2012. August 8-10. 2012. Kyoto, Japan. P. 438–443.

[22] Амелина Н.О., Васильев В.И., Граничин О.Н., Кияев В.И. Перспективный децентрализованный подход к балансировке загрузки в многоядерных процессорах // В сб. трудов международной суперкомпьютерной конференции “Научный сервис в сети Интернет: поиск новых решений”, г. Новороссийск, 17-22 сентября 2012 г. М: Изд-во Моск. ун-та. С. 345–347.

[23] Амелина Н.О. Консенсусное мультиагентное управление стохастическими системами. дисс. ... канд. физ.-мат. наук. СПбГУ. Санкт-Петербург. 2012.

[24] Амелина Н.О., Амелин К.С., Вергадос Д.Д. Планирование в стохастических беспроводных сетях с ретрансляторами // Стохастическая оптимизация в информатике. Т. 9. С. 17–43. 2013.

[25] Амелина Н.О. Исследование консенсуса в мультиагентных системах в условиях стохастических неопределенностей // Вестник ННГУ. 2013. № 1(3), С. 173–179.

[26] Амелина Н. Применение протокола локального голосования для децентрализованной балансировки загрузки сети с переменной топологией и помехами в измерениях // Вестник СПбГУ. Сер. 1: Математика. Механика. Астрономия. 2013. № 3. С. 12–20.

[27] Amelina N., Granichin O., Kornivetc A. Local voting protocol in decentralized load balancing problem with switched topology, noise, and delays // Proc. of 52st IEEE Conference on Decision and Control. December 10–13. 2013. Firenze, Italy. P. 4613–4618.

[28] Amelin K., Amelina N., Granichin O., Granichina O., Andrievsky B.Randomized algorithm for UAVs group flight optimization // Proc. of 11^th IFAC International Workshop on Adaptation and Learning in Control and Signal Processing. July 3–5. 2013. Caen, France. P. 205–208.

[29] Amelin K., Amelina N., Granichin O., Putov V. Task allocation algorithm for the cooperating group of light autonomous unmanned aerial vehicles // Proc. of 2nd RED-UAS 2013 IFAC Workshop on Research, Education and Development of Unmanned Aerial Systems. November 20–22. 2013. Compiegne, France. P. 152–155.

[30] Chilwan A., Amelina N., Mao Z., Jiang Y., and Vergados D.J. Consensus based report-back protocol for improving the network lifetime in underwater sensor networks // Advances in Communication Networking. — Springer International Publishing. 2014. P. 26–37.

[31] Амелина Н.О., Корнивец А.Д., Иванский Ю.В., Тюшев К.И. Применение консенсусного протокола для балансировки загрузки стохастической децентрализованной сети при передаче данных // В сб. “Труды XII Всероссийского совещания по проблемам управления”. Россия, Москва, ИПУ РАН. 16–19 июня 2014, С. 8902–8911.

[32] Amelina N., Fradkov A. Analysis of nonlinear local voting protocol for stochastic dynamical networks // Proc. of 2014 IEEE Multi-conference on Systems and Control. October 8–10. 2014. Antibes/Nice, France. P. 693–698.

[33] Амелина Н.О., Иванский Ю.В. Задача достижения дифференцированного консенсуса при стоимостных ограничениях // Вестник СПбГУ. Сер. 1: Математика. Механика. Астрономия. 2015. Т. 2(60). Вып. 4. С. 3–14.

[34] Ivanskiy Y., Amelina N., Granichin O., Granichina O., and Jiang Y. Optimal step-size of a local voting protocol for differentiated consensuses achievement in a stochastic network with cost constraints for different priorities // Proc. of the 2015 IEEE Multi-Conference on Systems and Control (MSC 2015). September 21–23. 2015. Sydney, Australia. P. 1367–1372.

[35] Amelina N., Granichin O., Granichina O., Ivanskiy Y., and Jiang Y. Optimal step-size of a local voting protocol for differentiated consensuses achievement in a stochastic network with priorities // Proc. of the 14th European Control Conference 2015. Linz, Austria. July 15–17. 2015. P. 628–633.

[36] Amelina N., Erofeeva V., Granichin O., and Malkovskii N. Simultaneous perturbation stochastic approximation in decentralized load balancing problem with unknown but bounded disturbances // Proc. of the IFAC Conference on Modelling, Identification and Control of Nonlinear Systems (MICNON’15). Saint Petersburg, Russia. June 24–26. 2015. P. 946–951.

[37] Amelina N., Granichin O., Granichina O., Ivanskiy Y., and Jiang Y. Local voting protocol for differentiated consensuses in a stochastic network with priorities // Proc. of the IFAC Conference on Modelling, Identification and Control of Nonlinear Systems (MICNON’15). Saint Petersburg, Russia, June 24–26. 2015. P. 964–969.

[38] Amelina N., Fradkov A. Approximate consensus in multi-agent nonlinear stochastic systems // Proc. of 13th European Control Conference (ECC 2014). June 24–27. Strasbourg, France. P. 2833–2838.

[39] Robbins H., Monro S. A stochastic approximation method // Ann. Math. Statist. 1951. Vol. 22. P. 400–407.

[40] Kiefer J., Wolfowitz J. Statistical estimation on the maximum of a regression function // Ann. Math. Statist. 1952. Vol. 23. P. 462–466.

[41] Blum J.R. Multidimensional stochastic appoximation // Ann. Math. Statist. 1954. Vol. 9. P. 737–744.

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

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

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

[45] Polyak В.Т., Tsybakov A.В. On stochastic approximation with arbitrary noise (the KW case) / In: Topics in Nonparametric Estimation. Khasminskii R.Z. eds. // Advances in Soviet Math., Amer. Math. Soc. Providence. 1992. No. 12. P. 107–113.

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

[47] Spall J.C. Multivariate stochastic approximation using a simultaneous perturbation gradient approximation // IEEE Trans. Automat. Control. 1992. Vol. 37. No. 3. P. 332–341.

[48] Spall J.C. A one-measurement form of simultaneous perturbation stochastic approximation // Automatica. 1997. Vol. 33. P. 109–112.

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

[50] Borkar V.S. Stochastic Approximation. A Dynamical Systems Viewpoint. Cambridge University Press. 2008.

[51] Granichin O., Gurevich L., Vakhitov A. Discrete-time minimum tracking based on stochastic approximation algorithm with randomized differences // 48^th Conf. Decision Control. Shanghai, China. 2009. P. 5763–5767.

[52] Tsitsiklis J., Bertsekas D., Athans M. Distributed asynchronous deterministic and stochastic gradient optimization algorithms // IEEE Trans. Automat. Control. 1986. Vol. 31. No. 9. P. 803–812.

[53] Granichin O.N. Linear regression and filtering under nonstandard assumptions (Arbitrary noise) // IEEE Transactions on Automatic Control, Vol. 49, Oct. 2004, P. 1830–1835.

[54] Granichin O., Volkovich V., Toledano-Kitai D. Randomized Algorithms in Automatic Control and Data Mining.—Springer-Verlag: Heidelberg New York Dordrecht London. 2015.

Метрика для эвристических алгоритмов решения задачи вершинной минимизации автоматов

Мельникова Е. А., к. ф.-м. н.

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

Тренина М. А., старший преподаватель

Тольяттинский государственный университет

ya.e.melnikova@yandex.ru, trenina.m.a@yandex.ru

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

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

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

[1] Мельникова Е.А. Применение алгоритмов кластеризации подзадач для вершинной минимизации недетерминированных конечных автоматов // Вектор науки ТГУ. 2012. № 4. С. 86–89

[2] Мельникова Е.А., Тренина М.А. Метрика для кластеризации подзадач в задаче минимизации недетерминированных автоматов // Материалы 3-й научно-практической internet-конференции "Междисциплинарные исследования в области математического моделирования и информатики ТГУ, 2014. С. 61–62.

[3] Мельников Б.Ф. Мультиэвристический подход к задачам дискретной оптимизации // Кибернетика и системный анализ (НАН Украины), 2006. № 3. C. 32–42.

[4] Мельников Б.Ф., Мельникова Е.А. Некоторые эвристические алгоритмы в задаче вершинной минимизации недетерминированных конечных автоматов // Стохастическая оптимизация в информатике. 2013. Т. 9. № 2. С. 73–87.

[5] Мельников Б.Ф., Мельникова Е.А. Кластеризация ситуаций в алгоритмах реального времени для задач дискретной оптимизации // “Системы управления и информационные технологии”. 2007. № 2. С. 16–19.

[6] Melnikov B., Radionov A., Gumayunov V. Some special heuristics for discrete optimization problems // Proc. of 8th International Conference on Enterprise Information Systems, ICEIS-2006. P. 360–364.

[7] Колмогоров А. Элементы теории функций и функционального анализа . – М.: ФИЗМАТЛИТ. 2004. 570 с.

Эвристические алгоритмы генерации матриц бинарного отношения на состояниях канонических автоматов

Софонова Н. В., аспирант

Тольяттинский государственный университет

natashamilkova@yandex.ru

Дудников В. А., студент

Луганский государственный университет им. В. Даля

dudnikov.vladislav@gmail.com

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

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

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

[1] Харари Ф., Палмер Э. Перечисление графов. – М.: Мир. 1977.

[2] Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. – М.: Мир. 1982.

[3] Hromkovihc J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer. 2004.

[4] Klarreich E. Landmark Algorithm Breaks 30-Year Impasse. – URL: http://www.wired.com/2015/12/landmark-algorithm-breaks-30-yearimpasse/?mbid=social_fb

[5] Долгов В. Н., Софонова Н. В. О дугах конечных автоматов для описания алгоритмов построения Ватерлоо-подобных автоматов // Стохастическая оптимизация в информатике. 2015. Т. 11. No. 1. C. 65–76.

[6] Kameda T., Weiner P. On the state minimization of nondeterministic finite automata // IEEE Trans. on Comp. 1970. Vol. 19. No. 7. P. 617–627.

[7] Долгов В. Н., Мельников Б. Ф. Об алгоритмах автоматического построения Ватерлоо-подобных конечных автоматов на основе полных автоматов // Эвристические алгоритмы и распределенные вычисления. 2014. Vol 1. No. 4. C. 24–45.

[8] Melnikov B., Melnikova A. Some properties of the basis finite automaton // The Korean Journal of Computational and Applied Mathematics. 2002. Vol. 9. №. 1. P. 131–150.

[9] Melnikov B. Once more on the edge-minimization of nondeterministic finite automata and the connected problems // Fundamenta Informaticae. 2010. Vol 104. No. 3. P. 267–283.

[10] Melnikov B., Melnikova A. Some more on the basis finite automaton // Acta Informatica, Univ. Sapientiae. 2013. Vol. 5. №. 2 P. 227–244.

[11] Мельников Б. Ф. Недетерминированные конечные автоматы. — Тольятти: Изд-во ТГУ. 2009.

[12] Lombardy S., Sakarovitch J. The universal automaton // Logic and Automata. Amsterdam University Press. 2008. P. 457–504.

[13] Dedekind R. ¨Uber Zerlegungen von Zahlen durch ihre grosten gemeinsamen Teiler // Gesammelte Werke 2. Braunschweig. 1897. P. 103Џ148.

[14] Gross J. L., Yellen J., Zhang P. (Eds.) Handbook of Graph Theory // Discrete Mathematics and Its Applications. Vol. 25. 2003.

Вычисление диапазонов выходов линейных систем с внешним возмущением

Щербаков П. С., д. ф.-м. н.

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

cavour118@mail.ru

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

Ключевые слова: Линейные системы, внешние возмущения, множество достижимости.

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

[1] Bertsekas D.P., Rhodes I.B., Recursive state estimation for a set-membership description of uncertainty // IEEE Transactions on Automatic Control, 1971, no. 16, pp. 117-Џ128.

[2] Schweppe F.C., Uncertain Dynamic Systems, New Jersey: Prentice-Hall, 1973.

[3] Blanchini F., Miani S., Set-Theoretic Methods in Control, Systems & Control: Foundations & Applications, Boston: Birkhauser, 2008.

[4] Granichin O., Volkovich V., Toledano-Kitai D., Randomized Algorithms in Automatic Control and Data Mining, Intelligence Systems Reference Library, vol. 67, Heidelberg: Springer, 2015.

[5] Поляк Б.Т., Хлебников М.В., Щербаков П.С., Управление линейнымисистемами при внешних возмущениях (техника линейных матричных неравенств), Москва: ЛЕНАНД, 2014.

[6] Черноусько Ф.Л., Оценивание фазового состояния динамических систем, Москва: Наука, 1988.

[7] Kurzhanskii A.B., Valyi I., Ellipsoidal Calculus for Estimation and Control, Basel: Birkhauser, 1997.

[8] Boyd S., El Ghaoui L., Ferron E., Balakrishnan V., Linear Matrix Inequalities in System and Control Theory, Philadelphia: SIAM, 1994.

[9] Venkatesh S., Dahleh M., Does star norm capture l1 norm? // In: Proc. American Control Conference, Seattle, USA, 1995, pp. 944–945.

[10] Alamo T., Bravo J.M., Camacho E.F., Guaranteed state estimation by zonotopes // Automatica, 2005, 41:6, pp. 1035-Џ1043.

[11] Dabbene F., Henrion D., Set approximation via minimum-volume polynomial sublevel sets // In: Proc. European Control Conference, Zurich, Switzerland, 2013, pp. 1114–1119.

[12] Lasserre J.B., Level sets and non Gaussian integrals of positively homogeneous functions, arXiv:1110.6632 [math.OC] (Rapport LAAS n. 11595), October 2011.

[13] Tempo R., Calafiore G., Dabbene F., Randomized Algorithms for Analysis and Control of Uncertain Systems with Applications, 2nd Edition, London: Springer-Verlag, 2013.

[14] Dabbene F., Henrion D., Lagoa C., Shcherbakov P., Randomized approximations of the image set of nonlinear discrete-time systems with applications to filtering // In: Proc. 8th IFAC Symposium on Robust Control Design, Bratislava, Slovak Republic, 2015, pp. 37–42.