Программные продукты и системы, 2011, № 4

Программные продукты и системы
№ 4, 2011 г.

3

УДК 519/64+517.4

ВЕКТОРНЫЕ СИСТЕМЫ УСРЕДНЕНИЙ НА ГРАФЕ

(Работа выполнена при поддержке РФФИ, проект № 10-01-00041а)

А.В. Коганов, к.ф.-м.н. (НИИСИ РАН, Москва, akoganov@yandex.ru)

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

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

Во многих задачах томографии, рентгеноско
пии и математического моделирования необходимо получить объемное или плоское изображение 
объекта по данным об интенсивности излучения, 
которое усреднено по некоторой системе пространственных областей или сечений. Это классическая задача интегральной геометрии, относящаяся к функциональному анализу и его вычислительным приложениям (например, [1, 2]). В современных исследованиях исходное пространство, 
на котором восстанавливается распределение интенсивности, часто изначально имеет структуру 
дискретного графа, а исходная информация относится к весовым усреднениям по подграфам. Исследованию методов восстановления функции в 
таких ситуациях посвящены работы [3–5]. 

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

Классическая проблематика интегральной гео
метрии связана с обращением операторов, усредняющих функцию, определенную на линейном 
пространстве с мерой, по заданной системе прямых или к-плоскостей в этом пространстве. В последние годы стала развиваться теория обращения 
операторов усреднения на пространствах с комбинаторной структурой, содержащих конечное или 
счетное число точек [3, 4]. В [5] показана связь 
комбинаторных и аналитических методов. При 
этом возникают новые формулы обращения на непрерывных пространствах с мерой. В данной статье рассматривается конструкция нескольких усреднений для функций, определенных на комбинаторном пространстве. 

Определения систем усреднения 

и соответствующей алгебры операторов

Определение 1. Скалярной системой усредне
ний X, Y, F, a на счетном множестве X с задан
ным линейным пространством функций F вида 
f: X
и с параметром усреднения из счетного 

множества Y назовем заданный набор функций 
a(y, x):X
, yY, которому сопоставлена сис
тема операторов на пространстве F, отображающая его в пространство функций на множестве Y
по формуле 

a
a

x X

h f(y)
(h f)(y)
a(y,x)f(x)




 
.
(1)

Множество X назовем базовым, множество Y –

параметрическим, значения a(x, y) – весами усреднения для точки x с параметром y.

Скалярная система усреднений обратима, если 

по образу функции haf() можно восстановить исходную функцию f (отображение ha инъективное). 

Векторной системой усреднения назовем ко
нечный, или счетный, набор систем усреднений 
X, Y, F, ai, i=1, …, m, с общими базовыми и параметрическими множествами. 

Векторная система усреднений обратима, если 

по образу функции 

1
m
a
a
def
(a)
(h f(.),...,h f(.))
h f(.)

(2)

можно восстановить исходную функцию f (отображение h(a) инъективное). 

В тех случаях, когда утверждение относится к 

обоим типам систем усреднения, будем говорить о 
системе усреднения без уточняющих слов. 

Определение 2. Скалярная система усреднения 

на графе определяется следующим.

I. Базовое множество совпадает с параметриче
ским множеством X=Y.

II. Для каждого yX множество тех xX, для 

которых a(y, x)0, конечно:



y
X
# x | X,a(y,x)
0
 


  .

Это свойство назовем прямой финитностью

усреднения: для каждого значения параметра усреднение ведется по конечному числу точек.

III. Для каждого xX множество тех yX, для 

которых a(y, x)0, конечно:



x
X
# y | X,a(y,x)
0
 


  .

Это свойство назовем обратной финитностью

усреднения: каждая точка участвует в усреднении 
для конечного числа значений параметра. Наличие 

Программные продукты и системы
№ 4, 2011 г.

4

прямой и обратной финитности назовем двусторонней финитностью.

Такая система отображается на граф с множе
ством вершин X и ребрами (y, x), на которых a(y, 
x)0. По условию III в каждую вершину этого 
графа входит конечное число ребер, а по условию 
II из каждой вершины выходит конечное число 
ребер. Сами значения a(y, x) можно рассматривать 
как веса соответствующих ребер.

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

