e:\family\Oleg\TexDoc\sb10_1\sb10

УДК 519.712 ВКК 32.811.7

С82

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

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

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

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

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

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

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

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

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

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

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

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

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

ISSN 1992-2922

Издание выпускается ежегодно (том 1, ненумерованный, вышел в 2005 г., тома (вып.) 2—9 — в 2006—13 гг.) и содержит научные работы по стохастической оптимизации, особо выделяя приложения в информатике. Первый выпуск десятого тома составлен из поступивших в редколлегию рукописей и материалов одноименной регулярной серии семинаров для студентов, аспирантов и научных работников, проводившихся в 2014 г. на математико-механическом факультете С.-Петербургского университета под руководством профессора кафедры системного программирования О. Н. Граничина. Выпуск опубликован при поддержке гранта РФФИ №13-07-00250-а.

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

ББК 32.811.7

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

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

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

helen.bend@gmail.com

Рецензия на новую книгу, посвященную концепции рандомизированных алгоритмов.

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

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

[1] Granichin О., Volkovich V., Toledano-Kitai D. Randomized Algorithms in Automatic Control and Data Mining. Book Series: Computational Intelligence and Complexity. Vol. 67. — Springer-Verlag: Heidelberg. 2014. 251 p.

Дифференцированный консенсус в стохастической сети с приоритетами

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

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

ivanskiy.yuriy@gmail.com

Работа выполнена при поддержке Минобрнауки России (УИН RFMEFI60414X0035) и при частичной поддержке РФФИ

(проект № 13-07-00250-а)

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

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

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

[1] Ren W., Beard R. W., and Atkins E.M. Information consensus in multivehicle cooperative control // Control Systems, IEEE. 2007. Vol. 27. No. 2. P. 71-82

[2] Ren W. and Beard R. Distributed consensus in multi-vehicle cooperative control: theory and applications — Springer. 2007.

[3] Bullo F., Cortes J., and Martine, S. Distributed control of robotic networks: a mathematical approach to motion coordination algorithms. — Princeton University Press. 2009.

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

[5] Amelina N., Granichin О., and Kornivetc A. Local Voting Protocol in Decentralized Load Balancing Problem with Switched Topology, Noise, and Delays // Proc. of 52nd IEEE Conference on Decision and Control (CDC 2013). 2013. P. 4613-4618.

[6] Amelin K., Amelina N., Granichin O., and Putov V. V. Task Allocation Algorithm for the Cooperating Group of Light Autonomous Unmanned Aerial Vehicles // IFAC Proceedings Volumes (IFAC-PapersOnline) 2 (PART 1). 2013. P 152-155.

[7] Комаров С.Н., Терехов А.Н., Граничина О.А. Интегрированно-распределенная автоматизированная информационная система для крупного научно-образовательного учреждения // Вестник Санкт-Петербургского университета. Серия 10: Прикладная математика. Информатика. Процессы управления. 2008. №1. С. 87-94.

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

[9] Amelin К., Amelina N., Granichin О., and Granichina О. Multi-Agent Stochastic Systems with Switched Topology and Noise // Proceedings - 13th ACIS International Conference on Software Engineering, Artificial Intelligence, Networking, and Parallel/Distributed Computing, SNPD 2012. С 438-443.

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

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

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

[13] Amelina Н., Granichin О., and Jiang Y. Differentiated Consensuses in Decentralized Load Balancing Problem with Randomized Topology, Noise, and Delays // IEEE Conference on Decision and Control (CDC 2014). 2014. P. 4613-4618

[14] Qin J. and Yu C. Group consensus of multiple integrator agents under general topology // Decision and Control (CDC), 2013 IEEE 52nd Annual Conference on. 2013. P. 2752-2757.

[15] Yu J. and Wang L. Group consensus in multi-agent systems with switching topologies and communication delays // Systems & Control Letters. 2010. Vol. 59. Is. 6. P. 340-348.

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

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

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

[19] Dovrolis С. and Ramanathan P. A case for relative differentiated services and the proportional differentiation model // IEEE Network. 1999. Vol. 56. No. 7. P. 3315-3326.

