Известия Тульского государственного университета. Технические науки, 2016, № 11. Часть 1

Министерство образования и науки Российской Федерации 
 
Федеральное государственное бюджетное  
образовательное учреждение высшего образования  
«Тульский государственный университет» 
 

 
 
 
16+ 
ISSN 2071-6168 
 
 
 
ИЗВЕСТИЯ  
ТУЛЬСКОГО ГОСУДАРСТВЕННОГО 
УНИВЕРСИТЕТА 
 
 
 
 
ТЕХНИЧЕСКИЕ НАУКИ 
 
 
Выпуск 11 
 
 
Часть 1 
 
 
 
 
 
 
 
 
 
 
 
Тула 
Издательство ТулГУ 
2016 

УДК 621.86/87                                                                             ISSN 2071-6168 
 
 
Известия Тульского государственного университета. Технические науки.  
Вып. 11. Ч. 1. Тула: Изд-во ТулГУ, 2016. 290 с.
 
Рассматриваются научно-технические проблемы информатики, вычислительной техники, защиты информации, интеллектуального анализа 
данных, а также вопросы применения информационных систем в решении 
прикладных задач. 
Материалы предназначены для научных работников, преподавателей вузов, студентов и аспирантов, специализирующихся в проблематике 
технических наук. 
 
 
 
Редакционный совет 
 
М.В. ГРЯЗЕВ – председатель, В.Д. КУХАРЬ – зам. председателя, 
В.В. ПРЕЙС – главный редактор, А.А. МАЛИКОВ – отв. секретарь, 
И.А. БАТАНИНА, О.И. БОРИСКИН, М.А. БЕРЕСТНЕВ, В.Н. ЕГОРОВ, 
О.Н. ПОНАМОРЕВА, Н.М. КАЧУРИН, В.М. ПЕТРОВИЧЕВ 
 
 
 
Редакционная коллегия 
 
О.И. Борискин (отв. редактор), С.Н. Ларин (зам. отв. редактора), 
Б.С. 
Яковлев 
(отв. 
секретарь), 
И.Л. 
Волчкевич, 
Р.А. 
Ковалев,  
М.Г. Кристаль, А.Д. Маляренко (Республика Беларусь), А.А. Сычугов,  
Б.С. Баласанян (Республика Армения), А.Н. Чуков  
 
 
Подписной индекс 27851 
по Объединённому каталогу «Пресса России» 
 

Сборник 
зарегистрирован 
в 
Федеральной 
службе по надзору в сфере связи, информационных 
технологий и массовых коммуникаций (Роскомнадзор).  
ПИ № ФС77-61104 от 19 марта 2015 г.  
«Известия ТулГУ» входят в Перечень ведущих 
научных 
журналов 
и 
изданий, 
выпускаемых 
в 
Российской Федерации, в которых должны быть 
опубликованы научные результаты диссертаций на 
соискание учёной степени доктора наук 
 
 
© Авторы научных статей, 2016 
© Издательство ТулГУ, 2016 

Данный выпуск журнала приурочен к двухлетию создания Института прикладной математики и компьютерных наук, образованного путем 
слияния факультета кибернетики и механико-математического факультета 
ТулГУ. За прошедшие с момента создания два года институт сохранил и 
преумножил достижения своих предшественников как в научной, так и в 
учебной сферах. 
В настоящее время институт является основным структурным подразделением университета. В нем осуществляется подготовка специалистов, бакалавров, магистров в области информатики и вычислительной 
техники, математиков, механиков, а также специалистов по защите информации. Преподавателями института выполняются научные исследования практически по всем разделам компьютерных наук: алгоритмы и 
структуры данных (теории вычислимости, вычислительной сложности, параллельных вычислений, дедуктивных и реляционных баз данных, распознавания образов, теория алгоритмов), архитектура компьютеров (цифровая логика, теория кодирования и теория конечных автоматов); разработка 
программного обеспечения (создание программных систем, которые 
должны удовлетворять заданным программным спецификациям, быть 
безопасными, защищенными, надежными и заслуживающими доверия 
пользователей); базы данных и информационно-поисковые системы (организация больших наборов постоянно сохраняемых и совместно используемых данных, допускающих их обновление и обеспечивающих эффективное выполнение запросов); искусственный интеллект и робототехника 
(распознавание сенсорных сигналов, звуков, изображений и образов, обучение, процессы рассуждения при решении задач и планирования); взаимодействие человека и компьютера (пользовательский интерфейс); прикладная математика (методы и алгоритмы дискретной математики в научных исследованиях). 
Ученые института идут «в ногу со временем» и начинают пробовать свои силы в новых для них сферах науки и техники. Это, в первую 
очередь, работы, связанные с информационной безопасностью. 
Результаты исследований ученых института докладываются как на 
российских, так и международных научных конференциях, публикуются в 
российских и международных изданиях. Некоторые из них нашли отражение в данном сборнике. 
 