В этом случае граф имеет ребро (y, x), если 

есть ненулевой вес ai(y, x)0 для некоторой компоненты i{1, …, m}. 

В системе усреднения на графе можно гово
рить о системе весов на ребрах. Этот граф назовем соответственным системе усреднения.

Стандартным пространством функций для 

систем усреднений на графе определим пространство F всех финитных функций, принимающих 
ненулевые значения в конечном числе точек. Это 
множество точек назовем носителем функции. 
Областью определения всех функций считаем все 
базовое множество X. На этих функциях значение 
оператора усреднения всегда определено и также 
финитно. Поэтому определена итерация любых 
двух операторов из векторной системы усреднения. Тогда эти операторы образуют алгебру по 
умножению (итерация операторов) и сложению 
(сумма образов) с обычным умножением на число 
(умножение образа). Для векторной системы усреднения это алгебра с m образующими, которая в 
общем случае некоммутативна. Эту алгебру назовем соответственной системе усреднения. Ее образующие – операторы 

1
m
a
a
h ,...,h
.

Определение 3. Вычислим кратные веса для 

скалярной системы усреднения 

a(x,z | t
1)



1
t

1
1
2
t

y ,
,y
X

a(x,y )a(y ,y ) ... a(y ,z)







;
(3)

a(x,z |1)
a(x,z)

.

Тогда

y X

a(x,z | t
1)
a(x,y | t)a(y,z)




 
.
(4)

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

на графе верна формула

n
a

y X

h f(x)
a(x,y | n)f(y)



 
.
(5)

Доказательство по индукции непосредственно 

из (1) и (4).

Определение 4. Вычислим кратные веса для 

векторной системы усреднения

1
t 1
a(x,z | i ,...,i
)



1
2
t 1

1
t

i
1
i
1
2
i
t

y ,
,y
X

a (x,y )a (y ,y ) ... a
(y ,z)








;
(6)

i
a(x,z | i)
a (x,z)

.

Тогда

1
t 1
a(x,z | i ,...,i
)

1
t 1
i
1
t
i

y X

a (x,y | i ,...,i )a
(y,z)




 
. (7)

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

на графе верна формула

i
i
t
1
a
a
1
t

y X

h
...h f(x)
a(x,y | i ,...,i )f(y)



 
.
(8)

Доказательство по индукции непосредственно 

из (1) и (7). Если все индексы принимают одно 
значение, то формула (8) совпадает с (5). Поэтому 
лемма 2 является обобщением леммы 1 на случай 
нескольких образующих соответственной алгебры.

Определение 5. Цепью длины n–1 на базовом 

множестве системы усреднения назовем конечную 
последовательность элементов x1, …, xn, в которой 
соседние члены различны xixi+1 и связаны ребром 
в соответственном графе. В скалярном случае a(xi, 
xi+1)0, i=1, …, n–1. Для векторной системы усреднения наличие ребра означает наличие для 
каждой пары соседних членов хотя бы одной системы aj(i), j(i){1, …, m}, в которой выполнено условие aj(i)(xi, xi+1)0. Цепь в векторной системе 
усреднения называется строгой, если в ней для 
всех i=1, …, n–1 дополнительно выполнено условие aj(i)(xi, xi)0.

Определение 6. Векторная система усреднения 

называется ациклической, если в ней все цепи не 
содержат повторяющихся членов. Это означает, 
что из условия a(x, yi1, …, it)0 для некоторой 
последовательности i1, …, it при yx следует, что 
для любой последовательности i1, …, it выполнено равенство a(y, xi1, …, it)=0 (если есть путь 
из одной точки в другую, то нет обратного пути). 

В частности, для скалярной ациклической сис
темы усреднений из условий yx и a(x, yt)0 для 
некоторого значения t1 следует, что для любого 
значения t1 выполнено условие a(y, xt)=0.

Соответственные графы ациклических систем 