[20] Dovrolis C, Stiliadis D., and Ramanathan P. Proportional Differentiated Services: Delay Differentiation and Packet Scheduling // IEEE/ACM Transactions on Networking. 2002. Vol. 10. No. 1 P. 12-26.

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

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

[23] Lewis F.L., Zhang И., Hengster-Movric, К., and Das, A. Cooperative Control of Multi-Agent Systems: Optimal and Adaptive Design Approaches (Communications and Control Engineering). — Springer. P. 307. 2014.

[24] Поляк Б. Т. Введение в оптимизацию. — М.: Наука. Гл. ред. физ.-мат. лит.-ры. С. 384. 1983.

[25] Amelina N., Granichin О., Granichina О., 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.

[26] Granichin O., Volkovich Z. (V.), and Toledano-Kitai D. Randomized Algorithms in Automatic Control and Data Mining. — Springer. 2014. 251 p.

Анализ алгоритмов параллельного хеширования

Р. И. Кучумов, студент

А. В. Соколов, профессор, д.ф.-м.н.

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

ИПМИ КарНЦ РАН

kuchumovri@gmail.com, avs@krc.karelia.ru

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

Ключевые слова: Хеш-таблица, хеширование кукушки, Hopscotch hashing, параллельные вычисления.

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

[1] Herlihy M., Shavit N. The Art of Multiprocessor Programming. -Burlington, USA: Morgan Kaufmann Publishers. 2008.

[2] Fan В., Andersen D. G., Kaminsky M. МетСЗ: Compact and Concurrent MemCache with Dumber Caching and Smarter Hashing. - Pittsburgh, USA. 2013.

[3] Herlihy M., Shavit N., Tzafrir M. Hopscotch Hashing -Providence, USA 2008.

[4] Pagh R., Rodler F.F. Cuckoo Hashing - Aarhus, Denmark: 2004.

[5] Alcantara D.A.F. Efficient Hash Tables on the GPU - California, USA: 2011.

[6] MurmurHash3 https://code.google.eom/p/smhasher/wiki/ MurmurHash3 - Дата обращения: 29.09.2014.

Модель балансировки загрузки в вычислительной сети с использованием задачи параметрического потока

Н. В. Мальковский, аспирант

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

malkovskynv@gmail.com

Работа выполнена при поддержке Минобрнауки России (УИН RFMEFI60414X0035) и при частичной поддержке РФФИ

(проект № 13-07-00250-а)

В статье рассматривается модель вычислительной сети с известными величинами производительности узлов и пропускных способностей каналов связи. Для этой модели решается задача минимизации времени обработки некоторого пакета заданий с произвольным начальным распределением подзадач. Условия оптимальности (по времени выполнения последнего задания) перераспределения загрузки выражаются через специальный вид задачи параметрического максимального потока (англ. parametric maximum flow, parametric flow problem, PFP), решение которой можно получить за время работы одного запуска любого из алгоритмов решения задачи максимального потока вида preflow-push. Для данного подхода приведены обоснования устойчивости и работоспособности при наличии неточностей в измерениях величин пропускных способностей / производительности / начального распределения и задержек коммуникации.

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

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

[1] Kameda H. et al. Optimal load balancing in distributed computer systems. - Springer Publishing Company, Incorporated, 2011.

[2] Alakeel A.M. A guide to dynamic load balancing in distributed computer systems // International Journal of Computer Science and Information Security. 2010. T. 10. No. 6. P. 153-160.

[3] Doddini Probhuling L. Load balancing algorithms in cloud computing // International Journal of Advanced Computer and Mathematical Sciences. 2013. T. 2. P. 4.

[4] Tantawi A.N., Towsley D. Optimal static load balancing in distributed computer systems // Journal of the ACM (JACM). 1985. T. 32. No. 2. P. 445-465.

[5] Kim C, Kameda H. An algorithm for optimal static load balancing in distributed computer systems // IEEE Transactions on Computers. 1992. T. 41. No. 3. P. 381-384.

[6] Kim C, Kameda H. Optimal static load balancing of multi-class jobs in a distributed computer system // In: Proceedings of the 10th International Conference on Distributed Computing Systems, May 1990, P. 562-569.

[7] Ni L.M., Hwang K. Optimal load balancing in a multiple processor system with many job classes // Software Engineering, IEEE Transactions on. 1985. No. 5. P. 491-496.