Директор ИПМКН 
кандидат технических наук, доцент 
Алексей Алексеевич Сычугов 

ИНТЕЛЛЕКТУАЛЬНЫЙ АНАЛИЗ ДАННЫХ 
 
 
 
 
УДК 004.942 
 
АНАЛИЗ АЛГОРИТМОВ ПРЕОБРАЗОВАНИЯ ИНФОРМАЦИИ  
В ИНФОРМАЦИОННО-ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ  
 
Г.В. Басалова  
 
Рассмотрен подход к анализу алгоритмов преобразования информации в информационно-вычислительных системах с использованием математического аппарата сетей Петри. Предлагаемый подход позволяет выполнять моделирование и анализ 
алгоритмов обработки информации в разрабатываемой или уже существующей вычислительной системе. При этом анализ может производиться с помощью вычислительной техники, так как все его этапы строго формализованы. 
Ключевые слова: алгоритмы обработки информации, моделирование вычислительных систем, сети Петри. 
 
Одним из основных этапов разработки любых, в том числе и специализированных, вычислительных систем являются изучение и анализ 
процессов обработки информации в проектируемой системе. В процессе 
изучения и анализа должны быть уточнены структура вычислительной 
системы, входные, промежуточные и выходные данные, процедуры обработки информации и последовательность их реализации, основные характеристики специализированной вычислительной системы и ограничения на 
ее реализацию [1].  
При анализе процессов преобразования информации используются 
информационные модели, предназначенные для отражения информационных связей между объектами. Особенность такого рода моделей заключается в их графическом представлении, но при этом имеется возможность 
матричного или аналитического способа их изображения. Информационные модели отражают информационные потоки между различными объектами, отношения между ними, содержат идентификаторы объектов, объемные, временные, частотные и другие характеристики как самих объектов, так и входящих и исходящих потоков данных, а также последовательность выполнения расчетов.  

Интеллектуальный анализ данных 

 

 
5

В основу описываемого подхода положен принцип последовательного эквивалентного преобразования матричных моделей систем обработки данных в зависимости от этапа анализа системы и необходимости получения требуемых характеристик.  
Исходной информацией для моделирования и анализа технологии 
обработки данных является состав информационных ресурсов (ИР) по каждой задаче, отношения предшествования между ними, области их определения, множество используемых констант, структурированные матрицы 
смежности и достижимости, определяющие технологию обработки данных. 
На основе анализа матриц смежности и достижимости ИР строится 
информационных граф для каждой задачи. Анализ информационного графа и его подграфов позволяет определить состав процедур, необходимых 
для решения задачи. Объединения множества процедур и множества ИР по 
множеству задач определяют полное множество ИР и процедур заданного 
множества задач обработки данных. Путем проведения специальных операций “выравнивания” и “наложения” графов отдельных задач формируется общий интегрированный граф технологии решения задач обработки 
данных, матрица смежности которого является результатом логического 
сложения матриц смежности анализируемых задач.  
Интегрированный граф содержит общие и специфические части 
технологии решения рассматриваемого множества задач. Исходными данными для анализа, систематизации и формирования требований к схеме 
обработки данных является информация о парных отношениях между наборами информационных ресурсов системы обработки данных, формализуемая в виде матрицы смежности. 
Рассмотрим матричные и графовые модели описания исходной информации и процедур ее обработки. Для описания алгоритмов решения задач обработки данных используют два стандартных блока: функциональный блок и блок принятия решений (рис. 1).  

 
 
