Аналитический алгоритм нахождения всех полных алгоритмов контроля (избыточных, не избыточных, оптимальных)

Для каждого столбца таблицы покрытий строится элементарная контрольная столбцовая дизъюнкция (ЭКСД). ЭКСД будет представлять из себя дизъюнкцию символов проверок d_h, которые накрывают рассматриваемый столбец γ. Контрольная конъюнктивная форма (ККФ) – F. Методом построения таблицы истинности можно показать, что функционал контрольной конъюнктивной формы по законам булевой алгебры преобразуется в функционал контрольной дизъюнктивной формы. Все расчёты могут быть проверены по таблице истинности. Каждое произведение в дизъюнктивной форме отображает полный алгоритм контроля. Достоинство метода – метод даёт регулярное решение. Недостаток – сложность преобразований в булевой алгебре.

Вся прелесть этого метода зачёркивается сложностями логических преобразований. На практике используют квазиоптимальные алгоритмы.

Практическое значение имеют инженерные алгоритмы, построение оптимальных и субоптимальных алгоритмов.

Аналитический метод построения одного квазиоптимального или субоптимального безусловного алгоритма по количеству выполняемых проверок

Иногда этот метод называют скорейшим методом спуска по дереву.

Проверки упорядочиваются по модулю характеристического уравнения. Упорядочивание проверок возможно потому, что мы работаем с безусловным алгоритмом, где важен состав, а не последовательность алгоритма. В качестве первой проверки выбирается проверка 1. На втором шаге вычисляются прогностические характеристические числа.

Проверку вторую выбираем по максимальному приращению на втором шаге модуля нового характеристического числа. Если после проверки итоговый модуль меньше, то идём на следующий шаг.

В том случае, если в таблице покрытий имеются сплошные строки, то построение алгоритма не делается.

Этот метод компактнее, чем метод, который основывается на основах булевой алгебры. НО! Этот метод даёт оптимальный алгоритм только в том случае, если в точках ветвления идёт однозначный выбор лучшей проверки. Если же в точках графа возможны альтернативные варианты, то ведётся отбор проверки с меньшим номером. Наличие альтернативных решений исключает факт построения оптимального алгоритма.