[8] Grosu D., Chronopoulos A. T. Noncooperative load balancing in distributed systems // Journal of Parallel and Distributed Computing. 2005. T. 65. No. 9. P. 1022-1034.

[9] Grosu D., Chronopoulos А. Т., Leung M.Y. Load balancing in distributed systems: An approach using cooperative games // Parallel and Distributed Processing Symposium, IEEE Computer Society, 2001. P. 196.

[10] Altman E., Kameda H., Hosokawa Y. Nash equilibria in load balancing in distributed computer systems // International Game Theory Review. 2002. T. 4. No. 02. P. 91-100.

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

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

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

[14] Dantzig G. В. et al. The generalized simplex method for minimizing a linear form under linear inequality restraints //Pacific Journal of Mathematics. 1955. T. 5. No. 2. P. 183-195.

[15] Nesterov Y., Nemirovskii A., Ye Y. Interior-point polynomial algorithms in convex programming. Philadelphia : Society for Industrial and Applied Mathematics, 1994. T. 13.

[16] Ford L.R., Fulkerson D.R. Maximal flow through a network // Canadian journal of Mathematics. 1956. T. 8. No. 3. P. 399-404.

[17] Ahuja R.K. et al. Applications of network optimization // In: Handbooks in Operations Research and Management Science. 1995. T. 7. P. 1-83.

[18] Goldberg A. V., Tarjan R.E. A new approach to the maximum-flow problem // Journal of the ACM (JACM). 1988. T. 35. No. 4. P. 921-940.

[19] Карзанов А. В. Нахождение максимального потока в сети методом предпотоков //ДАН СССР. 1974. Т. 215. № 1. С. 49-52.

[20] Gallo G., Grigoriadis M.D., Tarjan R.E. A fast parametric maximum flow algorithm and applications // SIAM Journal on Computing. 1989. T. 18. No. 1. P. 30-55.

[21] Gusfield D. On scheduling transmissions in a network, Tech. Report YALEU DCS TR 481, Department of Computer Science, Yale University, New Haven, CT, 1986.

[22] Itai A., Rodeh M. Scheduling transmissions in a network // Journal of Algorithms. 1985. T. 6. No. 3. P. 409-429.

[23] Ford L.R., Fulkerson D.R. Flows in Networks. Princeton University Press, Princeton, NJ. 1962.

[24] Goldberg A. V. An efficient implementation of a scaling minimum-cost flow algorithm // Journal of Algorithms. 1997. T. 22. No. 1. P. 1-29.

[25] Orlin J.B. A faster strongly polynomial minimum cost flow algorithm // Operations Research. 1993. T. 41. No. 2. P. 338-350.

[26] Goldberg A.V., Tarjan R.E. Solving minimum-cost flow problems by successive approximation // In: Proceedings of the nineteenth annual ACM symposium on Theory of computing. ACM, 1987. P. 7-18.

[27] Edmonds J., Karp R.M. Theoretical improvements in algorithmic efficiency for network flow problems // Journal of the ACM (JACM). 1972. V. 19. No. 2. P. 248-264.

[28] Granichin O.N., Amelina N.O. Simultaneous perturbation stochastic approximation for tracking under unknown but bounded disturbances // IEEE Transactions on Automatic Control. 2014. T. P. 99.

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

[30] Calafiore G. С, Campi M.C. The scenario approach to robust control design //Automatic Control, IEEE Transactions on. 2006. T. 51. No. 5. P. 742-753.

Применение проблемно-ориентированных метрик в геометрических алгоритмах решения псевдогеометрической версии задачи коммивояжера

С. Б. Макаркин, аспирант

Б. Ф. Мельников, д. ф.-м. н.

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

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

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

s.makarkin@gmail.com, bormel@rambler.ru, trenina.m.a@gmail.com

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

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

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

[1] Макаркин С, Мельников Б. Геометрические методы решения псевдогеометрической версии задачи коммивояжера // Стохастическая оптимизация в информатике. 2013. Т. 9. № 2. С. 54-72.

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

[3] Громкович Ю. Теоретическая информатика. Введение в теорию автоматов, теорию вычислимости, теорию сложности, теорию алгоритмов, рандомизацию, теорию связи и криптографию. - Пер. с нем. - СПб.: Изд-во БХВ-Петербург. 2010. 326 с.