Рис. 1. Блоки для построения моделей обработки информации 
 
Функциональный блок  u  представляет собой отдельную процедуру 
обработки данных, под которой понимается некоторое преобразование одних информационных элементов в другие безотносительно к средствам, на 
которых реализуется это преобразование.  Основным требованием при вы

Известия ТулГУ. Технические науки. 2016. Вып. 11. Ч. 1 

 

 
6

делении функциональных блоков является одинаковый уровень абстракции и детализации при анализе отдельных задач обработки данных. Под 
блоком    uп    принятия решений понимают процедуру или операцию логического сравнения поступающих входных данных с заданными. В результате операции сравнения управление передается одному (u1) или другому 
(u2)  функциональному блоку. С помощью этих блоков описывают циклические участки в алгоритмах обработки данных.  
Информационное обеспечение алгоритма обработки данных составляет множество типов ИР, обрабатываемых процедурами алгоритма. В 
качестве ИР в зависимости от уровня абстракции рассматриваются базы 
данных, массивы, блоки, записи и т.д. Процедуры обработки данных,  входящие в функциональный блок, можно рассматривать как преобразования 
множества входных либо промежуточных ИР в множество промежуточных 
либо выходных ИР задачи [2].  
Степень абстракции процедур обработки информационных элементов зависит от необходимого уровня детализации описания задач обработки данных при их анализе.  
Представим процессы преобразования и обработки информации в 
вычислительной системе с помощью сети Петри. 
Как известно, сеть Петри определяется множеством состояний и 
переходов, а также входными и выходными функциями переходов. Состояния сети будем обозначать кружками, а переходы черточками (барьерами). Дуги соответствуют функциям, связывающим множества состояний 
и переходов. Входная функция переходов определяет для каждого перехода множество его входных состояний, а выходная – множество его выходных состояний. 
При использовании сетей Петри вводится понятие маркера, под которым понимается метка готовности запуска перехода по каждому из его 
входных состояний. Наличие маркера будем обозначать точкой  в кружочке, соответствующем состоянию. Число точек соответствуют числу маркеров в каждом состоянии. 
Переход может сработать, если в каждом его входном состоянии 
имеется хотя бы один маркер. Размещение маркеров по вершинамсостояниям сети Петри называется ее разметкой. 
Таким образом, сеть Петри – это набор N = (P, T, F, H, M0), где   
– P – конечное множество состояний;  
– T – конечное множество переходов;  
– F: P ×T ⇒ {0, 1}, H: T ×P ⇒ {0, 1} – функции инцидентности;  
– M0: P ⇒ {0, 1, 2, …} – начальная разметка сети. 
Графически сеть Петри представляется в виде ориентированного 
графа. Вершину-состояние p и вершину-переход t соединяют дугой (p,t), 
если F(p,t)=1 и дугой (t,p), если H(t,p)=1.  

Интеллектуальный анализ данных 

 

 
7

Вершины-состояния помечаются целыми неотрицательными числами или соответствующим числом маркерных точек. 
Если все состояния сети обозначить последовательно символами p1, 
p2, p3, … pn, то разметку всех состояний сети можно представить в виде nмерного вектора M, координаты которого равны числу маркерных точек в 
соответствующих состояниях. 
Функционирование сети заключается в переходе от одной разметки 
к другой. Смена разметок происходит в результате срабатывания переходов. Переход t может сработать при разметке М, если 

M(p) – F(p,t) ≥ 0, ∀p ∈ P. 

Это означает, что каждое входное состояние перехода t помечено 
хотя бы одной маркерной точкой. 
В результате срабатывания некоторого перехода t, удовлетворяющего условию (1) разметка M заменяется разметкой M’:  

∀p ∈ P: M’(p) = M(p) – F(p,t) + H(t,p), 

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

