Вычислительная техника и прикладная математика

• Название: Вычислительная техника и прикладная математика
• Дата: 12.05.2023
• Размер: 0.78 Mb.
• Имя файла: razdel-3-33.pdf
• Тип: Документы; #1125413
• страница: 4 из 6

Теорема 4. Если nw
i,j
< w
i,j
и e
i,j

E
T
, то без изменения останутся кратчайшие пути и оценки их длин для вершин множества V
(Vi)
Доказательство. Пусть уменьшился вес ребра e
i,j

E
R
, которое не входит ни в один кратчайший путь. Допустим, что это ребро входит в путь

i,k


i
и

j,p


j
. Если изменившееся ребро e
i,j
не уменьшает оценок обеих инцидентных ему вершин v
i
и v
j
, т.е. d
i,k

d
i
и d
j,p

d
j
, дерево кратчайших путей не изменится.
Действительно, рассматриваемое ребро оказывает влияние, прежде всего на инцидентные ему вершины множества V. Если включение ребра e
i,j
в дерево не уменьшает оценок пути d
i
, d
j
, то такое включение только увеличит оценки вершин. Т.к. существовавшие до изменения пути до этих вершин имели меньшую длину, то данное ребро не включается в дерево кратчайших путей. Если включение этого ребра приводит к уменьшению оценки какой-либо из инцидентных вершин, например
v
i
, то эта оценка d
i,k
будет оценкой кратчайшего пути до вершины v
i
, и ребро e
i,j
войдет в искомое дерево кратчайших путей. Это происходит в силу того, что после изменения не существует иного кратчайшего пути

i
до вершины v
i
, кроме пути

i,k
, содержащего ребро
e
i,j
Этот кратчайший путь

i,k
не будет существовать, если не будет кратчайших путей до всех промежуточных вершин v
p

V
(Vi)
этого пути.
Кратчайшие пути до остальных вершин графа станут «недействительными», т. е. невозможно будет сказать, останутся они такими же или кратчайший путь до них будет включать изменившееся ребро. Теорема доказана.
Теорема 5. Если nw
i,j
> w
i,j
и e
i,j

E
T
и
nw
i,j
> nw
i,j
t
(точки вхождения в дерево), то изменению могут подвергнуться кратчайшие пути и оценки их длин для вершин V
Т
(Vj)
и новые кратчайшие пути к этим вершинам будут проходить через ребра, состоящие в отношении парного перехода к ребрам этих вершин.
Доказательство. Пусть увеличился вес ребра e
i,j

E
T
, которое входит, по крайней мере, в один кратчайший путь

k
, например в

k,p
Согласно теореме 1 вершины v
k
, в кратчайшие пути до которых ребро e
i,j
не входит, будут составлять множество V
Т
вершин, кратчайшие пути до которых после изменения не изменятся
(не изменится последовательность ребер и величины кратчайших путей). Для вершин V
Т
(Vj)
среди парных переходов соответствующих этим вершинам будут находиться ребра, имеющие минимальную длину пути к этим вершинам.
Теорема доказана.
Следствие. При увеличении веса ребра, входящего в дерево кратчайших путей для вершин V
Т
(Vj)
, маршрутная степень которых больше двух, новые кратчайшие пути будут проходить через ребра, состоящие в отношении парного перехода к ребрам, входящим в исходный граф.
Теорема 6. Если nw
i,j
< w
i,j
и e
i,j

E
T
и новое значение nw
i,j
< nw
i,j
t
(точки вхождения в дерево), то новые кратчайшие пути к вершинам множества v

V
Т
(Vj)

V
(Vi)
будут проходить через ребра, состоящие в отношении парного перехода к ребрам этих вершин.
Доказательство. Пусть уменьшился вес ребра e
i,j

E
R
, которое не входит ни в один кратчайший путь. Согласно с теоремой 4 без изменения останутся кратчайшие пути и оценки их длин для вершин множества V
(Vi)
. Т.к nw
i,j
<
nw
i,j
, то включение этого ребра приводит к уменьшению оценки какой-либо из инцидент- ных вершин, например v
i
, и эта оценка d
i,k
будет оценкой кратчайшего пути до вершины v
i
, и ребро e
i,j
войдет в искомое дерево кратчайших путей. Это происходит в силу того, что после изменения не существует иного кратчайшего пути

i
до вершины v
i
, кроме пути

i,k
, содержащего ребро e
i,j
. Этот кратчайший путь

i,k
не будет существовать, если не будет кратчайших путей до всех промежуточных вершин v
p

V
(Vi)
этого пути. Теорема доказана.
Следствие. При уменьшении веса ребра, не входящего в дерево кратчайших путей для вершин V
Т
(Vj)

