Вопросы надежности радиоэлектронной аппаратуры. Корнилов А.Г. - 39 стр.

UptoLike

ВУЗ: 

КНИТУ-КАИ им. Туполева | Казань

Составители: 

Рубрика: 

39
Лекция № 10
Метод Закревского.
Метод покрытия бинарных матриц.
Основные понятия:
1. число е – некоторый двоичный код, например, типа 11010 = π
1
, π
2
, π
3
е = 00111 = π
3
, π
4
, π
5
2. оператор Закревского – некоторая операция, которая выполняется над
числом e.
Рассмотрим единичный оператор Закревского:
Δω
1
(101000) = 101100
Правило: число е просматривается справа налево, находится разряд, в
котором имеется единица, в следующем за ним пишется единица, тем самым
выполнило оператор Закревского.
Рассмотрим нулевой оператор:
Δω
0
(101000) = 100100
Правило: число е просматривается справа налево, находим разряд, в
котором имеется единица, в этом разряде пишем нуль, а в следующем вправо
разряде – единицу, т.о. оператор Закревского взят.
Взятие оператора Закревского: Δω
0
(101011) = ω
0
(101000)
Тогда выполняется нулевой оператор Закревского от числа е, в котором эта
группа единиц заменена нулями и берётся нулевой оператор.
Δω
1
(101011) = Δω
0
(101000)
вспомогательные числа е
-
, е
+
е
-
(101110) = 101100
Число е просматривается справа налево, находится разряд, в котором
имеется единица, и заменяется на нуль.
е
+
(101110) = 101101
Число е просматривается справа налево, находится разряд, в котором
имеется единица. Она превращается в нуль, а во всех разрядах вправо пишется
единица.
Частный случай:
Если имеется е
+
(101111) = 101110
Алгоритм Закревского:
1. Производится упорядочивание строк бинарной матрицы в порядке
возрастания числа единиц в строке. При этом строки, имеющие
> 1 – располагаются выше
< 1 – располагаются ниже.
2. Выбирается число е = 1000.0. Число е – текущее, в процессе меняется.
3. Определяется, является ли рассматриваемое число е некоторым полным
покрытием матрицы. Если нет, то параметру ω€0 →
п.4
4. Если набор, соответствующий числу е, является минимальным,
получается решение. 
                                   Лекция № 10
                               Метод Закревского.
                         Метод покрытия бинарных матриц.
      Основные понятия:
      1. число е – некоторый двоичный код, например, типа 11010 = π1, π2, π3
         е = 00111 = π3, π4, π5
    2. оператор Закревского – некоторая операция, которая выполняется над
         числом e.

        Рассмотрим единичный оператор Закревского:
       Δω1(101000) = 101100
       Правило: число е просматривается справа налево, находится разряд, в
котором имеется единица, в следующем за ним пишется единица, тем самым
выполнило оператор Закревского.
      Рассмотрим нулевой оператор:
       Δω0(101000) = 100100
       Правило: число е просматривается справа налево, находим разряд, в
котором имеется единица, в этом разряде пишем нуль, а в следующем вправо
разряде – единицу, т.о. оператор Закревского взят.
       Взятие оператора Закревского: Δω0 (101011) = ω0 (101000)
      Тогда выполняется нулевой оператор Закревского от числа е, в котором эта
группа единиц заменена нулями и берётся нулевой оператор.
      Δω1 (101011) = Δω0 (101000)
     вспомогательные числа е-, е+
        е- (101110) = 101100
      Число е просматривается справа налево, находится разряд, в котором
имеется единица, и заменяется на нуль.
        е+ (101110) = 101101
      Число е просматривается справа налево, находится разряд, в котором
имеется единица. Она превращается в нуль, а во всех разрядах вправо пишется
единица.
       Частный случай:
       Если имеется е+ (101111) = 101110

     Алгоритм Закревского:

      1. Производится упорядочивание строк бинарной матрицы в порядке
возрастания числа единиц в строке. При этом строки, имеющие
                               > 1 – располагаются выше
                               < 1 – располагаются ниже.
      2. Выбирается число е = 1000.0. Число е – текущее, в процессе меняется.
      3. Определяется, является ли рассматриваемое число е некоторым полным
покрытием матрицы. Если нет, то параметру ω€0 → п.4
      4. Если набор, соответствующий числу е, является минимальным,
получается решение.


                                                                                39

Страницы