точка. Это обозначается: 
t
M
M
'
→
. 
Пусть D ={d1, d2, ..., dS} –  множество ИР специализированной вычислительной системы, где S – число элементов;   U = {u1, u2, ..., uL} – множество процедур обработки данных.  
Поставим в соответствие каждому элементу di∈D вершинусостояние pi сети. Каждому элементу uj∈U поставим в соответствие переход ti сети.  
В соответствии со взаимосвязью информационных ресурсов и процедур обработки соединим дугами элементы множеств P и T. Элемент 
pi∈P соединяется с элементом tj∈T дугой (pi, tj), если информационный ресурс di является входным элементом процедуры uj и дугой (tj, pi) – если выходным. Так как информационный ресурс может являться входным для нескольких процедур, то для восстановления маркерных точек состояния pi 
после срабатывания перехода tj необходимо также построить дуги (tj, pi) 
для таких tj и pi, для которых существует дуга (pi, tj). 
Под матрицей смежности ИР   М0  понимают квадратную бинарную 
матрицу, проиндексированную по обеим осям множеством информационных элементов и содержащую запись 1 в позиции (i, j)  
s
j
i
,1
,
=
, если между информационными ресурсами di  и  dj существует отношение R такое, 
что для получения информационного элемента dj непосредственно необходимо обращение к ИР di.  

Известия ТулГУ. Технические науки. 2016. Вып. 11. Ч. 1 

 

 
8

Считается также (для удобства), что каждый элемент достижим из 
самого себя, то есть 
j
i
d
R
d
j
i
=
,
. Наличие такого отношения будет обо
значать как 
j
i
d
R
d
, а его отсутствие как 
j
i
d
R
d
, чему соответствует запись 0 в позиции  (i, j)  матрицы  М0.  
Такая формализация позволяет однозначно идентифицировать 
входные и выходные ИР в алгоритме обработки данных [3]. 
Матрице смежности М0  ставится в соответствие граф информационных взаимосвязей G(D, M0), множеством  вершин  которого  является  
множество ИР, а дуга (di,  dj) соответствует записи 1 в позиции   (i, j) в матрице смежности. Взаимосвязь между процедурами обработки, наборами 
входных и промежуточных данных удобно представлять с помощью таблицы 
инцидентности, 
которая 
представляет 
собой 
таблицу 
вида 

S
s
L
l
t
T
ls
,1
,
,1
,
=
=
=
, где  







−

+

=

.
процедуры
элементом
вsходным
является
если
,1

,
процедурой
ся
использует
не
если
,0

,
процедуры
элементом
входным
является
если
,1

l
s

l
s

l
s

ls
u
d
u
d
u
d
t

 
В таблице Т0 каждая строка отображает процедуру обработки данных, а каждый столбец – использование всеми процедурами рассматриваемого ИР, то есть в строке содержится информация о множестве входных и выходных данных, связанных с анализируемой процедурой.  
В s-м столбце таблицы допускается больше одной позиции (l, s) со 
значением -1, если существуют альтернативные варианты получения соответствующего ИР. В этом случае их число должно совпадать с общим числом процедур, имеющих в пересечении с s-м столбцом значение -1. 
Рассмотрим графовое представление двух основных видов взаимосвязи между элементами таблицы Т0. Выделим два случая. Пусть столбцу 
информационного ресурса ds соответствует единственная процедура  ul   со 
значением -1, а входными элементами процедуры ul  являются dk, dp, dm, 
что обозначим в виде ul (ds) = {dk, dp, dm } (рис. 2). Этот случай соответствует единственному варианту получения ds . 
 

 
 
Рис.2. Пример графа  для единственного варианта получения  
информационного ресурса ds 

Интеллектуальный анализ данных 

 

 
9

Пусть столбцу ИР ds  соответствуют  процедуры ul  и  uj со значением -1, то есть: 
ul (ds) = {dk, dp},     uj (ds) = {dk, dm}. 
Этот случай соответствует наличию двух альтернативных вариантов получения информационного элемента ds (рис. 3). В первом случае ИР 
получается с помощью процедуры ul , входными ИЭ которой являются dk, 
dp  во втором –  с помощью другой процедуры, имеющей входы dk, dm. 
 

 
 