[4] Hromkovic J. Algorithmics for Hard Problems. Introduction to Combinatorial Optimization, Randomization, Approximation, and Heuristics. Springer. 2003. 538 p.

[5] Melnikov B. Multiheuristic approach to discrete optimization problems // Cybernetics and Systems Analysis. 2006. Vol. 42. No. 3. P. 335-341.

[6] Melnikov В., 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] Мельников В., Романов Н. Еще раз об эвристиках для задачи коммивояжера // Стохастическая оптимизация в информатике. 2013. Т. 9. № 2. С. 54-72.

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

Моделирование методом Монте-Карло динамики атомарных процессов при отжиге нанопористого кремния

Ю. С. Нагорное, к. ф.-м. н.

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

Nagornovl01.Yuri@gmail.com

В работе приведены результаты моделирования методом Монте-Карло динамики атомарных процессов в нанопористом кремнии и их интерпретация с точки зрения термодинамики плавления поверхностного слоя квантовых нитей. Как показали результаты моделирования и термодинамический расчет процесс отжига прямоугольных пор можно представить следующим образом. Вначале поверхностная энергия определяется только геометрическими характеристиками пор, которые соответствуют симметрии направлений (НО) и (100). В процессе отжига происходит плавление поверхностного слоя так, что поверхностная энергия стремится к минимуму. В предположении, что заполнение микроканалов происходит за счет поверхностной энергии самих каналов, принятые приближения позволили объяснить формирование полостей в зависимости от глубины канала. Как было показано в расчетах, при глубоких порах термодинамической системе не хватает поверхностной энергии, чтобы принять минимальное значение, в результате происходит остановка процесса трансформации поры, при значениях глубины 22 nm и более. При глубине поры 47 nm происходит соответственно разделение канала на две полости, поскольку их объединение требует дополнительной энергии.

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

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

[1] Bisi О., Ossicini S., Pavesi L. Porous silicon: a quantum sponge structure for silicon based optoelectronics // Surface Science Reports. 2000. Vol. 38. P. 1-126.

[2] Болотов В.В., Росликов В.Е., Курдюкова Е.А. и др. Исследование электрофизических и газочувствительных свойств нано-композита por-Si/SnOx // Физика и техника полупроводников. 2012. Т. 46. №1. С. 109-112.

[3] Жарова Ю.А., Федулова Г.В., Астрова Е.В. и др. Технология получения гетеропереходов в решетке двумерного фотонного кристалла на основе макропористого кремния // Физика и техника полупроводников. 2011. Т. 45. № 8. С. 1136-1143.

[4] Гречников А.А., Алимпиев С.С, Никифоров СМ., Симанов-ский Я.О. Способ формирования эмиттера ионов для лазерной десорбции-ионизации химических соединений. Патент №2426191 С1 от 26.05.2010г.

[5] Костишко Б.М., Золотое А.В., Нагорное Ю.С. Моделирование деградации рельефа нанопористого кремния в процессе отжига в неоднородном температурном поле // Физика и техника полупроводников. 2009. Т. 43. №3. С. 372-375.

[6] Костишко Б.М., Золотое А.В., Нагорное Ю.С. Роль диффузии в кластерообразовании и процессе зарастания пор в мелкопористом кремнии // Тезисы докладов II Международной конференции молодых ученых и студентов 'Актуальные проблемы современной науки'. Естественные науки. Часть 1. Самара. 2001. С. 93.

[7] Kostishko B.M., Zolotov A.V., Atazhanov Sh.R. Comparative Simulation of Annealing of Porous Silicon Substrate of Simple Cubic and Diamond-Like Lattice Structure // Physics of low-dimensional structures. 2004. №3/4. P. 1-8.

[8] Золотов А.В. Моделирование процессов термического отжига и высокотемпературной карбонизации пористого кремния. Диссертация на соискание степени кандидата физико-математических наук по специальности 01.04.10 - физика полупроводников. Ульяновск. УлГУ. 2007 г. 139 с.

[9] Kersulis S., Mitin V. Molecular beam epitaxial growth of Si (001): Monte Carlo study // Semicond. Sci. Technol. 1995. Vol. 10. P.653-659.