V
(Vi)
, маршрутная степень которых больше двух, новые кратчайшие пути будут проходить через ребра, состоящие в отношении парного перехода к ребрам, вхо- дящим в исходный граф.
Использование доказанных выше теорем позволяет разработать алгоритм, уменьшающий размерность задачи поиска кратчайших путей в условиях, когда пропускная способность линий связи и структура сети динамически меняется.
Каждую вершину в алгоритме будет описывать структура данных VERTEX. Данная структура содержит индекс, равный индексу соответствующей вершины v
i
; указатель на родительскую вершину v i
.p (для корневой вершины он будет содержать null v i
.p=null), оценку длины оптимального маршрута v i
.d и массив указателей на потомков по иерархии v i
.c j

ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
53
(для вершин–листьев он пустой). Полученное в процессе работы алгоритма дерево T будет представлять собой массив объектов типа
VERTEX. Вершина v i
, i = 1..||V||, T.vs – начальная вершина. Каждое ребро графа G описывается структурой, которая определяется весом ребра e i
.w и указателями на инцидентные вершины e i
.v1, e i
.v2.
Для поиска оптимальных маршрутов будем применять алгоритм Дейкстры.
//Алгоритм Дейкстры. T – структура данных дерева оптимальных маршрутов, V – множество вершин графа, vs – начальная вершина.
DeicstraAlg(T,V,vs)
1.
Initialize(V,vs)
2.
Q.add(V,vs)
3.
Пока Q  
4. vm = Extract-Min(Q);
5.
T.add(vm);
6.
Для всех инцидентных vm ребер vk
7.
Если d[vm.i]>d[vk.i]+w(vk,vm) то
8. d[vm.i] = d[vk.i] + w(vk,vm);
9. p[vm.i] = vk;
Конец Если
Конец Для
Конец Пока
Конец
В приведенной процедуре используется функция Extract – Min, возвращающая объект с минимальным ключом. Реализация данной функции и ее трудоемкость зависят от способа определения списка (очереди). Алгоритм вычис- ляет значения массивов d и p оценок длин оптимальных маршрутов и указателей на роди- тельские таблицы соответственно. Полученные массивы необходимо сохранить.
// Процедура сохранения массивов
SaveAr(v,i)
1.
Если i=0 то
2. v.d1:=d;
3. v.p1:=p;
Иначе
4. v.d2:=d;
5. v.p2:=p;
Конец Если
Конец
Для ребер, участвующих в построении опти- мальных маршрутов, является целесообразным проводить расчет для инцидентных вершин, лежащих ниже по иерархии.
// Процедура нахождения деревьев оптимальных маршрутов для всех вершин графа
GetSPT(T,V,vs)
1.
Q.Add(vs)
2.
Пока Q
3. v:=Q.Get
4.
Для всех v.ci
5.
Q.Add(v.ci.v2)
Конец Для
6.
Если v<>vs то
7. e:=E(v,v.p)
8. tw:=e.w;
9. e.w:=0;
10.
DeicstraAlg(T,V,v)
11.
SaveAr(v,0)
12. e.w:=M
13.
DeicstraAlg(T,V,v)
14.
SaveAr(v,1)
Конец Если
Конец Пока
Конец
В приведенной процедуре М – число, принятое за максимальное в данной системе.
Процедура нахождения деревьев оптимальных маршрутов для графа обходит все вершины графа с формированием списков парных пере- ходов для каждой вершины.
От дерева оптимальных маршрутов из заданной вершины легко перейти к списку парных переходов. Оценки длин оптимальных маршрутов в данном случае будут соответст- вовать приращениям потенциала этой вершины.
При поиске оптимального маршрута особой обработки, как было сказано выше, заслуживает вариант уменьшения веса ребра, не входящего в оптимальный маршрут. В этом случае необхо- димо предварительно проверить вершины, лежа- щие выше по иерархии.
// Процедура проверки на включение в поддере- во вершины v вершин, лежащих выше по иерар- хии относительно вершины v
TestUp(v)
1. v2:=v.P
2.
Пока v2.d>v.d+E(v,v2)
3. v2.d:= v.d+E(v,v2)
4.
Для всех v2.Ci
5.
Если v2.Ci<>v то
6. v2.Ci.d:=v2.d+E(v2,v2.Ci)
Конец Если
Конец Для
7. v:=v2;
8. v2:=v2.P;
Конец Пока
Конец
Для проверки срабатывания парного пере- хода используется условие целесообразности включения ребра в дерево. Отдельно обраба- тываются случаи увеличения и уменьшения оценки длины оптимального маршрута.
// Процедура обработки изменения веса ребра будет выглядеть следующим образом:
PathPT(e,nw)

