о мінімального (або мінімальний) діагностичний тест. br/>
4.3 Побудова досить простих діагностичних тестів за допомогою алгоритму Сіндеева
Вихідний матеріал в даному алгоритмі задається у вигляді матриці станів, причому розглядається транспонована матриця станів, тобто матриця станів, у якої стовпці відповідають усім можливим станам, а рядки - всім можливим перевіркам. Заради. Простоти викладу обмежимося випадком, коли безліч результатів перевірок складається з двох елементів А = {0,1}, тобто кожна перевірка має лише два можливих результати. Матрицю станів можна розглядати як завдання деякої кінцевої схеми
В
Передбачається, що всі n станів, складові повну групу подій, рівноймовірні:. Тоді, з точки зору теорії інформації, невизначеність або ентропія, створювана такий кінцевої схемою, запишеться у вигляді:
В
Для того щоб однозначно визначити стан кінцевої схеми, необхідно провести деякий експеримент, що складається в послідовному виборі не більше ніж m перевірок. Кожна перевірка pk несе деяку кількість інформації щодо стану вказаної кінцевої схеми:, де H (pk) - середня умовна ентропія стану схеми за умови вибору перевірки pk. Так як при проведенні перевірки pk є тільки два можливих результати pk = 1 і pk = 0 з імовірностями РK (pk) і pk (), то
В
де і - ентропії станів схеми після проведення перевірки pk;
,
де l -число одиниць у i-й рядку вихідної матриці станів. При цьому
, a ,
Першої вибирається перевірка p k , несуча максимальну кількість інформації . Якщо таких перевірок декілька, то обирається будь-яка з них.
I ( p k ) = H - H ( p k ) = I max
Другий вибирається перевірка p t , яка володіє найбільшою умовної інформацією I ( p t / p k ) щодо стану, що характеризується ентропією Н ( p k )
I ( p t