[10] Двуреченский А.В., Зиновьев В.А., Марков В.А. Механизм структурных изменений поверхности Si(lll) при импульсном воздействии низкоэнергетическими ионами в процессе эпитак-сии из молекулярного пучка // Журнал экспериментальной и теоретической физики. 1998. Т. 114. № 12. С. 2055-2060.

[11] Зверев А.В., Неизвестный И.Г., Шварц Н.Л., Яновицкая З.Ш. Моделирование процессов эпитаксии, сублимации и отжига в трехмерном приповерхностном слое кремния // Физика и техника полупроводников. 2001. Т. 35. № 9. С. 1067-1074.

[12] Лап W., Kaiming Zh., Xide X. Pair potentials for C-C, Si-Si and Si-C from inversion of the cohesive energy // J. Phys.: Condens. Matter. 1994. №6. P. 989-996.

[13] Levi A.C., Kotra M. Theory and simulation of Crystal growth // J. Phys.: Condens. Matter 1997. Vol. 9. P. 299-344.

[14] Агафонова Е.А., Мартышов М.Н., Форш П.А. и др. Влияние термического окисления на перенос носителей заряда в нано-структурированном кремнии // Физика и техника полупроводников. 2010. Т. 44. № 3. С. 367-371.

[15] Жигунов Д.М., Швыдун И.В., Емельянов А.В., Тимошенко В.Ю., Кашкаров П.К., Семиногов В.Н. Фотолюминесцентное исследование структурной эволюции аморфных и кристаллических нанокластеров кремния при термическом отжиге слоев субоксида кремния различной стехиометрии // Физика и техника полупроводников. 2012. Т. 46. №3. С. 369-375.

[16] Mahmoudia Be., Gabouzea N. Haddadib M. et al. The effect of annealing on the sensing properties of porous silicon gas sensor: Use of screen-printed contacts // Sensors and Actuators B: Chemical. 2007. Vol. 123. № 2. P.680-684.

[17] Громов Д.Г., Гаврилов С.А. Проявление гетерогенного механизма при плавлении малоразмерных систем // Физика твердого тела. 2009. Т. 51. №10. С. 2012-2021.

[18] Гафнер Ю.А., Гафнер С.Л., Зимулин И.С, Редель Л.В., Самсонов В.М. Возможные механизмы роста теплоемкости в нано-структурированных металлах // Физика твердого тела. 2013. Т. 55. №10. С. 2026-2032.

[19] Yang С.С, Li G., Jiang Q. Effect of pressure on melting temperature of silicon // J. Phys.: Condens. Matter. 2003. Vol. 15. P. 4961-4965.

[20] Ott N., Nerding M. Evolution of the microstructure during annealing of porous silicon multilayers // J. Appl. Phys. 2004. Vol. 95. №2. P. 497-503.

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

[1] Tempo R., Calafiore G., Dabbene F. Randomized Algorithms for Analysis and Control of Uncertain Systems: with Applications. Springer, 2013.

[2] Handbook of Global Optimization, Khiwer, Vol. 1, 1995, (R. Horst and P. Pardalos, eds.), Vol. 2, 2002 (P.M. Pardalos and H.E. Romeijn, eds.).

[3] Diaconis P. The Markov chain Monte Carlo revolution // Bull. Amer. Math. Soc. 46, 2, 179-205, 2009.

[4] Dabbene F., Shcherbakov P., Polyak B.T. A randomized cutting plane method with probabilistic geometric convergence // SIAM J. Optimiz. 20(6), 3185-3207, 2010.

[5] Polyak B.T., Shcherbakov P.S. Random spherical uncertainty in estimation and robustness // IEEE Transactions on Automatic Control. 45(11), 2145-2150, 2000.

[6] K. Deb, Multiobjective optimization // In: E. K. Burke and G. Kendall, eds, Search Methodologies: Introductory Tutorials in Optimization and Decision Support Techniques, Springer Science+Business Media, New York, 2014, pp. 444-463.

[7] Polyak В., Shcherbakov P., Khlebnikov M. Quadratic image of a ball: Towards efficient description of the boundary // In: Proc. Int. Conf. Syst. Theory, Control, Computing (ICSTCC 2014), Oct. 2014, Sinaia, Romania. PP. 105-110.