не имеют циклов при движении по направлению 
ребер, но могут иметь петлю в некоторой вершине, если a(x, x)0 или ai(x, x)0 для некоторой 
компоненты i{1, …, m}. Такую точку xX базового пространства (то есть вершину соответственного графа) в ациклической векторной системе 
усреднения назовем петлевой.

Задача пополнения векторной 

системы усреднения

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

Замечание 1. Системе усреднения соответст
вует линейный оператор h(a). Поэтому необратимость означает, что ядро этого оператора нетриви

Программные продукты и системы
№ 4, 2011 г.

5

ально: dimker(h(a))1. Если же ядро тривиально,
ker(h(a))={0}, то оператор обратим. В случае конечного базового множества X< задача обращения сводится, например, к построению матрицы обратного оператора 
1

(a)
h . 

Если ядро нетривиально, функции из ядра по 

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




i
(a)
a
f
ker(h
)
i
1,...,m
x
X, h f(x)
0

  
 

. (9)

Теорема 1. Ядро оператора векторной системы 

усреднения совпадает с пересечением ядер ком
понент:

i

m

(a)
a

i 1

ker(h
)
ker(h )




.
(10)

Это следует из формулы (9).
Утверждение 1. Задача пополнения векторной 

системы усреднения решается любым (и только 
таким) набором скалярных систем 

m 1
m k
a
a
h
,...,h


 , у 

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

i

m k

(a)
a

i m 1

ker(h
)
ker(h )
{0}








.
(11)

Это утверждение следует из теоремы 1 и заме
чания 1. Если обозначить расширенную систему 
усреднения a=(a1, …, am, am+1, …, am+k), то левая 
часть формулы (11) определяет ядро ker(h(a)).

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

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




