ISSN 1818-1015
Министерство образования и науки Российской Федерации
Ярославский государственный университет им. П.Г. Демидова
МОДЕЛИРОВАНИЕ И АНАЛИЗ
ИНФОРМАЦИОННЫХ СИСТЕМ
Том 19 № 4 2012
Основан в 1999 г.
Выходит 6 раз в год
Свидетельство о регистрации ПИ №ФС77-49724 от 11.05.12
выдано Федеральной службой по надзору в сфере связи,
информационных технологий и массовых коммуникаций
Главный редактор
В.А. Соколов
Редакционная коллегия
С.М. Абрамов, О.Л. Бандман, В.А. Бондаренко,
С.Д. Глызин (зам. гл. ред.), М.Г. Дмитриев, В.Л. Дольников,
В.Г. Дурнев, Л.С. Казарин, Ю.Г. Карпов, С.А. Кащенко, А.Ю. Колесов,
И.А. Ломазова, Г.Г. Малинецкий В.Э. Малышкин, В.А. Непомнящий,
П.Г. Парфенов, Н.Х. Розов, Р.Л. Смелянский, Е.А. Тимофеев (зам. гл. ред.)
Ответственный секретарь Е. В. Кузьмин
Адрес редакции: 150000, Ярославль, ул. Советская, 14
E-mail: mais@uniyar.ac.ru
Website: mais.uniyar.ac.ru
Научные статьи в журнал принимаются по электронной почте и на кафедре
теоретической информатики Ярославского государственного университета. Статьи
должны содержать УДК, аннотации на русском и английском языках и сопровождаться
набором текста в редакторе LaTEX. Плата с аспирантов за публикацию
рукописей не взимается.
Ярославский государственный
университет им. П.Г. Демидова, 2012
c
Стр.1
СОДЕРЖАНИЕ
Моделирование и анализ информационных систем. Т. 19, №4. 2012
Об одной нестационарной задаче маршрутизации с ограничениями
Ченцов А.Г., Ченцов П.А.
О построении и верификации программ логических контроллеров
Кузьмин Е.В., Соколов В.А.
Сравнительный анализ производительности транспортных протоколов Trickles
и TCP в условиях высокой нагрузки на коммуникационную сеть
Никитинский М.А., Чалый Д.Ю.
Преобразование хвостовых рекурсий в функционально-потоковых параллельных
программах
Легалов А.И., Непомнящий О.В., Матковский И.В., Кропачева М.С.
Счетные идеалы в полурешетке De степеней перечислимости
Тихов В.В.
Об одном вопросе А.И. Мальцева из "Коуровской тетради"
Дурнев В.Г.
Замечания о расположениях точек на квадриках
Селиверстов А. В.
Обобщенные асинхронные системы
Кудряшова Е.С., Хусаинов А.А.
Двойственность Гейла и смежностность случайных многогранников. II
Бродский А.Г.
О стойкости кодового зашумления к статистическому анализу
наблюдаемых данных многократного повторения
Деундяк В.М., Косолапов Ю.В.
Оптимизация расчёта инвариантов сети Петри в рамках задачи
формирования сценариев интеграционного тестирования
Доррер М.Г., Курохтин В.В.
Конструктивная классификация графов
Иорданский М.А.
Контекстно-свободная грамматика одной ритмической модели русского стиха
Бойков В. Н.
The First Yaroslavl Summer School on Discrete and Computational Geometry
Dolbilin N., Edelsbrunner H., Ivanov A., Musin O.
Редактор, корректор А.А. Аладьева. Редактор перевода Э.И. Соколова. Подписано в печать
25.11.2012. Формат 60х841/8. Усл. печ. л. 20,3. Уч.-изд. л. 18,5. Тираж 500 экз. Заказ 120/012
Отпечатано на ризографе. Ярославский государственный университет им. П. Г. Демидова,
150 000, Ярославль, ул. Советская, 14. Телефон редакции (4852) 79-77-72.
5
25
37
48
59
67
72
78
87
110
128
144
154
168
Стр.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 19 No 4 2012
Founded in 1999
6 issues per year
Editor-in-Chief
V. A. Sokolov
Editorial Board
S.M. Abramov, O.L. Bandman, V.A. Bondarenko,
S.D. Glyzin (Deputy Editor-in-Chief ), 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, V.E. Malyshkin, G.G. Malinetsky, V.A. Nepomniaschy,
P.G. Parfionov, N.H. Rozov, 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, 2012
c
Стр.3
Contents
Modeling and Analysis of Information Systems. Vol. 19, No 4. 2012
On a Nonstationary Route Problem with Constraints
Chentsov A.G., Chentsov P.A.
On Construction and Verification of PLC-Programs
Kuzmin E. V., Sokolov V. A.
Performance Analysis of the Transport Protocols Trickles and TCP
under High-load Network Conditions
Nikitinskiy M.A., Chalyy D.Ju.
Tail Recursion Transformation in Functional Dataflow Parallel Programs
Legalov A.I., Nepomnyaschy O.V., Matkovsky I.V., Kropacheva M.S.
Countable Ideals in a Semi-Lattice of the De Enumeration Degrees
Tikhov V.V.
On one A.I. Mal’cev’s Question from the ”Kourovskaya Notebook”
Durnev V.G.
Some Notes about Arrangements of Points on Quadrics
Seliverstov A. V.
Generalized Asynchronous Systems
Kudryashova E.S., Khusainov A.A.
Gale Duality and the Neighborliness of Random Polytopes. II
Brodskiy A.G.
On the Firmness Code Noising to the Statistical Analysis
of the Observable Data of Repeated Repetition
Deundyak V.M., Kosolapov J.V.
Optimization of Calculating Invariants in Petri Nets to Support the Creation
of Integration Testing Scenarios
Dorrer M.G., Kurohtin V.V.
A Constructive Classification of Graphs
Iordanskii M.A.
A Context-Free Grammar of One Rhythmic Model of Russian Verse
Boykov V.N.
The First Yaroslavl Summer School on Discrete and Computational Geometry
Dolbilin N., Edelsbrunner H., Ivanov A., Musin O.
5
25
37
48
59
67
72
78
87
110
128
144
154
168
Стр.4
Модел. и анализ информ. систем. Т.19, №4 (2012) 5–24
УДК 519.6
Об одной нестационарной задаче маршрутизации
с ограничениями
Ченцов А.Г., Ченцов П.А.1
Институт математики и механики УрО РАН
e-mail: chentsov@imm.uran.ru, chentsov.p@mail.ru
получена 4 марта 2012
Ключевые слова: маршрут, трасса, динамическое программирование, условия
предшествования
Исследуется экстремальная задача маршрутизации перемещений при ограничениях
в виде условий предшествования. Предполагается, что исполнитель
покидает начальный пункт (базу), после чего посещает систему мегаполисов
(конечных целевых множеств), на каждом из которых выполняет некоторую
работу. Функции стоимости внешних перемещений и (внутренних) работ зависят
от "момента посещения" , который может отвечать фактическому времени,
а может соответствовать естественной очередности (первое посещение, второе,
третье и т. д. ). Построены экономичный вариант широко понимаемого метода
динамического программирования (МДП) и, на его основе, оптимальный
алгоритм, реализованный на ПЭВМ. Предложен вариант жадного алгоритма.
1. Содержательная постановка задачи
Рассмотрим систему мегаполисов M1, . . . ,MN, где N – натуральное число, N
2; каждый мегаполис Mj есть непустое конечное подмножество (п/м) заданного
множества X. Задана база xo ∈ X, для которой xo /
также, что Mi ∩ Mj = ∅ при i = j (итак, дана система "островов" и точка, не
лежащая на "островах"). Требуется организовать перемещения
∈ M1, . . . , xo /
xo →(x(1)
1 ∈Mα(1) x(1)
2 ∈Mα(1))→. . .→(x(N)
1 ,x(1)
1 ∈Mα(N) x(N)
2 ), . . . , (xN)
1 ,x(N)
2 ∈Mα(N)),
где α – перестановка индексов 1, . . . ,N. В (1) прямые стрелки отвечают внешним
перемещениям, а волнистые – внутренним работам, выполняемым в пределах мегаполисов.
Требуется выбрать α, (x(1)
∈ MN. Полагаем
(1)
2 ) из соображений минимизации
аддитивного критерия качества (сумма стоимостей). На выбор α накладываются
дополнительные ограничения. В этой связи допустим сейчас (позднее будет
выбрана несколько более общая форма), что заданы два набора индексов из
1Работа поддержана грантами РФФИ №10-01-96020, №10-08-00484, №11-01-90432-укр ф а
5
Стр.5