[8] Уилкс С. Математическая статистика. М.: Наука. 1967.

Матричные методы построения минимальных форм конечно-нестационарных максиминных нечетких автоматов

А. Ю. Пономарева, к. ф.-м. н.,

Р. В. Строилов,

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

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

a_ponomareva@mail.ru

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

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

Работа выполнена при поддержке гранта РФФИ 13-01-00538-а. ²© А. Ю. Пономарева, Р. В. Строилов, М. К. Чирков, 2014

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

[1] Kandel A., Lee S.C. Fuzzy Switching and Automata: Theory and Applications. Crane Russak, New York, 1979. 303 p.

[2] Пономарева А.Ю., Чирков М.К. Оптимизация обобщенных нечетких автоматов // Математические модели. Теория и приложения. Вып. 11. СПб.: ВВМ. 2010. С. 148-168.

[3] Пономарева А.Ю., Чирков М.К. Оптимальные формы задания конечно-нестационарных автоматных моделей // Вестн. С.-Петербургского ун-та. Сер. 1. 2004. Вып. 1 (№1). С. 33-42.

[4] Пономарева А.Ю., Строилов Р.В. Приведенные формы конечно-нестационарных нечетких автоматов // Математические модели. Теория и приложения. Вып. 12. СПб.: ВВМ. 2011. С. 150-166.

[5] Пономарева А.Ю., Чирков М.К. Матричные методы построения приведенных форм обобщенных конечно-нестационарных автоматов // Математические модели. Теория и приложения. Вып. 3. СПб.: НИИХ СПбГУ. 2003. С. 49-66.

Способы повышения устойчивости оптико-электронной системы с использованием алгоритмов фильтрации Калмана

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

ЗАО "Конструкторское бюро приборостроения имени академика

А.Г. Шипунова", Тула

kbkedr@tula.net, pwmru@rambler.ru

Рассмотрены возможности использования фильтра Калмана для повышения качества работы оптико-электронной системы при сопровождении малоконтрастных объектов. Создана математическая модель фильтра и проведены испытания.

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

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

[1] Ярлыков М.С. Статистическая теория радионавигации. - М. Радио и связь, 1985. - 344 с.

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

[3] Понятский В.М., Петрушин В. В. Повышение динамической точности и помехоустойчивости в системах телеуправления // Изв. ТулГУ. Сер. "Проблемы проектирования и производства систем и комплексов". - Тула: ТулГУ, 2003, Вып. 6. С. 333-335.

[4] Понятский В.М. Проектирование фильтра Калмана для системы управления летательным аппаратом // Юбилейная научно-техническая конференция "Авиационные системы в XXI веке" (11-13 апреля 2006 г.) - М.:ГосНИИАС, 2006. Том 2. С. 172-176.

[5] Понятский В.М. Исследование способов реализации адаптивной системы управления с фильтром Калмана // Стохастическая оптимизация в информатике. 2008. Вып.4. С. 186-200.

[6] Понятский В.М. Способ повышения помехоустойчивости ро-бототехнической системы // Труды XII межд. семинара "Супервычисления и математическое моделирование" (11-15 окт. 2010 г.) - г. Саров ФГУП "РФЯЦ-ВНИИЭФ". 2011. С. 288-300.

[7] Granichin О., Volkovich V., Toledano-Kitai D. Randomized Algorithms in Automatic Control and Data Mining. Springer-Verlag: Heidelberg. 2014. 251 p.

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

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

А. В. Смагличенко, ведущий инженер

ЗАО "РТСофт" "Средства и системы автоматизации"

asmaglichenko@dev.rtsoft.ru

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

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

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

[1] Горбатиков, А. В., Ларин, Н. В., Моисеев Е. И., Белящов А.B. Применение метода микросейсмического зондирования для изучения строения погребенной трубки взрыва // Доклады Академии Наук. 2009. Том 428. №4. С. 526-530.

[2] Патент РФ на изобретение №2271 554, МПК G01V 1/00. Способ сейсморазведки / А. В. Горбатиков; заявл. 25.03.2005; опубл. 10.03.2006. Бюл. №7. 9 с.