(a)
(a")

m 1
m k

F
ker(h
)
ker(h
),

a"
a
,...,a
.







(12)

Определение 8. Назовем приведенной систе
мой любую минимальную по составу скалярных 
операторов подсистему системы усреднения, ядро 
которой совпадает с ядром всей системы.

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

Утверждение 2. Если исходная система и ми
нимальное пополнение приведенные, полученная 
пополненная система остается приведенной. Это 
следует из свойства (12), поскольку отбрасывание 
любой скалярной компоненты усреднения приведет к увеличению одного из двух прямых слагаемых и тогда возникнет нетривиальное пересечение ядер в левой части формулы (11).

Утверждение 3. Если исходная система была 

усреднением на графе и пополнение является усреднением на графе, это свойство сохраняет пополненная система. Это проверяется непосредственно по условиям I–III определения 2 с учетом 
того, что объединение конечного числа конечных 
множеств будет конечным. 

Метод построения минимального пополне
ния для систем усреднения на графе. Рассмотрим произвольную функцию
(a)
ker(h
)

. Обо
значим 


def
V(x | a)
y | X,a(y,x)
0 , x
X




.

В силу прямой финитности можно записать

i

i

a
i

y V(x|a )

h
(x)
a (x,y) (y)
0








, 
(13)

i
#V(x | a )   ; i=1, …, m; xX.

Определим 
i
V(x)
V(x | a )| i
1,...,m
 

, тогда

V(x)< и

ia
i

y V(x)

h
(x)
a (x,y) (y)
0








; i=1, …, m. (14)

Обозначим D носитель функции , который 

конечен, поскольку оператор усреднения определен на пространстве финитных функций. 

Введем скалярное произведение функций f, 

fF:
def

y X

f
f '
f(y)f '(y)






.
(15)

Введем новые веса усреднения:

D
b(x,y)
b(x,y |
)
(y)
(x)

(y),
x
D ,

0,
x
D .



  







 




С функцией  свяжем усредняющий оператор 

hb, действующий на F. По определению ядра 
b(.,.|
)
 можно записать

b
b|

f
,
x
D ,
h f(x)
h
f(x)
0
x
D .







 




(16)

Поскольку функция  финитная, то оператор 

(16) двусторонне финитный (в усреднении участ

Программные продукты и системы
№ 4, 2011 г.

6

вуют только точки из носителя функции  и только для точек x из этого носителя). Для функций, 
ортогональных ядру оператора h(a) в смысле скалярного произведения (15), значение f* обнуляется. Обозначим (a) некоторый базис ядра оператора h(a). Рассмотрим векторный оператор 



(b|
)
b|
h
h
|



 .
(17)

Теорема 2. Оператор (17) является приведен
ным минимальным пополнением системы усреднения h(a). 

Доказательство.



(b|
)
b|
(a)
ker(h
)
ker(h
)
f | f
h








,

(b|
)
(a)
(b|
)
(a)
ker(h
,h
)
ker(h
)
ker(h
)
0





, (18)

(b|
)
(a)
ker(h
)
ker(h
)
F



.

Таким образом, оператор (17) является мини
мальным пополнением. Покажем, что система усреднения h(b) является приведенной. Устраним 
из этой системы любую функцию . Введем 
обозначения. Пусть S – некоторый набор функций 
из F. Тогда S – линейная оболочка этих функций; ortS – ортогональное дополнение к S; 
Pr(f)S – проекция функции f на S. В этих обозначениях из (18) 
(b|
)
ker(h
)
ort


 . Обозначим 

=\{}. Поскольку  является базисом ядра, то 

t
Pr( )
'
0
  



;

(b|
')
ker(h
)
ort
'
ort
t
ort




 

 . 

Теорема доказана.

Следствие. Из теоремы 2 и утверждения 3 

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

Пополнение ациклических 
систем усреднения на графе

Рассмотрим ациклическую систему усреднения

h(a) на графе (АСУГ – определение 6). 

Теорема 3. Если в АСУГ все вершины петле
вые, она обратима.

Доказательство. Введем функцию перехода

i(x), удовлетворяющую условию a(x, xi(x))0. По 
условию теоремы эта функция может быть задана 
в каждой точке.

В условиях теоремы для каждой вершины вер
на формула a(x,x | i(x))f(x) 

i(x)
a

y X

h
f(x)
a(x,y | i(x))f(y).




 
(19)

Для усреднения функции по строгим цепям 

требуются модифицированные кратные веса усреднения. Суммарные относительные веса перехода из точки x в точку y по строгим цепям длины 
t=1,… с использованием функции перехода i()
можно вычислить по рекуррентным формулам относительно параметра t:

1
,
x
y;
(x,y)
a(x,x | i(x))
0,
x
y;





 





*

i
a (x,y |1)
a (x,y | i(x)) (x,y);



*
*
*

z X

a (x,y | t
1)
a (x,z | t)a (z,y |1)




 
.
(20)

Многократная итерация формулы (19) позво
ляет записать бесконечный формальный ряд:

i(x)

i(y )

a

t
*

a

t 1
y X

h
f(x)

f(x)
a(x,x | i(x))

( 1)
a (x,y | t)h
f(y).














(21)

Поскольку функция финитная и система на 

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

Это доказывает теорему.
Теорема 4. Для пополнения векторной АСУГ 

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

Замечание 2. Указанное в теореме 4 пополне
ние в общем случае не будет ни минимальным, ни 
приведенным. Но, если в пополненной системе 
устранение любой компоненты приводит к исчезновению петли в некоторой точке, можно говорить об условно неприводимой системе. В этом 
случае все компоненты необходимы для применения формулы обращения (21).

Замечание 3. Наличие в АСУГ непетлевых то
чек делает невозможным обращение усреднения 
по формуле (21), но при этом может существовать 
обратимость иными методами. Теорема 3 утверждает только достаточные, но не необходимые условия обратимости АСУГ. Рассмотрим, например,
скалярную АСУГ на двусторонне бесконечном 
линейном соответственном графе с вершинами 
{…; –1; 0; +1} и ребрами вида (i, i+1). Веса усреднения заданы формулой 

1,
y
x
1,
a(x,y)
0,
y
x
1.




 




Тогда система не имеет ни одной петли. Опе
ратор усреднения задан формулой h(a)f(x)=f(x+1).

Это усреднение очевидно обратимое: f(x)=

=h(a)f(x–1). Таким образом, теорема 3 действительно не дает необходимых условий обратимости АСУГ.

Программные продукты и системы
№ 4, 2011 г.

7

Алгебра, порожденная векторным 

усреднением на графе

Компонента векторного усреднения на графе 

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

Заметим, что любое произведение конечного 

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

Если исходная система на графе была ацикли
ческой, любое ее расширение полиномами в соответственной алгебре сохраняет ацикличность. Это 
следует из принципа преобразования соответственного графа. Если в исходном графе не было 
циклов длиннее единицы, последовательное соединение ребер этого графа не породит цикла. В 
частности, если вершина исходного соответственного графа была непетлевой, и в новом графе она 
останется непетлевой. Таким образом, полиноми
альное расширение АСУГ не может дать пополнения этой системы до обратимой по формуле (21).

Подводя итоги, отметим, что в работе введено 

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

Таким образом, решена задача получения 

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

Литература

1. Гельфанд И.М., Гиндикин С.Г., Граев М.И. Избранные 

задачи интегральной геометрии. М.: Добросвет, 2000. 208 с.

2. Гельфанд И.М., Граев М.И., Виленкин Н.Я. Обобщен
ные функции / Интегральная геометрия и связанные проблемы 
теории представлений. М.: Физматгиз, 1962. Т. 5.

3. Коганов А.В. Комбинаторные методы интегральной 

геометрии: в сб. Математика. Компьютер. Образование. Вып. 
12. Ч. 2. М.–Ижевск: НИЦ «Регулярная и хаотическая динамика». 2005. С. 746–758.

4. Граев М.И., Коганов А.В. Алгоритмы восстановления 

функции через ее усреднения по подмножествам // Программные продукты и системы. 2008. № 4. С. 33–38. 

5. Коганов А.В. Интегральная геометрия на системах по
крытий // Математические исследования: сб. тр.; [под ред. 
акад. В.Б. Бетелина]. М.: НИИСИ РАН, 2005. С. 197–230. 

УДК 004.4

ПРОГРАММА ДЛЯ АВТОМАТИЧЕСКОГО СОЗДАНИЯ И ПРОВЕРКИ
ИСХОДНЫХ МАТЕРИАЛОВ КОНСТРУКТОРСКОЙ ДОКУМЕНТАЦИИ

А.А. Подковыров (НИИСИ РАН, barfey@mail.ru)

Описана программа, позволяющая за несколько минут выполнить большинство операций, которые невозможно 

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

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

конструкторской документации, генерация документации, спецификация, перечень компонентов. 

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

Программные продукты и системы
№ 4, 2011 г.

8

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

Для решения этой проблемы была разработана 

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

Основными преимуществами программы яв
ляются:


адаптация системы управления под любое 

приложение 
операционной 
системы 
Windows

(поддерживаются Windows XP, Windows Vista и 
Windows 7);


генерация скриптов системы проектирова
ния для их выполнения без участия оператора;


пакетное исполнение операций (под паке
том в данном случае понимается перечень операций для создания определенного типа документа 
или их набора);


четкая структура выполнения заданий для 

поиска ошибок в их работе;


встроенные конверторы кодировок шриф
тов кириллицы DOS-WIN-DOS;

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


работа со списком компонентов в виде таб
лицы БД;


импорт БД и списков из Microsoft Excel;


обновление информации о компонентах;


проверка состояния проекта и поиск оши
бок в нем;


контроль использования компонентов (кон
троль доступности для использования);


работа с проектами, имеющими несколько 

исполнений;


шаблон для сохранения данных о пользова
теле;


предпросмотр и печать документов с со
блюдением требуемого формата.

Работоспособность
программы
проверялась 

при использовании ее для создания технической 
документации проекта печатной платы, разработанного в системе автоматизированного проектирования печатных плат Cadence Allegro PCB 
Designer [1].

Работа с программой разделена на пять незави
симых этапов (этапы следуют в рекомендуемом 
для выполнения порядке):


контроль используемых компонентов;


проверка готовности печатной платы для 

производства;


создание спецификации;


генерация документации с возможностью 

выбора необходимых документов;


создание разностной спецификации (для 

проектов, имеющих несколько версий).

Программу можно использовать частично, для 

генерации только требуемой документации.

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

Контроль компонентов, входящих в электриче
скую схему проекта, необходим для выяснения их 
текущего состояния: «можно использовать», «использование ограничено», «не использовать». Для 
работы используется БД текущих компонентов в 
формате MS Excel. Если БД неактуальна, программа предложит обновить ее. Далее можно 
сравнить список компонентов электрической схемы (генерируется системой Cadence) с БД используемых элементов и увидеть результаты работы в 
окне. Для удобства из результатов исключаются
компоненты, которые «можно использовать», чтобы увидеть лишь требующие проверки. Обычно в 
проекте должны присутствовать только компоненты, которые «можно использовать». Если в 
проекте есть компоненты, использование которых 
ограничено, необходимо вернуться к этапу разработки принципиальной схемы и изменить ее. Наличие компонентов с ограниченным использованием согласуется с руководителем работ.

После завершения разработки проекта следует 

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

Программные продукты и системы
№ 4, 2011 г.

9

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

Приведение таблицы компонентов, выводимой 

системой проектирования, к стандартизованному 
формату спецификации на печатную плату всегда 
отнимает много времени. Благодаря разработанной программе, выводимая системой Cadence информация отображается как таблица с порядком 
столбцов готовой спецификации, а не в виде 
сплошного неотформатированного списка с разделителями. Поля и их последовательность соответствуют виду готовой спецификации и расположены на тех же местах. Таблица редактируется и сохраняется в промежуточный формат (для удобства 
использования в дальнейшем, например, при составлении разностной спецификации), имеется 
список стандартных групп, сортировка компонентов по группам и по очередности групп. Спецификация приобретает вид, требуемый ГОСТом, при 
необходимости в конце добавляется расшифровка 
сокращений названий фирм. Добавлена возможность замены названий для соответствия их библиотеке с русскими компонентами, так как САПР 
может не поддерживать кириллицу. Кроме того,
можно заменить название и фирму-производителя
для часто используемых компонентов (обычно это 
резисторы и конденсаторы). Названия таких компонентов заменяются их характеристиками, а в 
качестве фирмы-производителя указывается «любая» (any). Предусмотрена возможность прямого 
вывода готовой спецификации на печать с ее 
предварительным просмотром. Формат и шрифт 
подобраны для правильного отображения на листе 
формата А4. Также имеется возможность генерации перечня компонентов для конструкторской 
документации в формате csv (открывается MS 
Excel).

Для сохранения спецификации разработан 

промежуточный файл, содержащий отредактированный список компонентов, а также всю требуемую для создания спецификации по ГОСТу информацию. Необходимость в этом файле обусловлена несколькими причинами:


готовая спецификация очень трудно подда
ется редактированию; 


не все требуемые компоненты отображают
ся в списке компонентов, выдаваемом системой 
проектирования, их надо будет добавить вручную;

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


информация о разработчике и ведущем 

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

быть размещены вместе со списком компонентов;

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


метаданные, сохраняемые в файле вместе с 

остальными данными, используются для настройки программы.

Генерация документации – основной этап ра
боты программы. Он реализован в виде отдельных 
пакетных задач, которые могут выполняться независимо друг от друга. Используемые в программе
методы


дают возможность экономить время и по
лучать только требуемые технические документы, 
а не создавать всю документацию за один раз; 


позволяют легко проследить процессы, вы
полняемые в данный момент программой, и выявить конкретный шаг, на котором происходит 
ошибка; 


допускают 
возможность
редактировать 

только те пакетные задачи, изменение которых 
необходимо в связи с новыми требованиями производства, а не весь этап генерации документации.

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

 подготовка системы (очистка от любых 

предыдущих установок, которые могут привести к 
неправильному результату, установка скриптов и 
конфигурационных файлов);

 работа с системой (запуск системы и от
крытие проекта печатной платы, выполнение ранее предустановленных скриптов и операций, завершение работы системы);

 обработка полученных результатов (обра
ботка результатов, очистка системы от промежуточных файлов и файлов-скриптов, вывод результатов в окне программы и сохранение их на диск в 
текущей директории проекта).

Требование очистки системы до ее запуска 

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

Пакетные задачи выполняются отдельным про
граммным потоком [2]. Такой принцип позволяет 
более гибко управлять работой программы и дает 
возможность прервать ее практически в любой 
момент. После запуска САПР программа отправляет на исполнение скрипт менеджера автоматизации (nncron), он, в свою очередь, используя 
эмуляции нажатия клавиатуры, производит манипуляции с системой, выполняя необходимые операции. Для увеличения производительности ино

Программные продукты и системы
№ 4, 2011 г.

10

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

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

Программа поддерживает сложные проекты, 

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

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

Использование данной программы позволило 

сократить время подготовки технической документации в САПР печатных плат Cadence Allegro 
PCB Designer с 1–2 дней (для сложных проектов) 
до 15 минут при условии, что проект печатной 
платы не содержит серьезных ошибок.

Литература

1.
URL: http://www.cadence.com/products/pcb/pcb_design/

pages/default.aspx (дата обращения: 17.07.2011).

2.
Шамис В.А. Borland C++ Builder 6. Для профессиона
лов. СПб: Питер, 2005. 798 с.

УДК 004.416.6/6

ИНКРЕМЕНТАЛЬНОЕ ТИРАЖИРОВАНИЕ ДАННЫХ 

ПРИ ВЗАИМОДЕЙСТВИИ ИНФОРМАЦИОННЫХ СИСТЕМ

А.Г. Прилипко (НИИСИ РАН, prag19@mail.ru)

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

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

Многие предприятия и организации использу
ют в своей работе сразу несколько информационных программных систем [1], в частности, системы бухгалтерского, управленческого и налогового 
учета. Поэтому важными являются интеграция и 
согласованность находящихся в них данных [2]. 
Часто для работы одной системы требуются данные из другой системы, для этого необходимо организовать их передачу из одной или нескольких 
систем-источников в систему-приемник, которых 
также может быть несколько.

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

В подобной ситуации самое простое – заново 

повторить весь цикл передачи и обработки данных. Однако в тех случаях, когда объем переносимых данных значителен, а в процессе их обра
ботки требуется непосредственное участие человека (например, визуальный просмотр промежуточных результатов обработки), повторение полного цикла обработки будет неоправданно трудозатратным. Кроме того, необходимо принимать во 
внимание и возможные требования по срочности 
получения конечного результата обработки.

В таких случаях наиболее подходит метод ин
крементального тиражирования данных (то есть 
их перенос в одну или несколько систем), характерными особенностями которого являются:


периодическая передача порций данных из 

системы-источника в систему-приемник;


отслеживание изменений в очередной пор
ции данных по сравнению с ранее переданными;


наличие контрольных событий, после кото
рых данные за некоторый период считаются неизменяемыми;


просмотр и проверка найденных изменений 

с возможностью их подтверждения (приема) или 
отказа от них;


обработка только изменившихся данных.

Приведем ряд примеров применения метода 

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

Программные продукты и системы
№ 4, 2011 г.

11

Рассмотрим задачу переноса информации о 

платежах из системы бухгалтерского учета в системы учета затрат и бюджетирования, являющиеся 
частью общей системы АСУ НИИСИ [3]. Необходимо отслеживать изменения в переносимых данных, при том что их формат со временем может 
изменяться. Отметим, что требуется не только переносить данные, но и учитывать историю их использования в других системах.

Для хранения информации о платежах в реля
ционной базе данных АСУ НИИСИ, куда входят 
целевые системы, создана таблица платежей, в которую периодически переносятся преобразованные к нужному виду актуальные данные из таблиц 
бухгалтерской системы (см. рис.). Во время переноса дополнительно определяется, появились ли 
новые платежи, были ли какие-то из них удалены, 
изменилось ли их содержание. Если появляется 
новый платеж, он через таблицу платежей попадает в целевую таблицу. Под таковой понимается 
таблица, в которой хранится информация пользователя, необходимая для решения конкретной задачи, и в определенные поля которой переносятся 
данные о платежах. Идентификатор записи в таблице платежей остается при этом неизменным, поэтому ссылки на записи в таблице платежей из целевых таблиц менять не требуется. В то же время 
записи об удалении платежей и изменениях уже 
существующих дополнительно помещаются в таблицу изменений, на записи в которой и указывает 
дополнительное поле в целевых таблицах. 

В дальнейшем эти таблицы могут просмотреть

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

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

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

Этот подход оказался более эффективным по 

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

АСУ НИИСИ 

Cистемы учета затрат и бюджетирования

Таблицы-источники
Таблица платежей

id

Данные о 
платеже

Таблица изменений

Целевые таблицы

Перенос 

актуальных 

данных

id

fk2

fk1

Перенос данных

о платежах

id

fk

Информация 

об 

изменениях

Данные о 
платеже
Другие 
данные

Перенос информации о платежах

Программные продукты и системы
№ 4, 2011 г.

12

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

Обратим внимание на хранение истории изме
нений и действий пользователя в системе. Для 
этого при изменении некоторой записи в таблице 
в специальную таблицу заносится информация о 
том, кто и когда произвел изменение данной записи с указанием уникального идентификатора таблицы и записи, а также предыдущее значение поля 
или содержимое всей записи в виде текстовой 
строки в XML-формате. Такой способ хранения 
оказывается достаточно экономичным, поскольку 
хранятся только явно сделанные пользователями 
изменения. Кроме того, в этой таблице фиксируются и другие события, происходящие в системе, 
в том числе информация о действиях пользователя, связанных с входом или выходом из соответствующей информационной системы, формированием отчетов, вызовом поисковых запросов.

Хранение истории изменений записей в табли
цах БД полезно и при определении того, кто и когда вносил те или иные изменения, например, при 
электронном согласовании документов, хранящихся в информационной системе. Кроме того, 
дополнительно появляется возможность реализовать функцию откатки, не внося для этого специальные изменения в структуру таблиц информационной БД.

Следующий пример – расчет налога на при
быль по данным бухгалтерии. Одним из его этапов является формирование регистров налогового 
учета – документов с обоснованием затрат, используемых при расчете налога на прибыль.

В стандартных системах для бухгалтерского 

учета в бюджетных учреждениях (в частности, 1С:
Предприятие 7.7. Конфигурация «Бухгалтерия для 
бюджетных учреждений») отсутствуют встроенные развитые средства учета затрат для налогового учета. Их реализация в рамках бухгалтерской 
системы требует существенных доработок и приводит к значительным трудозатратам при сопровождении и обновлении версий самой бухгалтерской системы. Оказалось, что более эффективным 
решением этой задачи является разработка пакета 
специализированных утилит для формирования 
налоговых регистров. Сначала необходимая бухгалтерская информация за отчетный квартал выгружается из системы бухгалтерского учета в виде 
файла с данными о затратах, снабженными дополнительной автоматической разметкой. Далее информация из этого файла переносится в налоговый регистр, содержащий данные о затратах с 
начала года, после чего ответственное лицо просматривает и уточняет разметку в налоговом ре
гистре, корректирует данные и удаляет не подлежащую налоговому учету информацию. После 
обработки рядом программ формируется окончательный вариант отчетного налогового регистра.

Поскольку подготовка налоговых регистров 

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

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

Рассмотрим еще одну задачу – перенос инфор
мации о движении материалов из бухгалтерской 
системы в специализированную информационную 
систему «Учет движения материалов», созданную 
в рамках АСУ НИИСИ и помогающую при списании материалов по завершении договора определять номера документов поставщиков материалов 
и цены, по которым они были получены.

Здесь в качестве исходных данных выступают 

внутренние бухгалтерские требования-накладные, 
содержащие информацию о выдаче и движении 
материалов. Необходимо найти соответствующие 
приемные акты, в комментариях к которым указаны номера документов и организации-поставщики 
этих материалов. Ситуация осложняется тем, что 
указанные документы зачастую были созданы в 
разные годы и хранятся в разных бухгалтерских 
системах.

Информация, сохраняемая в системе учета 

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

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