Рис.3. Пример графа при наличии альтернативных вариантов  
получения информационного ресурса ds 
 
Для проведения основных процедур анализа задач обработки данных требуется получить структурированную матрицу смежности и построить соответствующие им графы. Для формирования структурированной матрицы смежности необходимо преобразовать исходные данные таким образом, чтобы выявить уровни обработки, последовательность используемых процедур и т.д. 
Вначале осуществляют переупорядочение ИР в матрице смежности 
по уровням их обработки. С этой целью используют матрицу достижимости ИР. Под матрицей достижимости В0 понимается квадратная бинарная 
матрица, проиндексированная одинаковым образом по обеим осям множеством информационных ресурсов 
S
s
d
D
s
,1
},
{
=
=
. Запись 1 или 0 в каж
дой позиции (i, j) матрицы достижимости соответствует наличию или отсутствию для всех упорядоченных пар ИР (di, dj) отношения достижимости 
R, обладающего свойством транзитивности. 
Информационный ресурс dj достижим  из информационного ресурса di (
j
i
d
R
d
), если на графе информационных взаимосвязей можно ука
зать направленный путь от вершины di  к вершине dj, либо di = dj, то есть 
если для получения информационного ресурса dj  используется ИР di.  
Матрица достижимости определяется с использованием матрицы 
смежности Т0 и свойства транзитивности отношения достижимости. При 
этом заданной матрице достижимости может соответствовать некоторое 

Известия ТулГУ. Технические науки. 2016. Вып. 11. Ч. 1 

 

 
10

множество матриц смежности Т0, любая из которых имеет одну и ту же 
матрицу достижимости В0. Следовательно, имеется множество графов информационных взаимосвязей, любой из которых содержит необходимую 
информацию для построения матрицы достижимости.  
Процедура выделения уровней обработки с использованием матрицы достижимости В0 состоит в следующем. Информационный ресурс 
D
di ∈
, принадлежит множеству элементов верхнего уровня матрицы достижимости, если 
)
(
)
(
)
(
i
i
i
d
R
d
A
d
R
=
∩
, где R(di) и А(di) –  соответственно 
множество предшествования и достижимости информационного элемента 
di.   
С использованием матрицы достижимости производится итеративное разделение множества ИР на подмножества в соответствии с уровнями 
их обработки. 
Упорядоченному множеству ИР соответствует структурированный 
граф информационных взаимосвязей, ИР которого разделены на различные 
уровни. 
Обозначим структурированную матрицу смежности Т0С. В этой 
матрице информационные ресурсы разделены на подмножества в соответствии с уровнями их обработки. Информационные ресурсы, столбцы которых в матрице Т0С не содержат единиц (нулевые столбцы) являются входными элементами задач обработки данных, а информационные ресурсы, 
соответствующие высшему уровню обработки L1, являются выходными 
ресурсами. Остальные ресурсы являются промежуточными. 
Для полного анализа необходимо получение взаимосвязи между 
информационными ресурсами и процедурами в алгоритме обработки данных. Поэтому на втором этапе анализа, используя информацию, содержащуюся в структурированной матрице смежности и таблице инцидентности 
задач обработки данных, строится структурированная матрица смежности 
технологии задач обработки данных [4]. Она отражает существующую 
взаимосвязь между информационными ресурсами и процедурами в общем 
алгоритме обработки данных. В этой матрице процедуры упорядочены по 
уровням их использования, а информационные ресурсы – по уровням их 
обработки. 
Таким образом, рассмотренный метод позволяет выполнять моделирование и анализ алгоритмов обработки информации в разрабатываемой 
или уже существующей специализированной вычислительной системе. 
При этом анализ может проводиться с помощью вычислительной техники, 
так как все его этапы строго формализованы. 
 
Список литературы 
 
1. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов / пер. с англ. М.: Мир, 1981. 366 с.