54
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
1. v1=e.v1 2. v2=e.v2 3.
Если v1.d>e.v2 то
4. v1=e.v2 5. v2=e.v1
Конец Если
6.
Если nw>e.w то
7. dt:=v2.d2 8. pt:=v2.p2 9.
Если not e.InTree то
10.
TestUp(v2)
Конец Если
Иначе
11. dt:=v2.d
12. pt:=v2.p
Конец Если
13.
Q.Add(vs)
14.
Пока Q
15. v:=Q.Get
16.
Для всех v.ci
17.
Q.Add(v.ci.v2)
Конец Для
18.
Если v<>vs то
19. Если v.p.d+E(v.p,v).w>pt[v.i].d+E(pt[v.i],v) то
20. v.p:= pt[v.i]
21. v.d:= pt[v.i].d+E(pt[v.i],v)
Конец Если
Конец Если
Конец Пока
Конец
Рассмотрим работу алгоритма адаптивной ускоренной маршрутизации. Укрупненная схема алгоритма имеет следующий вид.
Шаг 1. Для вершины, являющейся листом дере- ва, производится поиск всех парных переходов без ограничений. Эти списки для удобства дальнейшей работы привязываются к вершине, инцидентной рассматриваемому ребру и распо- ложенной ниже по иерархии.
Шаг 2. Если вершина не является листом дерева, то вычисляются парные переходы для этой вершины и выбираются лучшие значения потен- циалов парных переходов для потомков верши- ны и собственных парных переходов. Подобная процедура выполняется для формирования спис- ков парных переходов в случае увеличения и уменьшения веса ребра.
Шаг 3. Для каждой вершины формируется пол- ный список парных переходов. Число элементов в каждом их этих списков не превышает коли- чества вершин графа. Такое решение позволяет отказаться от предварительной сортировки по- тенциалов или приращений для парных пере- ходов без значительного усложнения алгоритма обработки изменения.
Шаг 4. Для каждой вершины формируется пол- ный список возможных маршрутов, проходящий через ребра, состоящие в отношении парного перехода, включая и ребра, входящие в дерево кратчайших путей.
Шаг 5. Анализируя полученную используемым протоколом маршрутизации информацию, опре- делить, произошло ли изменение метрики для какого-либо ребра: а) если да, то перейти к шагу 6; б) иначе - к шагу 5.
Шаг 6. Используя список парных переходов, определить, требуется ли сделать парный пере- ход: а) если да, то перейти к шагу 7; б) иначе – к шагу 9.
Шаг 7. Для каждой вершины, у которой в список возможных маршрутов входит ребро с изменив- шейся метрикой, определить путь минимальной длины и поместить его в дерево кратчайших путей, тем самым, построив новое дерево кратчайших путей на графе.
Шаг 8. а) передать пакеты по доступным эквивалентным маршрутам; б) установить флаг передачи.
Шаг 9. Пересчитать точки вхождения в дерево и переформировать список маршрутов замены для каждой изменившейся вершины.
Шаг 10. Перейти к шагу 5.
Работа составных частей алгоритма основы- вается на использовании доказанных выше теорем, следовательно, можно сделать вывод о корректности работы всего алгоритма в целом.
Проведем анализ сложности алгоритма адаптивной ускоренной маршрутизации, для чего найдем верхнюю и нижнюю оценки его трудоемкости. Для этого определим оценки для процедур, составляющих алгоритм. Для всех процедур было найдено количество повторений каждого шага и стоимость для верхней и нижней оценок трудоемкости. Трудоемкость модифици- рованного алгоритма Дейкстры составляет:

(N
2
log
2
N).
Результаты анализа трудоемкости остальных процедур сведены в таблицах 1 – 3.
Таблица 1 – Трудоемкость процедуры SaveAr
Верхняя оценка трудоемкости процедуры
SaveAr:

= 1 + 1 + 1 = 3, а нижняя оценка:

= 1 + 1 + 1 = 3.
№ шага п/п
(N)
(N)
Число повторений
Цена
Число повторений
Цена
1 1
1 1
1 2
1 1
0 1
3 1
1 0
1 4
0 1
1 1
5 0
1 1
1

ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
55
Таблица 2 – Трудоемкость процедуры GetSPT
Верхняя оценка трудоемкости процедуры
GetSPT:

= 15N + 2N
2
log
2
N + 1,
а нижняя оценка:

= 15N + 2N
2
log
2
N + 1.
Переходя к асимптотическим выражениям, получаем верхнюю оценку трудоемкости по- строения дерева кратчайших путей и получения дополнительной информации:

(N
2
log
2
N) и нижнюю оценку:

(N
2
log
2
N).
Тогда трудоемкость процедуры PathPT запи- шется следующим образом:
Верхняя оценка трудоемкости процедуры
PathPT:

= 10 + 5N + 3(N - 1) + 6N + 2 = 14N + 9, а нижняя оценка:

=8 + 5N + N – 1 = 6N + 7
Таким образом, удается рассчитать дерево кратчайших путей за линейное время в худшем случаи. Такой результат удается получить путем использования дополнительной информации о парных переходах.
Переходя к асимптотическим выражениям, получаем верхнюю оценку трудоемкости:

(N)
и нижнюю оценку:

(N).
Таким образом, разработанный алгоритм адаптивной ускоренной маршрутизации позво- ляет повысить эффективность функциониро- вания корпоративных сетей.
Таблица 3 – Трудоемкость процедуры PathPT
Заключение. Разработка алгоритма адап- тивной ускоренной маршрутизации позволяет повысить эффективность функционирования корпоративных сетей за счет уменьшения трудоемкости построения таблиц маршрути- зации до величины порядка O(N) в условиях динамически изменяющейся структуры корпора- тивной сети и характеристик линий связи.
Библиографический список
1. Куракин Д.В. Маршрутизаторы для глобаль- ных телекоммуникационных сетей и реализуемые в них алгоритмы // Информационные технологии.–
1996. №2.
2. Олифер В.Г., Олифер Н.А. Основы компью- терных сетей – СПб.: Питер, 2009. – 352 с.
№ шага п/п

(N)

(N)
Число повто- рений
Цена
Число повто- рений
Цена
1 1
1 1
1 2
N
1
N
1 3
N
1
N
1 4
N
1
N
1 5
N
1
N
1 6
N
1
N
1 7
N
1
N
1 8
N
1
N
1 9
N
1
N
1 10
N
Nlog
2
N
N
Nlog
2
N
11
N
3
N
3 12
N
1
N
1 13
N
Nlog
2
N
N
Nlog
2
N
14
N
3
N
3
№ шага п/п

(N)

(N)
Число повторений
Цена
Число повторений
Цена
1 1
1 1
1 2
1 1
1 1
3 1
1 1
1 4
1 1
0 1
5 1
1 0
1 6
1 1
1 1
7 1
1 0
1 8
1 1
0 1
9 1
1 1
1 10 1
6N+2 0
1 11 0
1 1
1 12 0
1 1
1 13 1
1 1
1 14
N
1
N
1 15
N
1
N
1 16
N
1
N
1 17
N
1
N
1 18
N
1
N
1 19
N-1 1
N-1 1
20
N-1 1
0 1
21
N-1 1
0 1

56
ISSN 1995-4565. Вестник РГРТУ. № 3 (выпуск 33). Рязань, 2010
УДК 519.718
В.В. Тарасов, Н.В. Елкина
К ЗАДАЧЕ КОНТРОЛЯ ВХОДНОЙ ИНФОРМАЦИИ НА СХЕМАХ
ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ С ЗАДЕРЖКАМИ
Рассмотрена задача контроля входной информации на схемах из функ-
циональных элементов в базисе


z
,
,
&, 
, где
z – тождественная функция
с задержками.
Ключевые слова: функции алгебры логики с задержками, надежность и
контроль, схемотехника.
Введение. В исследованиях [1-5] по теории функций алгебры логики (ФАЛ) с задержками основной задачей являлось изучение методов синтеза вычислительных устройств на предмет быстродействия. Цель статьи: рассмотрение задачи контроля входной информации на схемах из функциональных элементов в базисе


,
&, 
с добавлением к базису элемента, реализующего тождественную функцию
z с задержками, диф- ференцированными по входу. Пусть t – момент времени подачи сигнала (нуля или единицы) на вход элемента
z , тогда на выходе этот сигнал появляется в момент времени


t
, где
1



при подаче на вход нуля и
2



при подаче на вход единицы. Положим для определенности
2 1



. Под ФАЛ с задержками будем понимать пару функций

 



n
n
x
x
x
x
f
,...,
,
,...,
1 1

, где при одновременной подаче значений переменных
1 1


x
, …,
n
n
x


на входы ФАЛ


n
x
x
f
,...,
1
на выходе получаем значение


n
f

 ,...,
1
с временной внутренней задержкой


0
,...,
1




n
,
 
R




. ФАЛ с задержками



n
x
x
f
,
,...,
1


n
x
x ,...,
1

существенно зависит от переменной
i
x , если существует пара соседних наборов по переменной
i
x :


n
i
i








,...,
,
0
,
,...,

1 1
1
и


n
i
i








,...,
,
1
,
,...,

1 1
1
такие, что
 
 





f
f
либо
 
 







, в противном случае переменная
i
x называется фиктивной.
При добавлении или изъятии фиктивных переменных у ФАЛ с задержками получив- шиеся функции не считаются равными.
Причиной этого служит следующий важный пример. Рассмотрим схему


y
x
S
,
(см. рисунок
1), реализующую функцию
x
, где вход
y
является фиктивным с традиционно функ- циональной точки зрения.
&
x
y