[3] Горбатиков А. В., Степанова М.Ю., Кораблев Г.Е. Закономерности формирования микросейсмического поля под влиянием локальных геологических неоднородностей и зондирование среды с помощью микросейсм // Физика Земли. 2008. №7. C. 66-84.

[4] Ыт S., Harris J.G. Analog implementation of ratio spectrum // In: Proc. of the IEEE International Symposium on Circuits and Systems. Monterey. 1998. P. 277-280.

[5] Skowronski M.D., Harris, J. A Probabilistic Analysis of the Ratio Spectrum // In: Proc. of the IEEE Adaptive Systems for Signal Processing, Communications, and Control Symposium. Lake Louise, Alta. 2000. P. 333-336.

Сравнение квадратичных критериев качества: эллипсоидальный подход

М. В. Хлебников, д. ф.-м. н.

Институт проблем управления им. В. А. Трапезникова РАН

mkhlebnikov2008@yandex.ru

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

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

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

[1] Хлебников М.В. LMI-подход к сравнению квадратичных критериев качества // XXI Международная конференция по автоматическому управлению "Автоматика-2014". Киев, Украина, 23-27 сентября 2014 г.

[2] Levine W.S., Athans M. On the determination of the optimal constant output feedback gains for linear multivariable systems // IEEE Transactions on Automatic Control. 1970. Vol. 15. No. 1. P. 44-48.

[3] Boyd S., El Ghaoui L., Feron E., Balakrishnan V. Linear Matrix Inequalities in System and Control Theory. Philadelphia: SI AM, 1994.

[4] Овсеевич А.И. Структура аттрактора форм множеств достижимости // Функциональный анализ и его приложения. 2010. Т. 44. № 2. С. 74-81.

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

[6] Хлебников М.В., Щербаков П. С. Линейно-квадратичное управление: II // Автоматика и телемеханика. 2015. (в печати)

Differentiated Consensuses in a Stochastic Network with Priorities

Y. Ivanskiy

Saint Petersburg State University

ivanskiy.yuriy@gmail.com

Key words: differentiated consensus, network control, randomized algorithms.

In this paper we consider a distributed stochastic network system with incoming tasks of different priorities. The system is assumed to have variable topology, and the agents are not necessarily always connected to each other. In addition, the observations about the neighbors' states are assumed to be available with random noise and delays. To ensure efficient operation of this network system, a novel control strategy is proposed. With this strategy, the network resources are allocated in a randomized way with probabilities corresponding to each priority class. To maintain the balanced load across the network for different priorities, a so-called "differentiated consensuses" problem is examined. This consensus problem is that, in a system with multiple classes, consensus is desired for each class separately; these may be different for different classes. In this paper, we prove the ability of the proposed control protocol to maintain almost balanced load, i.e. an approximate consensus for every priority class across the network. In addition, a numerical example that illustrates the proposed control strategy and the results of simulations are provided.

Bibliogr.: 26 refs.

Analysis of Concurrent Hash Tables Algorithms

R. I. Kuchumov,

Petrozavodsk State University

kuchumovri@gmail.com

A. V. Sokolov,

Petrozavodsk State University,

Institute of Applied Mathematical Research of the Karelian Research

Centre, RAS

avs@krc.karelia.ru

Key words: Hash tables, cuckoo hashing, hopscotch hashing, concurrent computing.

The paper considers the analysis of cuckoo hashing and hopscotch hashing for multicore processors. Cuckoo hashing is used in distributed memory caching systems which are often used in server applications and databases. Hopscotch hashing is interesting for its processor's cache usage scheme and high performance. Besides that, we compare the implementation of these hashing methods with the concurrent _hash_ map table from the Intel TBB library.

Bibliogr.: 6 refs.

A Model for Network Load Balancing Problem Based on the Parametric Flow Approach

N. V. Malkovsky

Saint Petersburg State University

malkovskynv@gmail.com

Key words: load balancing, optimal control, linear systems, robust systems, network flows, maximum flow problem, parametric flow problem.

In this paper, a model of network load balancing is considered. The network is assumed to have known and measured values of the computing performance of its nodes and capacities of its communication channels. For this model, the problem of finding the minimum calculation time of task package with arbitrary initial task distribution is studied. This problem is reformulated as a special case of parametric flow problem which can be solved with the same asymptotical complexity as that for the maximum flow problem via preflow-push algorithms. Robustness and stability properties in the presence of uncertainties of the measurements and communication delays are proved for this approach.

