Покажем, что поиск одной индивидуальной маски можно свести к задаче о покрытии множества.
Пусть задана диагностическая информация в виде СПР и требуется найти индивидуальную маску для технического состояния $$s_k$$. Для каждой возможной точки проверки $$i:j$$ построим подмножество $$S_{i:j}$$ множества $$S$$, в которое внесем все технические состояния, отличающиеся от состояния $$s_k$$ при использовании точки проверки $$i:j$$. Таким образом, получим покрытие
$$ \tilde{S}=\{S_{1:1}, S_{1:2},\ldots, S_{1:m},\ldots, S_{|\tau|:m}\}$$множества $$S$$. Очевидно, что минимальному подпокрытию $$\tilde{S'}\subseteq\tilde{S}$$
$$ \tilde{S'}=\{S_{i_1:j_1}, S_{i_1:j_2},\ldots, S_{i_l:j_l}\}$$будет соответствовать минимальная индивидуальная маска
$$h=\{i_1:j_1, i_2:j_2,\ldots, i_l:j_l\}$$Задача нахождения минимального подпокрытия множества является $$NP$$-полной.
В [1] предлагается жадный алгоритм ее решения. Идея алгоритма состоит в следующем: строим $$\tilde{S'}_i\subseteq\tilde{S}$$, причем $$\tilde{S'}_0=\varnothing$$, а
$$\tilde{S'}_{k+1}$$ строится из
$$\tilde{S'}_{k}$$ добавлением элемента из $$\tilde{S}$$, который покрывает наибольшее количество элементов множества $$S$$, непокрытых элементами из
$$\tilde{S'}_{k}$$.
Временная сложность данного алгоритма составляет
$$O(|S|-1)^2m|\tau|)$$,
Так как поиск маски должен быть произведен для каждого технического состояния, общая временная сложность поиска всего множества индивидуальных масок составит $$O(|S|^3m|\tau|)$$. В целях обеспечения необходимого объема памяти для сохранения результатов потребуется $$O(|S|^2)$$ бит, что и является оценкой емкостной сложности поиска множества индивидуальных масок.
Ниже описывается алгоритм, предложенный в [2], который улучшит приведенную временную характеристику.
При описании алгоритма будем использовать следующие обозначения. Пусть $$S'$$ - некоторое подмножество множества технических состояний, $$i:j$$ - точка проверки, а $$b$$ - высказывание, истинность которого равна нулю (ложь) или единице (истина).
Тогда через $$amt(S',i:j,b)$$ обозначим количество технических состояний из множества $$S'$$, для которых значение в точке проверки $$i:j$$ равно значению истинности $$b$$. Обозначение $$\overline{b}$$ будет соответствовать логической
Алгоритм 2 ( Жадный алгоритм поиска множества индивидуальных масок ).
Вход: Словарь полной реакции; $$S$$ - множество технических состояний.
Выход: $$H$$ - множество индивидуальных масок.
Алгоритм $$MaskSet(S_1,S_2,J)$$ функционирует следующим образом:
Формирование индивидуальной маски с помощью алгоритма 2 для каждого конкретного технического состояния $$s_k$$ повторяет работу жадного алгоритма для поиска
Суть алгоритма 2 состоит в поиске индивидуальных масок одновременно для всех технических состояний. Основная идея, направленная на ускорение данного поиска, заключается в следующем. Часто индивидуальные маски для разных технических состояний имеют одинаковые элементы.
Например, когда на шаге 2 алгоритм $$MaskSet$$ находит точку проверки, по значению которой можно отличить все состояния из $$S'_1$$ от всех состояний из $$(S_1\cup S_2)\setminus(S'_1\cup S'_2)$$, то эта точка проверки должна быть включена во все маски, соответствующие состояниям из $$S'_1$$ (что и делается на шаге 4).
После этого необходимо дополнить эти маски так, чтобы они отличали друг от друга состояния из $$S'_1\cup S'_2$$ (первый
Аргумент $$S_1$$ алгоритма $$MaskSet$$ определяет набор технических состояний, для которых необходимо провести поиск индивидуальной маски. Объединение $$S_1\cup S_2$$ задает множество состояний, для которых должно быть введено отличие в масках для состояний из $$S_1$$. Аргумент $$S_2$$ определяет множество технических состояний, для которых маски уже были найдены. Последний аргумент алгоритма $$MaskSet$$ введен для упорядочения поиска точек проверки.
Рассмотрим работу алгоритма на примере схемы C17 и ДИ, заданной для этой схемы в виде СПР из табл. 27.5.
В табл. 32.1 - табл. 32.10, представленных ниже, иллюстрируется выбор точек проверки на шаге 2 в процедуре $$MaskSet$$ при сокращении ДИ для схемы С17.
На первом шаге алгоритма создается множество пустых масок
$$Н= \{h_i=\varnothing | 0\le i\le 8\}.$$На следующем шаге происходит вызов процедуры $$MaskSet$$:
$$ MaskSet(\{s_0, s_1, , s_2, s_3, s_4, s_5, s_6, s_7, s_8 \},\varnothing,9)$$производящая поиск точки проверки по значению величины $$J'$$ из вариантов, перечиcленных в табл. 32.1. Первому максимальному значению $$J'=7$$ соответствует точка проверки $$2:2$$ и значение $$b=1$$. Выбираем эту точку проверки. Для нее вычисляем $$S'_1=\{s_8\}$$ и $$S'_2=\varnothing$$. Добавляем точку проверки $$2:2$$ в маску $$h_8$$, после чего производятся рекурсивные вызовы.
$$MaskSet(\{s_8\},\varnothing,1)$$ - вызов завершается без внесения изменений в маски.
$$ MaskSet(\{s_0, s_1, , s_2, s_3, s_4, s_5, s_6, s_7\},\{ s_8 \},7)$$из той же табл. 32.1 выбираем следующее максимальное значение $$J'=7$$, соответствующее точке проверки $$4:1$$ и значению $$b=0$$ (значение $$J'=7$$, соответствующее точке проверки $$2:2$$ и значению $$b=1$$ не выбирается, так как $$amt(\{ s_0, s_1, , s_2, s_3, s_4, s_5, s_6, s_7 \},2:2,1)=0$$). Вычисляем $$S'_1=\{s_6\}$$, $$S'_2=\varnothing$$. Добавляем $$4:1$$ в маску $$h_6$$.
$$MaskSet(\{s_6\},\varnothing,1)$$ - вызов завершается без внесения изменений в маски.
$$ MaskSet(\{s_0, s_1, , s_2, s_3, s_4, s_5, s_7\},\{ s_6,s_8 \},7)$$- следующее максимальное значение $$J'$$ (не превышающее 7) в табл. 32.1 равно 5 и соответствует точке проверки $$2:1$$ и значению $$b=1$$. $$S'_1=\{s_1\}$$, $$S'_2=\{s_8\}$$. Добавляем $$2:1$$ в маску $$h_1$$.
$$MaskSet(\{s_0\},\{s_8\},2)$$- значения $$J'$$ для данного вызова приведены в табл. 32.2. Первое максимальное значение $$J'$$ равно 0 для точки проверки $$1:2$$ и значения $$b=0$$. $$S'_1=\{s_1\}$$, $$S'_2=\varnothing$$. Точка проверки $$1:2$$ добавляется в $$h_1$$.
$$MaskSet(\{s_1\},\varnothing,1)$$ - вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_1,s_8\},1)$$- вызов завершается без внесения изменений в маски.
$$ MaskSet(\{s_0,s_2,s_3,s_4,s_5,s_7\},\{s_1,s_6,s_8\},5)$$- следующее максимальное значение $$J'$$ (не превышающее 5) в табл. 32.1 равно 3 и соответствует точке проверки $$3:2$$ и значению $$b=0$$. $$S'_1=\{s_3,s_4,s_7\}$$, $$S'_2=\varnothing$$. Добавляем $$3:2$$ в маски $$h_3$$, $$h_4$$ и $$h_7$$.
$$MaskSet(\{s_3,s_4,s_7\},\varnothing,3)$$- значения $$J'$$ для этого вызова приведены в табл. 32.3. Первое максимальное значение $$J'$$ равно 1 и соответствует точке проверки $$1:1$$ и значению $$b=1$$. $$S'_1=\{s_7\}$$, $$S'_2=\varnothing$$. Вносим $$1:1$$ в $$h_7$$.
$$MaskSet(\{s_7\},\varnothing,1)$$ - вызов завершается без внесения изменений в маски.
$$ MaskSet(\{s_3,s_4\},\{s_7\},1)$$- из табл. 32.3 выбираем следующее значение $$J'=1$$ для $$1:2$$ и значения $$b=1$$. $$S'_1=\{s_4\}$$, $$S'_2=\varnothing$$. Вносим $$1:2$$ в $$h_4$$.
$$MaskSet(\{s_4\},\varnothing,1)$$ - вызов завершается без внесения изменений в маски.
$$ MaskSet(\{s_3\},\{s_4, s_7\},1)$$- из табл. 32.3 следующее значение $$J'$$, не превышающее 1 и для которого $$amt(\{s_3\},i:j,b)\ne0$$, равно -1 и соответствует точке проверки $$1:1$$ и значению $$b=0$$. $$S'_1=\{s_3\} $$, $$S'_2=\{s_4\}$$. Вносим $$1:1$$ в $$h_3$$.
$$MaskSet(\{s_3\},\{s_4\},\varnothing,2)$$- из табл. 7.4 выбираем $$J'=0$$ для точки проверки $$1:2$$ и значения $$b=0$$. $$S'_1=\{s_3\}$$, $$S'_2=\varnothing$$. Вносим $$1:2$$ в $$h_3$$.
$$MaskSet(\{s_3\},\varnothing,1)$$ - вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing, \{s_3,s_4\},1)$$ - вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing, \{s_3,s_4,s_7\},1)$$ - вызов завершается без внесения изменений в маски.
$$ MaskSet(\{s_0,s_2,s_5\},\{s_1,s_3,s_4,s_6,s_7,s_8\},3) $$- максимальное значение $$J'$$ не превышающее 3 в табл. 32.1 равно 1 и соответствует точке проверки $$1:1$$ и значению $$b=1$$. $$S'_1=\{s_0\}$$, $$S'_2=\{s_1,s_7,s_8\}$$. Точка проверки $$1:1$$ помещается в маску $$h_0$$.
$$MaskSet(\{s_0\},\{s_1,s_7,s_8\},4)$$- значения $$J'$$ для данного вызова приведены в табл. 32.5. Первое максимальное значение $$J'$$ равно 0 для точки проверки $$1:2$$ и значения $$b=1$$. $$S'_1=\{s_0\}$$, $$S'_2=\{s_8\}$$. Точка проверки $$1:2$$ добавляется в $$h_0$$.
$$MaskSet(\{s_0\},\{s_8\},2)$$- значения $$J'$$ для данного вызова приведены в табл. 32.6. Первое максимальное значение $$J'$$ равно 0 для точки проверки $$2:1$$ и значения $$b=0$$. $$S'_1=\{s_0\}$$, $$S'_2=\varnithing$$. Точка проверки $$2:1$$ добавляется в $$h_0$$.
$$MaskSet(\{s_0\},\varnothing,2)$$ - вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_0,s_8\},1)$$ - вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_0,s_1,s_7,s_8\},1)$$ - вызов завершается без внесения изменений в маски.
$$MaskSet(\{s_2,s_5\},\{s_0,s_1,s_3,s_4,s_6,s_7,s_8\},1)$$- максимальное значение $$J'$$ не превышающее 1 в табл. 32.1 равно 1 и соответствует точке проверки $$1:2$$ и значению $$b=0$$. $$S'_1=\{s_2\}$$, $$S'_2=\{s_1,s_3,s_7\}$$. Точка проверки $$1:2$$ помещается в маску $$h_2$$.
$$MaskSet(\{s_2\},\{s_1,s_3,s_7\},1)$$-значения $$J'$$ для данного вызова приведены в табл. 32.7. Первое максимальное значение $$J'$$ равно 0 для точки проверки $$1:1$$ и значения $$b=0$$. $$S'_1=\{s_2\}$$, $$S'_2=\{ s_3\}$$. Точка проверки $$1:1$$ добавляется в $$h_2$$.
$$MaskSet(\{s_2\},\{s_3\},2)$$- значения $$J'$$ для данного вызова приведены в табл. 32.8 . Первое максимальное значение $$J'$$ равно 0 для точки проверки $$3:1$$ и значения $$b=1$$. $$S'_1=\{s_2\}$$, $$S'_2=\varnothing$$. Точка проверки $$3:1$$ добавляется в $$h_2$$.
$$MaskSet(\{s_2\},\varnothing,1)$$- вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_2,s_3\},0)$$- вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_1,s_2,s_3,s_7\},0)$$- вызов завершается без внесения изменений в маски.
$$MaskSet(\{s_5\},\{s_0,s_1,s_2,s_3,s_4,s_6,s_7,s_8\},1)$$- следующее максимальное значение $$J'$$ не превышающее 1 в табл. 32.1 равно 1 и соответствует точке проверки $$3:1$$ и значению $$b=0$$. $$S'_1=\{s_5\}$$, $$S'_2=\{s_3,s_4,s_6\}$$. Точка проверки $$3:1$$ помещается в маску $$h_5$$.
$$MaskSet(\{s_5\},\{s_3,s_4,s_6 \},4)$$- значения $$J'$$ для данного вызова приведены в табл. 32.9. Первое максимальное значение $$J'$$ равно 0 для точки проверки $$3:2$$ и значения $$b=0$$. $$S'_1=\{s_5\}$$, $$S'_2=\{s_6\}$$. Точка проверки $$1:1$$ добавляется в $$h_5$$.
$$MaskSet(\{s_5\},\{s_6\},2)$$- значения $$J'$$ для данного вызова приведены в табл. 32.10. Первое максимальное значение $$J'$$ равно 0 для точки проверки $$4:1$$ и значения $$b=1$$. $$S'_1=\{s_5\}$$, $$S'_2=\varnothing$$. Точка проверки $$4:1$$ добавляется в $$h_5$$.
$$MaskSet(\{s_5\},\varnothing,1)$$- вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_5,s_6\},0)$$- вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_3,s_4,s_5,s_6\},0)$$- вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_0,s_1,s_2,s_3,s_4,s_5,s_6,s_7,s_8\},1)$$- вызов завершается без внесения изменений в маски.
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | -1 | 1 | 1 | -1 | -5 | 5 | -7 | 7 | 1 | -1 | 3 | -3 | 7 | -7 | -9 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | - | -2 | 0 | - | - | -2 | 0 | - | - | -2 | - | -2 | - | -2 | -2 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | -1 | 1 | -1 | 1 | -3 | - | -3 | - | -1 | 1 | -3 | - | - | -3 | -3 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | -2 | - | 0 | - | -2 | - | -2 | - | -2 | - | -2 | - | - | -2 | -2 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | - | -4 | - | 0 | 0 | - | -2 | - | - | -4 | - | -2 | - | -4 | -4 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | - | -2 | - | -2 | 0 | - | 0 | - | - | -2 | - | -2 | - | -2 | -2 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | 0 | - | -4 | - | -2 | - | -4 | - | - | -2 | - | 0 | - | -4 | -4 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | -2 | - | -2 | - | -2 | - | -2 | - | - | 0 | - | 0 | - | -2 | -2 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | -4 | - | - | -2 | -4 | - | -4 | - | -4 | - | - | 0 | - | -2 | -4 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | -2 | - | - | -2 | -2 | - | -2 | - | -2 | - | - | -2 | - | 0 | -2 | - |
Работа алгоритма закончена. В результате получены маски:
$$ h_0=\{1:1,1:2,2:1\},\\ h_1=\{1:2,2:1\},\\ h_2=\{1:1,1:2,3:1\},\\ h_3=\{1:1,1:2,3:2\},\\ h_4=\{1:2,3:2\},\\ h_5=\{3:1,3:2,4:1\},\\ h_6=\{4:1\},\\ h_7=\{1:1,3:2\},\\ h_8=\{2:2\}.$$Из приведенного примера ясно, что алгоритм не является точным, т. к. в маске $$h_2$$ точка проверки $$1:2$$ является избыточной.
Следующая теорема определяет верхнюю оценку объема совокупности индивидуальных масок, возвращаемой с помощью алгоритма 2.
Теорема 1. Суммарный объем совокупности индивидуальных масок, полученной с помощью алгоритма2, не превышает величины
$$M\cdot(1+ln(|S|-1)),$$где $$M$$ - суммарный объем совокупности минимальных индивидуальных масок заданного СПР.
Доказательство. Обозначим через $$\#MaskSet(S_1,S_2,J)$$ суммарное количество точек проверки, добавленное в совокупность масок $$H$$ в результате вызова $$MaskSet(S_1,S_2,J)$$.
Из определения алгоритма $$MaskSet$$ ясно, что
$$ \#MaskSet(S,\varnothing,|S|)=\sum\limits_{s\in S}\#MaskSet (\{s\},S\setminus\{s\},|S|-3). $$Запуск $$MaskSet (\{s\},S\setminus\{s\},|S|-3)$$ возвращает индивидуальную маску для технического состояния $$s$$. Работа такого запуска сводится к работе жадного алгоритма поиска
Известно [1], что размер покрытия множества $$P$$, полученного с помощью жадного алгоритма, превосходит размер
где $$M_s$$ - объем минимальной индивидуальной маски для технического состояния $$s$$. Из последнего неравенства следует, что
$$\# MaskSet(S,\varnothing,|S|) =\sum\limits_{s\in S}{M_s} \cdot(1+ln(|S|-1))= M\cdot(1+ln(|S|-1))$$где $$M=\sum\limits_{s\in S}{M_s}$$.
В следующей теореме оценивается сложность описанного алгоритма.
Теорема 2. Временная сложность алгоритма 2 составляет $$O(|S|^3m|\tau|)$$. Объем дополнительной памяти, необходимой для функционирования алгоритма 2, оценивается величиной $$O(|S|^2)$$.
Доказательство. Из формулировки алгоритма 2 ясно, что его сложность равна временной сложности вызова алгоритма $$MaskSet(S,\varnothing,|S|)$$. Оценим ее.
Заметим, что рекурсия по второму обращению к функции $$MaskSet$$ является концевой и эквивалентна итерационному процессу с параметром $$S_1$$ (с условием окончания процесса, как только выполнится $$|S_1|\le 1$$). Таким образом, стоит учитывать лишь первое обращение как
Максимально возможная глубина рекурсии по первому обращению $$MaskSet$$ равна $$|S|-1$$. При каждом таком рекурсивном вызове происходит уменьшение количества элементов в множестве $$S_1\cup S_2$$, вследствие чего можно оценить сверху объем необходимой памяти для вызова $$MaskSet(S,\varnothing,|S|)$$ величиной, кратной $$|S|(|S-1|)/2$$. Отсюда следует оценка емкостной сложности в формулировке теоремы.
Величиной той же кратности можно оценить стоимость поиска одной индивидуальной маски, а следовательно количество операций для поиска всей совокупности индивидуальных масок не превышает величины $$O(|S|^3m|\tau|)$$.
Жадный алгоритм- алгоритм, основанный на принятии локально оптимальных решений на каждом этапе его работы в расчете на возможность получения глобального оптимума.
Задача о минимальном покрытии множества - классическая NP-полная задача, формулируемая следующим образом: Задано множество $$U$$ и семейство его подмножеств $$S$$. Требуется найти такое семейство $$C\subseteq S$$,которое покрывает множество $$U$$.
В лекции описан жадный алгоритм поиска совокупности индивидуальных масок ДИ, базирующийся на сведении исходной задачи к классической задаче о минимальном покрытии множества.
Покажем, что поиск одной индивидуальной маски можно свести к задаче о покрытии множества.
Пусть задана диагностическая информация в виде СПР и требуется найти индивидуальную маску для технического состояния $$s_k$$. Для каждой возможной точки проверки $$i:j$$ построим подмножество $$S_{i:j}$$ множества $$S$$, в которое внесем все технические состояния, отличающиеся от состояния $$s_k$$ при использовании точки проверки $$i:j$$. Таким образом, получим покрытие
$$ \tilde{S}=\{S_{1:1}, S_{1:2},\ldots, S_{1:m},\ldots, S_{|\tau|:m}\}$$множества $$S$$. Очевидно, что минимальному подпокрытию $$\tilde{S'}\subseteq\tilde{S}$$
$$ \tilde{S'}=\{S_{i_1:j_1}, S_{i_1:j_2},\ldots, S_{i_l:j_l}\}$$будет соответствовать минимальная индивидуальная маска
$$h=\{i_1:j_1, i_2:j_2,\ldots, i_l:j_l\}$$Задача нахождения минимального подпокрытия множества является $$NP$$-полной.
В [1] предлагается жадный алгоритм ее решения. Идея алгоритма состоит в следующем: строим $$\tilde{S'}_i\subseteq\tilde{S}$$, причем $$\tilde{S'}_0=\varnothing$$, а
$$\tilde{S'}_{k+1}$$ строится из
$$\tilde{S'}_{k}$$ добавлением элемента из $$\tilde{S}$$, который покрывает наибольшее количество элементов множества $$S$$, непокрытых элементами из
$$\tilde{S'}_{k}$$.
Временная сложность данного алгоритма составляет
$$O(|S|-1)^2m|\tau|)$$,
Так как поиск маски должен быть произведен для каждого технического состояния, общая временная сложность поиска всего множества индивидуальных масок составит $$O(|S|^3m|\tau|)$$. В целях обеспечения необходимого объема памяти для сохранения результатов потребуется $$O(|S|^2)$$ бит, что и является оценкой емкостной сложности поиска множества индивидуальных масок.
Ниже описывается алгоритм, предложенный в [2], который улучшит приведенную временную характеристику.
При описании алгоритма будем использовать следующие обозначения. Пусть $$S'$$ - некоторое подмножество множества технических состояний, $$i:j$$ - точка проверки, а $$b$$ - высказывание, истинность которого равна нулю (ложь) или единице (истина).
Тогда через $$amt(S',i:j,b)$$ обозначим количество технических состояний из множества $$S'$$, для которых значение в точке проверки $$i:j$$ равно значению истинности $$b$$. Обозначение $$\overline{b}$$ будет соответствовать логической
Алгоритм 2 ( Жадный алгоритм поиска множества индивидуальных масок ).
Вход: Словарь полной реакции; $$S$$ - множество технических состояний.
Выход: $$H$$ - множество индивидуальных масок.
Алгоритм $$MaskSet(S_1,S_2,J)$$ функционирует следующим образом:
Формирование индивидуальной маски с помощью алгоритма 2 для каждого конкретного технического состояния $$s_k$$ повторяет работу жадного алгоритма для поиска
Суть алгоритма 2 состоит в поиске индивидуальных масок одновременно для всех технических состояний. Основная идея, направленная на ускорение данного поиска, заключается в следующем. Часто индивидуальные маски для разных технических состояний имеют одинаковые элементы.
Например, когда на шаге 2 алгоритм $$MaskSet$$ находит точку проверки, по значению которой можно отличить все состояния из $$S'_1$$ от всех состояний из $$(S_1\cup S_2)\setminus(S'_1\cup S'_2)$$, то эта точка проверки должна быть включена во все маски, соответствующие состояниям из $$S'_1$$ (что и делается на шаге 4).
После этого необходимо дополнить эти маски так, чтобы они отличали друг от друга состояния из $$S'_1\cup S'_2$$ (первый
Аргумент $$S_1$$ алгоритма $$MaskSet$$ определяет набор технических состояний, для которых необходимо провести поиск индивидуальной маски. Объединение $$S_1\cup S_2$$ задает множество состояний, для которых должно быть введено отличие в масках для состояний из $$S_1$$. Аргумент $$S_2$$ определяет множество технических состояний, для которых маски уже были найдены. Последний аргумент алгоритма $$MaskSet$$ введен для упорядочения поиска точек проверки.
Рассмотрим работу алгоритма на примере схемы C17 и ДИ, заданной для этой схемы в виде СПР из табл. 27.5.
В табл. 32.1 - табл. 32.10, представленных ниже, иллюстрируется выбор точек проверки на шаге 2 в процедуре $$MaskSet$$ при сокращении ДИ для схемы С17.
На первом шаге алгоритма создается множество пустых масок
$$Н= \{h_i=\varnothing | 0\le i\le 8\}.$$На следующем шаге происходит вызов процедуры $$MaskSet$$:
$$ MaskSet(\{s_0, s_1, , s_2, s_3, s_4, s_5, s_6, s_7, s_8 \},\varnothing,9)$$производящая поиск точки проверки по значению величины $$J'$$ из вариантов, перечиcленных в табл. 32.1. Первому максимальному значению $$J'=7$$ соответствует точка проверки $$2:2$$ и значение $$b=1$$. Выбираем эту точку проверки. Для нее вычисляем $$S'_1=\{s_8\}$$ и $$S'_2=\varnothing$$. Добавляем точку проверки $$2:2$$ в маску $$h_8$$, после чего производятся рекурсивные вызовы.
$$MaskSet(\{s_8\},\varnothing,1)$$ - вызов завершается без внесения изменений в маски.
$$ MaskSet(\{s_0, s_1, , s_2, s_3, s_4, s_5, s_6, s_7\},\{ s_8 \},7)$$из той же табл. 32.1 выбираем следующее максимальное значение $$J'=7$$, соответствующее точке проверки $$4:1$$ и значению $$b=0$$ (значение $$J'=7$$, соответствующее точке проверки $$2:2$$ и значению $$b=1$$ не выбирается, так как $$amt(\{ s_0, s_1, , s_2, s_3, s_4, s_5, s_6, s_7 \},2:2,1)=0$$). Вычисляем $$S'_1=\{s_6\}$$, $$S'_2=\varnothing$$. Добавляем $$4:1$$ в маску $$h_6$$.
$$MaskSet(\{s_6\},\varnothing,1)$$ - вызов завершается без внесения изменений в маски.
$$ MaskSet(\{s_0, s_1, , s_2, s_3, s_4, s_5, s_7\},\{ s_6,s_8 \},7)$$- следующее максимальное значение $$J'$$ (не превышающее 7) в табл. 32.1 равно 5 и соответствует точке проверки $$2:1$$ и значению $$b=1$$. $$S'_1=\{s_1\}$$, $$S'_2=\{s_8\}$$. Добавляем $$2:1$$ в маску $$h_1$$.
$$MaskSet(\{s_0\},\{s_8\},2)$$- значения $$J'$$ для данного вызова приведены в табл. 32.2. Первое максимальное значение $$J'$$ равно 0 для точки проверки $$1:2$$ и значения $$b=0$$. $$S'_1=\{s_1\}$$, $$S'_2=\varnothing$$. Точка проверки $$1:2$$ добавляется в $$h_1$$.
$$MaskSet(\{s_1\},\varnothing,1)$$ - вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_1,s_8\},1)$$- вызов завершается без внесения изменений в маски.
$$ MaskSet(\{s_0,s_2,s_3,s_4,s_5,s_7\},\{s_1,s_6,s_8\},5)$$- следующее максимальное значение $$J'$$ (не превышающее 5) в табл. 32.1 равно 3 и соответствует точке проверки $$3:2$$ и значению $$b=0$$. $$S'_1=\{s_3,s_4,s_7\}$$, $$S'_2=\varnothing$$. Добавляем $$3:2$$ в маски $$h_3$$, $$h_4$$ и $$h_7$$.
$$MaskSet(\{s_3,s_4,s_7\},\varnothing,3)$$- значения $$J'$$ для этого вызова приведены в табл. 32.3. Первое максимальное значение $$J'$$ равно 1 и соответствует точке проверки $$1:1$$ и значению $$b=1$$. $$S'_1=\{s_7\}$$, $$S'_2=\varnothing$$. Вносим $$1:1$$ в $$h_7$$.
$$MaskSet(\{s_7\},\varnothing,1)$$ - вызов завершается без внесения изменений в маски.
$$ MaskSet(\{s_3,s_4\},\{s_7\},1)$$- из табл. 32.3 выбираем следующее значение $$J'=1$$ для $$1:2$$ и значения $$b=1$$. $$S'_1=\{s_4\}$$, $$S'_2=\varnothing$$. Вносим $$1:2$$ в $$h_4$$.
$$MaskSet(\{s_4\},\varnothing,1)$$ - вызов завершается без внесения изменений в маски.
$$ MaskSet(\{s_3\},\{s_4, s_7\},1)$$- из табл. 32.3 следующее значение $$J'$$, не превышающее 1 и для которого $$amt(\{s_3\},i:j,b)\ne0$$, равно -1 и соответствует точке проверки $$1:1$$ и значению $$b=0$$. $$S'_1=\{s_3\} $$, $$S'_2=\{s_4\}$$. Вносим $$1:1$$ в $$h_3$$.
$$MaskSet(\{s_3\},\{s_4\},\varnothing,2)$$- из табл. 7.4 выбираем $$J'=0$$ для точки проверки $$1:2$$ и значения $$b=0$$. $$S'_1=\{s_3\}$$, $$S'_2=\varnothing$$. Вносим $$1:2$$ в $$h_3$$.
$$MaskSet(\{s_3\},\varnothing,1)$$ - вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing, \{s_3,s_4\},1)$$ - вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing, \{s_3,s_4,s_7\},1)$$ - вызов завершается без внесения изменений в маски.
$$ MaskSet(\{s_0,s_2,s_5\},\{s_1,s_3,s_4,s_6,s_7,s_8\},3) $$- максимальное значение $$J'$$ не превышающее 3 в табл. 32.1 равно 1 и соответствует точке проверки $$1:1$$ и значению $$b=1$$. $$S'_1=\{s_0\}$$, $$S'_2=\{s_1,s_7,s_8\}$$. Точка проверки $$1:1$$ помещается в маску $$h_0$$.
$$MaskSet(\{s_0\},\{s_1,s_7,s_8\},4)$$- значения $$J'$$ для данного вызова приведены в табл. 32.5. Первое максимальное значение $$J'$$ равно 0 для точки проверки $$1:2$$ и значения $$b=1$$. $$S'_1=\{s_0\}$$, $$S'_2=\{s_8\}$$. Точка проверки $$1:2$$ добавляется в $$h_0$$.
$$MaskSet(\{s_0\},\{s_8\},2)$$- значения $$J'$$ для данного вызова приведены в табл. 32.6. Первое максимальное значение $$J'$$ равно 0 для точки проверки $$2:1$$ и значения $$b=0$$. $$S'_1=\{s_0\}$$, $$S'_2=\varnithing$$. Точка проверки $$2:1$$ добавляется в $$h_0$$.
$$MaskSet(\{s_0\},\varnothing,2)$$ - вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_0,s_8\},1)$$ - вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_0,s_1,s_7,s_8\},1)$$ - вызов завершается без внесения изменений в маски.
$$MaskSet(\{s_2,s_5\},\{s_0,s_1,s_3,s_4,s_6,s_7,s_8\},1)$$- максимальное значение $$J'$$ не превышающее 1 в табл. 32.1 равно 1 и соответствует точке проверки $$1:2$$ и значению $$b=0$$. $$S'_1=\{s_2\}$$, $$S'_2=\{s_1,s_3,s_7\}$$. Точка проверки $$1:2$$ помещается в маску $$h_2$$.
$$MaskSet(\{s_2\},\{s_1,s_3,s_7\},1)$$-значения $$J'$$ для данного вызова приведены в табл. 32.7. Первое максимальное значение $$J'$$ равно 0 для точки проверки $$1:1$$ и значения $$b=0$$. $$S'_1=\{s_2\}$$, $$S'_2=\{ s_3\}$$. Точка проверки $$1:1$$ добавляется в $$h_2$$.
$$MaskSet(\{s_2\},\{s_3\},2)$$- значения $$J'$$ для данного вызова приведены в табл. 32.8 . Первое максимальное значение $$J'$$ равно 0 для точки проверки $$3:1$$ и значения $$b=1$$. $$S'_1=\{s_2\}$$, $$S'_2=\varnothing$$. Точка проверки $$3:1$$ добавляется в $$h_2$$.
$$MaskSet(\{s_2\},\varnothing,1)$$- вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_2,s_3\},0)$$- вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_1,s_2,s_3,s_7\},0)$$- вызов завершается без внесения изменений в маски.
$$MaskSet(\{s_5\},\{s_0,s_1,s_2,s_3,s_4,s_6,s_7,s_8\},1)$$- следующее максимальное значение $$J'$$ не превышающее 1 в табл. 32.1 равно 1 и соответствует точке проверки $$3:1$$ и значению $$b=0$$. $$S'_1=\{s_5\}$$, $$S'_2=\{s_3,s_4,s_6\}$$. Точка проверки $$3:1$$ помещается в маску $$h_5$$.
$$MaskSet(\{s_5\},\{s_3,s_4,s_6 \},4)$$- значения $$J'$$ для данного вызова приведены в табл. 32.9. Первое максимальное значение $$J'$$ равно 0 для точки проверки $$3:2$$ и значения $$b=0$$. $$S'_1=\{s_5\}$$, $$S'_2=\{s_6\}$$. Точка проверки $$1:1$$ добавляется в $$h_5$$.
$$MaskSet(\{s_5\},\{s_6\},2)$$- значения $$J'$$ для данного вызова приведены в табл. 32.10. Первое максимальное значение $$J'$$ равно 0 для точки проверки $$4:1$$ и значения $$b=1$$. $$S'_1=\{s_5\}$$, $$S'_2=\varnothing$$. Точка проверки $$4:1$$ добавляется в $$h_5$$.
$$MaskSet(\{s_5\},\varnothing,1)$$- вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_5,s_6\},0)$$- вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_3,s_4,s_5,s_6\},0)$$- вызов завершается без внесения изменений в маски.
$$MaskSet(\varnothing,\{s_0,s_1,s_2,s_3,s_4,s_5,s_6,s_7,s_8\},1)$$- вызов завершается без внесения изменений в маски.
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | -1 | 1 | 1 | -1 | -5 | 5 | -7 | 7 | 1 | -1 | 3 | -3 | 7 | -7 | -9 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | - | -2 | 0 | - | - | -2 | 0 | - | - | -2 | - | -2 | - | -2 | -2 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | -1 | 1 | -1 | 1 | -3 | - | -3 | - | -1 | 1 | -3 | - | - | -3 | -3 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | -2 | - | 0 | - | -2 | - | -2 | - | -2 | - | -2 | - | - | -2 | -2 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | - | -4 | - | 0 | 0 | - | -2 | - | - | -4 | - | -2 | - | -4 | -4 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | - | -2 | - | -2 | 0 | - | 0 | - | - | -2 | - | -2 | - | -2 | -2 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | 0 | - | -4 | - | -2 | - | -4 | - | - | -2 | - | 0 | - | -4 | -4 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | -2 | - | -2 | - | -2 | - | -2 | - | - | 0 | - | 0 | - | -2 | -2 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | -4 | - | - | -2 | -4 | - | -4 | - | -4 | - | - | 0 | - | -2 | -4 | - |
| Точка проверки | 1:1 | 1:2 | 2:1 | 2:2 | 3:1 | 3:2 | 4:1 | 4:2 | ||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| $$b$$ | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 | 0 | 1 |
| $$J'$$ | -2 | - | - | -2 | -2 | - | -2 | - | -2 | - | - | -2 | - | 0 | -2 | - |
Работа алгоритма закончена. В результате получены маски:
$$ h_0=\{1:1,1:2,2:1\},\\ h_1=\{1:2,2:1\},\\ h_2=\{1:1,1:2,3:1\},\\ h_3=\{1:1,1:2,3:2\},\\ h_4=\{1:2,3:2\},\\ h_5=\{3:1,3:2,4:1\},\\ h_6=\{4:1\},\\ h_7=\{1:1,3:2\},\\ h_8=\{2:2\}.$$Из приведенного примера ясно, что алгоритм не является точным, т. к. в маске $$h_2$$ точка проверки $$1:2$$ является избыточной.
Следующая теорема определяет верхнюю оценку объема совокупности индивидуальных масок, возвращаемой с помощью алгоритма 2.
Теорема 1. Суммарный объем совокупности индивидуальных масок, полученной с помощью алгоритма2, не превышает величины
$$M\cdot(1+ln(|S|-1)),$$где $$M$$ - суммарный объем совокупности минимальных индивидуальных масок заданного СПР.
Доказательство. Обозначим через $$\#MaskSet(S_1,S_2,J)$$ суммарное количество точек проверки, добавленное в совокупность масок $$H$$ в результате вызова $$MaskSet(S_1,S_2,J)$$.
Из определения алгоритма $$MaskSet$$ ясно, что
$$ \#MaskSet(S,\varnothing,|S|)=\sum\limits_{s\in S}\#MaskSet (\{s\},S\setminus\{s\},|S|-3). $$Запуск $$MaskSet (\{s\},S\setminus\{s\},|S|-3)$$ возвращает индивидуальную маску для технического состояния $$s$$. Работа такого запуска сводится к работе жадного алгоритма поиска
Известно [1], что размер покрытия множества $$P$$, полученного с помощью жадного алгоритма, превосходит размер
где $$M_s$$ - объем минимальной индивидуальной маски для технического состояния $$s$$. Из последнего неравенства следует, что
$$\# MaskSet(S,\varnothing,|S|) =\sum\limits_{s\in S}{M_s} \cdot(1+ln(|S|-1))= M\cdot(1+ln(|S|-1))$$где $$M=\sum\limits_{s\in S}{M_s}$$.
В следующей теореме оценивается сложность описанного алгоритма.
Теорема 2. Временная сложность алгоритма 2 составляет $$O(|S|^3m|\tau|)$$. Объем дополнительной памяти, необходимой для функционирования алгоритма 2, оценивается величиной $$O(|S|^2)$$.
Доказательство. Из формулировки алгоритма 2 ясно, что его сложность равна временной сложности вызова алгоритма $$MaskSet(S,\varnothing,|S|)$$. Оценим ее.
Заметим, что рекурсия по второму обращению к функции $$MaskSet$$ является концевой и эквивалентна итерационному процессу с параметром $$S_1$$ (с условием окончания процесса, как только выполнится $$|S_1|\le 1$$). Таким образом, стоит учитывать лишь первое обращение как
Максимально возможная глубина рекурсии по первому обращению $$MaskSet$$ равна $$|S|-1$$. При каждом таком рекурсивном вызове происходит уменьшение количества элементов в множестве $$S_1\cup S_2$$, вследствие чего можно оценить сверху объем необходимой памяти для вызова $$MaskSet(S,\varnothing,|S|)$$ величиной, кратной $$|S|(|S-1|)/2$$. Отсюда следует оценка емкостной сложности в формулировке теоремы.
Величиной той же кратности можно оценить стоимость поиска одной индивидуальной маски, а следовательно количество операций для поиска всей совокупности индивидуальных масок не превышает величины $$O(|S|^3m|\tau|)$$.
Жадный алгоритм- алгоритм, основанный на принятии локально оптимальных решений на каждом этапе его работы в расчете на возможность получения глобального оптимума.
Задача о минимальном покрытии множества - классическая NP-полная задача, формулируемая следующим образом: Задано множество $$U$$ и семейство его подмножеств $$S$$. Требуется найти такое семейство $$C\subseteq S$$,которое покрывает множество $$U$$.
В лекции описан жадный алгоритм поиска совокупности индивидуальных масок ДИ, базирующийся на сведении исходной задачи к классической задаче о минимальном покрытии множества.
Для получения официальных документов о завершении программы дополнительного профессионального образования (удостоверения о повышении квалификации, дипломов о профессиональной переподготовке и MBA) необходимо предоставить:
Внимание! Вы можете не заказывать доставку бумажной версии официального документы, а скачать его в электронном виде и распечатать самостоятельно. Информация о выданном документе в течение 1 месяца загружается в Федеральную информационную систему «Федеральный реестр сведений о документах об образовании и (или) о квалификации, документах об обучении» - ФИС ФРДО.
Доступ на новый сайт осуществляется с использованием адреса электронной почты, который был указан вами при регистрации на "старом". Мы постарались перенести все ваши данные с прежнего ресурса, однако не исключена вероятность потери части информации.
При возникновении проблемы со входом, воспользуйтесь функцией сброса пароля
Если вы обнаружите несоответствия, пожалуйста, сообщите нам.