5.Дм (0,1,1,1):

Алгоритм:

1Й этап:

1. Присвоить F пустое значение ( F -функция состояния ). Если элемент входит туда с инверсией, то машина соответствующая элементу - неисправна, если без — исправна.

2. Если нет синдрома S_ij =0, то выполнить переход к шагу 5

3. Добавить к F конъюнкцию не инвертированных значений b_i, b_j

4. F = F b_ib_j ( машины i и j исправны )

Выполнить переход на шаг 2

2Й этап:

1. Выбрать очередной элемент S_ij = 1

2. Если b_i присутствует в F без инверсии, то к F добавляем конъюнкцию b_j с инверсией F = F b_j и выполняем переход к шагу 8

3. Если b_j присутствует в F без инверсии, то к F добавляем конъюнкцию b_i с инверсией F = F b_i и выполняем переход к шагу 8

4. Если не все элементы синдрома выбраны, то выполнить переход к шагу 5

5. i = 1

6. Если b_i не входит в F, то дополнить F b_i: F = F b_i

7. i = i+1

8. Если i <= n, то выполнить переход к 10

9. Конец алгоритма

Для каждого элемента синдрома производится не более 1го изменения логического выражения F. При этом размер выражения не превышает 1го терма.

Количество термов определяется количеством конъюнкций объеденных через дизъюнкцию.

Каждый элемент синдрома рассматривается 1 раз. На последнем этапе работы выполняется дополнительные выражения переменными без инверсий в виде n итераций цикла.

O(n^2+n) — трудоемкость.

16. Планирование работы оувс

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

Однократное выполнение алгоритма называют периодом цикла решения и обознается Tцр.

Алгоритм может быть представлен в виде графа ИС.

D = ( W, P, Г )

Тактом решения — называется интервал времени в течении которого произведена 1 элементарная проверка.

Предположим что такты контроля = тактам решения и постоянные:

В качестве результата планирования работы ВС выступает диаграмма загрузки (ДЗ). В ней по вертикальной оси откладывается ЭМ, а по горизонтальной время:

(ДЗ1)

Для планирования работы ОУВС в общем случае требуется 3 этапа:

1. Построение ДЗ P1 не учитывающей диагностических операций. Цель построения — минимизация времени решения при заданном количестве ЭМ и заданном графе ИС. Существует ряд эвристических алгоритмов позволяющих построить такую диаграмму.

2. Точный алгоритм — это полный перебор всех возможных вариантов.

3. Построение P2 — трансформация ДЗ P1. Цель — освободить max возможное количество ЭМ задействованных в решении прикладной задачи, при этом время решения не должно превышать max. Tцр <= Tцр_max

4. P3 — дополнение ДЗ P2. Дублирующимися фрагментами прикладных задач согласно заданному ДГ.

(ДЗ2)

В ДЗ P2 снижают количество задействованных ЭМ до величины целой части n/2, так как дальнейшее снижение ведет к снижению количества проверок, проводимых на данном такте.

Для построения ДЗ P1 используется следующий алгоритм:

(ДЗ3)

Если имеется альтернативы, то возникает проблема выбора. Все алгоритмы определяют стратегию поведения на шагах, где имеется альтернатива.

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

[+]:высокая скорость

[-]:граф не анализируется => эффективность зависит от случайной величины.

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

3й алгоритм: приоритет при выборе имеют вершины min отстоящие от начальных

4й алгоритм: выбирается вершина, длина пути которой от конечной max

5й алгоритм: комбинация из выше перечисленных.