Bibliogr.: 30 refs.

Using Problem Oriented Metrics for Solving Pseudo-Euclidian Travelling Salesman Problem with Euclidian Algorithms

S. Makarkin, B. Melnikov

Samara state university

M. Trenina

Togliatty state university

mkhlebnikov2008@yandex.ru

Key words: travelling salesman problem, Euclidean TSP, pseudo-euclidi-an TSP, metrics, heuristic algorithm.

This paper is a continuation of the previous one published in vol. 9. To solve the pseudoeuclidian TSP, we use several randomly generated permutations of the set of the cities. For each permutation, we calculate the coordinates of each city. We select the best coordinates by solving an optimization problem by rotating and shifting the whole set of cities. We consider several different suitable metrics and analyze their properties. We also describe a heuristic local search algorithm based on these metrics and present the results of computational experiments.

Bibliogr.: 8 refs.

Monte Carlo Simulation of the Dynamics of Atomic Processes During Annealing of Nanoporous Silicon

Yu. S. Nagornov Togliatti State University Nagornov.Yuri@gmail.com

Key words: Monte-Carlo method, simulation of anneling, nanoporous silicon, quantum wires, melting thermodynamics.

The paper presents the results of Monte Carlo simulation of the dynamics of atomic processes in nanoporous silicon and their interpretation in terms of thermodynamics of melting of the surface layer of quantum wires. The results of simulation and thermodynamic calculation shows that the annealing process of the rectangular pores can be represented as follows. First, the surface energy is determined only by the geometric characteristics of pores, which correspond to the symmetry directions (110) and (100). During annealing, the surface layer is melted so that the surface energy tends to its minimum. Assuming that the filling of the micro-channels is due to the surface energy of the channels, the adopted approximations made it possible to explain the formation of cavities depending on the depth of the channel. The calculations show that, for deep pores, the thermodynamic system lacks the surface energy to take the minimum value; as a result the pore transformation process stops at the depth values of 22 nm or more. When the depth of the pores is about 47 nm, the channel separates into two cavities, since their association requires additional energy.

Bibliogr.: 20 refs.

Matrix Methods for the Design of Minimal Forms of Finite Nonstationary Maxmin Fuzzy Automata

Yu. Ponomareva,

R. V. Stroilov,

M. K. Chirkov

Saint Petersburg State University

a_ponomareva@mail.ru

Key words: finite nonstationary fuzzy automata, equivalence of finite nonstationary fuzzy automata, minimal forms of automata, matrix methods for the design of minimal forms.

We consider methods and procedures for the design of minimal (in the overall number of states) forms for nonstationary maxmin ("pessimistic") fuzzy automata with finite nonstationary structure. These methods are based on constructing special left and right transformation matrices for every elementary fuzzy structure that enters the functional automaton graph, and, respectively, on the consecutive construction of the so-called left and right reduced forms of automata. This leads to finding the minimal form of a given finite nonstationary maxmin fuzzy automata. An example is provided.

Bibliogr.: 5 refs.

Analysis of Ratios of Spectra to Estimate the Resolution of the Microseismic Sounding Method

A. V. Smaglichenko

"RTSoft" "Tools and automation systems"

asmaglichenko@dev.rtsoft.ru

Key words: seismic signal, spectra ratio, resolving ability of method, physical modeling.

A counterpart of the spectral representation, previously used to study the models of "white noise is applied to assess the resolution of the microseismic sounding method that finds the location of the Earth inhomogeneous structure by using the data of Rayleigh waves. Through the physical modeling it was shown that the ratio spectrum of signals recorded by the seismic receiver system, determines the parameter whose values can reflect the presence of hindrance caused by the heterogeneity in a relatively stationary seismic field, the behavior of the parameter is compared with the conditions of the seismic experiment that allows us to give recommendations for improving the resolution of the microseismic sounding method.

Bibliogr.: 5 refs.

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

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

Том 10

Выпуск 1

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

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

Подписано в печать 15.11.14. Формат 60 х 84/16-

Бумага офсетная. Печать офсетная.

Усл. печ. л. 10,0. Тираж 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