ISSN 1818-1015
Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П.Г. Демидова
МОДЕЛИРОВАНИЕ И АНАЛИЗ
ИНФОРМАЦИОННЫХ СИСТЕМ
Том 20 № 2 2013
Основан в 1999 г.
Выходит 6 раз в год
Свидетельство о регистрации ПИ №ФС77-49724 от 11.05.12
выдано Федеральной службой по надзору в сфере связи,
информационных технологий и массовых коммуникаций
Главный редактор
В.А. Соколов
Редакционная коллегия
С.М. Абрамов, О.Л. Бандман, В.А. Бондаренко,
С.Д. Глызин (зам. гл. ред.), Александр Дехтярь (США), М.Г. Дмитриев,
В.Л. Дольников, В.Г. Дурнев, Л.С. Казарин, Ю.Г. Карпов, С.А. Кащенко,
А.Ю. Колесов, И.А. Ломазова, Г.Г. Малинецкий, В.Э. Малышкин,
В.А. Непомнящий, П.Г. Парфенов, Н.Х. Розов, Р.Л. Смелянский,
Е.А. Тимофеев (зам. гл. ред.), Филипп Шнеблен (Франция)
Ответственный секретарь Е. В. Кузьмин
Адрес редакции: 150000, Ярославль, ул. Советская, 14
E-mail: mais@uniyar.ac.ru
Website: mais.uniyar.ac.ru
Научные статьи в журнал принимаются по электронной почте и на кафедре
теоретической информатики Ярославского государственного университета. Статьи
должны содержать УДК, аннотации на русском и английском языках и сопровождаться
набором текста в редакторе LaTEX. Плата с аспирантов за публикацию
рукописей не взимается.
○Ярославский государственный
университет им. П.Г. Демидова, 2013
c
Стр.1
СОДЕРЖАНИЕ
Моделирование и анализ информационных систем. Т. 20, №2. 2013
Ассоциативный параллельный алгоритм для динамической обработки
дерева кратчайших путей
Непомнящая А.Ш.
Алгоритм оценки параметров авторегрессионной модели элементарных
речевых единиц
Губочкин И. В.
Мультиагентная задача о роботах в пространстве: сложностн´
информационный и криптографический аспекты
Бернштейн А. Ю., Шилов Н. В.
Некоторые классы разрешимости задачи целочисленного сбалансирования
трехмерной матрицы с ограничениями второго рода
Смирнов А. В.
Построение модели для извлечения оценочной лексики в различных
предметных областях
Лукашевич Н. В., Четвёркин И. И.
Единая модель для геоклассификации веб-сайтов
Волков А. Н.
Группы гомологий сети Петри конвейера
Хусаинов А. А., Бушмелева Е. С., Тришина Т. А.
Моделирование, спецификация и построение программ
логических контроллеров
Кузьмин Е. В., Соколов В. А.
Асимптотика решения бисингулярной задачи для системы
линейных параболических уравнений. II
Бутузова М.В.
Технологии и алгоритмы для создания дополненной реальности
Благовещенский И. А., Демьянков Н. А.
Об эффективном моделировании неограниченного ресурса при помощи
односчетчиковых контуров
Башкин В. А.
О поворотах цифровых изображений
Парфенов П.Г.
Построение универсального линеаризованного графа потока управления
для использования в статическом анализе кода алгоритмов
Битнер В. А., Заборовский Н. В.
Algorithm for Efficient Entropy Estimation
Timofeev E. A.
Редактор, корректор А.А. Аладьева. Редактор перевода Э.И. Соколова. Подписано в печать
25.04.2013. Формат 60х841/8. Усл. печ. л. 21,4. Уч.-изд. л. 19,4. Тираж 500 экз.
Отпечатано на ризографе. Ярославский государственный университет им. П. Г. Демидова,
150 000, Ярославль, ул. Советская, 14. Телефон редакции (4852) 79-77-72.
ой,
34
54
70
80
92
104
121
129
139
157
166
178
5
23
Стр.2
ISSN 1818-1015
Ministry of Education and Science of the Russian Federation
P.G. Demidov Yaroslavl State University
MODELING AND ANALYSIS
OF INFORMATION SYSTEMS
Volume 20 No 2 2013
Founded in 1999
6 issues per year
State Registration License No ФС77-49724 of 11.05.12
Editor-in-Chief
V. A. Sokolov
Editorial Board
S.M. Abramov, O.L. Bandman, V.A. Bondarenko,
S.D. Glyzin (Deputy Editor-in-Chief ), Alexander Dekhtyar (USA), M.G. Dmitriev,
V.L. Dol’nikov, V.G. Durnev, L.S. Kazarin, Yu.G. Karpov, S.A. Kashchenko,
A.Yu. Kolesov, I.A. Lomazova, G.G. Malinetsky, V.E. Malyshkin, V.A. Nepomniaschy,
P.G. Parfionov, N.H. Rozov, Philippe Schnoebelen (France),
R.L. Smeliansky, E. A. Timofeev (Deputy Editor-in-Chief )
Responsible Secretary E. V. Kuzmin
Editorial Office Address: Sovetskaya str., 14, Yaroslavl, 150000, Russia
E-mail: mais@uniyar.ac.ru
Website: mais.uniyar.ac.ru
○ P.G. Demidov Yaroslavl State University, 2013
c
Стр.3
Contents
Modeling and Analysis of Information Systems. Vol. 20, No 2. 2013
Associative Parallel Algorithm for Dynamic Update of the Shortest Paths Tree
Nepomniaschaya A. S.
An Algorithm for Parameters Estimation of Autoregressive Model of Basic
Speech Units
Gubochkin I. V.
“Robots in Space” Multiagent Problem: Complexity, Information
and Cryptographic Aspects
Bernstein A.Yu., Shilov N. V.
Some Solvability Classes for the Problem of Integer Balancing
of a Three-Dimensional Matrix with Constraints of Second Type
Smirnov A. V.
Construction of a Model for the Cross-Domain Opinion Word Extraction
Loukachevitch N. V., Chetviorkin I. I.
Unified Classification Model for Geotagging Websites
Volkov A. N.
Homology Groups of a Pipeline Petri Net
Husainov A. A., Bushmeleva E. S., Trishina T. A.
Modeling, Specification and Construction of PLC-programs
Kuzmin E. V., Sokolov V. A.
Asymptotics of the Solution of the Bisingular Problem for a System
of Linear Parabolic Equations. II
Butuzova M.V.
Technologies and Algorithms for Building the Augmented Reality
Blagoveshchenskiy I. A., Demyankov N. A.
On the Efficient Representation of an Unbounded Resource with the Aid
of One-counter Circuits
Bashkin V. A.
On the Turns of Digital Images
Parfenov P. G.
The Construction of an Universal Linearized Control Flow Graph
for Static Code Analysis of Algorithms
Bitner V. A., Zaborovsky N. V.
Algorithm for Efficient Entropy Estimation
Timofeev E. A.
5
23
34
54
70
80
92
104
121
129
139
157
166
178
Стр.4
Модел. и анализ информ. систем. Т.20, №2 (2013) 5–22
c
⃝ Непомнящая А. Ш., 2012
УДК 519.172
Ассоциативный параллельный алгоритм для
динамической обработки дерева кратчайших путей
Непомнящая А. Ш.
Институт вычислительной математики и математической геофизики СО РАН
630090, Россия, г. Новосибирск, проспект Академика Лаврентьева, 6
e-mail: anep@ssd.sscc.ru
получена 19 апреля 2012
Ключевые слова: ориентированный взвешенный граф, дерево кратчайших
путей, матрица смежности, декрементальный алгоритм, ассоциативный
параллельный процессор
В работе строится эффективный ассоциативный параллельный алгоритм
для динамической обработки дерева кратчайших путей после удаления одной
дуги из ориентированного взвешенного графа. С этой целью вначале описывается
используемая структура данных и ее построение, а также приводится
STAR–машина, которая моделирует работу ассоциативных (контекстно–
адресуемых) параллельных систем с простыми процессорными элементами и
вертикальной обработкой информации. На этой модели ассоциативный параллельный
алгоритм представляется в виде главной процедуры DeleteArcSPT,
использующей группу вспомогательных процедур для выполнения его отдельных
частей. Доказана корректность процедуры DeleteArcSPT и показано, что
на STAR-машине она выполняется за время O(hk), где h – число битов, которое
требуется для кодирования длины максимального кратчайшего пути, а
k – число вершин, для которых вычисляются новые кратчайшие пути после
удаления одной дуги из исходного графа.
1. Введение
Задача нахождения кратчайших путей возникает в различных приложениях. Известны
две версии этой проблемы: нахождение кратчайших путей из одной вершины
(the single-source shortest paths problem) и нахождение кратчайших путей между
каждой парой вершин (the all-pairs shortest paths problem). Динамическая версия
проблемы нахождения кратчайших путей из одной вершины состоит в обработке
информации о кратчайших путях во время изменения графа без перевычисления
графа целиком после каждого локального изменения в нем. Типичными операциями
для этого вида преобразований являются добавление или удаление одной дуги либо
изменение веса одной дуги. Если граф представляет коммуникационную или транспортную
сеть, то добавление или удаление дуги отражает такие реальные изменения
5
Стр.5