Кратчайшие пути от фиксированной вершины

Вопрос 40: Признаки безопасности современных ИС

Для решения проблем безопасности информации современные ИС должны обладать следующими основными признаками:

· наличием информации различной степени конфиденциальности;

· обеспечением криптографической защиты информации различной степени конфиденциальности при передаче данных;

· иерархичностью полномочий субъектов доступа к программам к компонентам ИС (к файлам-серверам, каналам связи и т.п.);

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

· наличием механизма регистрации и учета попыток несанкционированного доступа, событий в ИС и документов, выводимых на печать;

· обязательным обеспечением целостности программного обеспечения и информации в ИС;

· наличием средств восстановления системы защиты информации;

· обязательным учетом магнитных носителей;

· наличием физической охраны средств вычислительной техники и магнитных носителей;

· наличием специальной службы информационной безопасности системы.

[1] Под организацией будем понимать сообщество людей, объединенных общими целями и использующих общие материальные и финансовые средства для производства материальных и информационных продуктов и услуг

[2] Ovod.pdf

Большинство известных алгоритмов нахождения расстояния между двумя фик­сированными вершинами s и t опирается на действия, которые в общих чертах можно представить следующим образом: при данной матрице весов дуг A[u,v], u,v є V. вычисляет некоторые верхние ограничения

D[u] на расстояния от s до всех вершин v єV. Каждый раз, когда мы устанавливаем, что D[u] + A[u,v] <D[v], (3.2) оценку D[v] улучшаем: D[u]:= D[u] + A[u,v].

Процесс прерывается, когда дальнейшее улучшение ни одного из ограничений невозможно. Легко можно показать, что значение каждой из переменных D[u] равно тогда d(s,v) -- расстоянию от.s до v. Заметим, что, для того чтобы определить расстояние от.s до t, мы вычисляем здесь расстояния от s до всех вершин графа. Не известен ни один алгоритм нахождения расстояния между двумя фиксированными вершинами, который был бы существенным образом более эффективным, нежели известные алгоритмы определения расстояния от фиксированной вершины до всех остальных. Описанная нами общая схема является неполной, так как она не определя­ет очередности, в которой выбираются вершины и и v для проверки условия (3.2). Эта очередность оказывает, как будет доказано, очень сильное влияние на эффективность алгоритма. Опишем теперь более детально методы нахождения расстояния от фиксированной вершины, называемой источников его всегда будем обозначать через s, до всех остальных вершин графа. Сначала представим алгоритм для общего случая, в котором предполага­ем только отсутствие контуров с отрицательной длиной. С этим алгоритмом обычно связывают имена Л.Р. Форда [22| и Р.Е. Беллмана |3|.

Алгоритм 3.2. (Нахождение расстояния от источника до всех вершин -метод Форда-Беллмана.)

Данные: Ориентированный граф <V,E> с п вершинами с выделенным источ­ником s є V, матрица весов дуг А[u,v], u,v є V (граф не содержит контуров отрицательной длины).

Результаты: Расстояния от источника до всех вершин графа: D[o] = d(s,v), v є V. 1. begin 2. for v єV do D[v]:= A[s,v]; D[s]:= 0; 3. for к:= 1 to n - 2 do 4. for v є V\{s} do o. for u є V do D[«]:= min(D[u], D[u] + A[u, v]) 6. end

Докажем правильность этого алгоритма. Для этого обозначим через длину кратчайшего из путей из s в v, содержащих не более т дуг , если не существует ни одного такого пути). Тогда имеем:

В самом деле, для каждого и є V очевидно имеем

причем равенство появляется, когда и является предпоследней вершиной произвольного кратчайшего пути из s в v.

Покажем теперь, что если при входе в очередную итерацию

то по окончании этой итерации

В самом деле, предполагая выполнение условия (3.4) и анализируя действие оператора в строке 5, мы видим, что по окончании нашей итерации цикла 3 имеем

что, принимая во внимание равенство (3.3), дает условие (3.5).

Отметим, что при входе в цикл 3 имеем

следовательно, после выполнения п — 2 итераций этого цикла будут выполняться неравенства Теперь достаточно показать, что . Это справедливо, поскольку каждый путь более чем с n-1 дугами содер­жит контур, устранение которого не увеличивает длины пути (ведь мы пред­полагаем отсутствие контуров отрицательной длины). Тем самым закончено доказательство корректности алгоритма. Очевидно, что временная сложность алгоритма есть . Мы можем, конечно, закончить вычисления, когда вы­полнение цикла 4 не вызывает изменения ни одной из переменных D[v], v є V. Это может наступить для к < n-2, однако такая модификация алгоритма не изменяет существенным образом его сложности. Для редких графов удобнее представлять граф списками инцидентности ПРЕДШ[u], v є V. Заменяя строку 5 на:

for и є ПРЕДШ[v] do D[v]:= min(D[w], D[u] + A[a, v]), получаем алгоритм со сложностью О(nт). Работа алгоритма Форда-Беллмана проиллюстрирована на рис. 3.1 (V = {1,.... 5). веса дуг даны числами в скобках, циклы 4 и 5 выполняются в порядке возрастания номеров вершин).

Дата добавления: 2014-01-11