О.Б. Лупанов - Элементы математической кибернетики (1161667), страница 9
Текст из файла (страница 9)
Цепь будет замкнутой с вероятностью p2 и разомкнутой с вероятностью 1 − p2 . Вся схемаокажется разомкнутой с вероятностью (1 − p2 )2 , и замкнутой с вероятностью 1 − (1 − p2 )2 . Итак, вероятность некорректной работы схемыпри xσi = 0 меньше 2p2 .Таким образом, в любом случае вероятность ошибки в одном контакте xσi не превышает 4p2 Повторяя описанную процедуру, можно добиться, чтобы вероятность ошибки в одном контакте Perr (xσi ) < pcN ,где, считаем, 4p = c < 1.
Если теперь необходимо построить контактную схему S, реализующую функцию f (x1 , . . . , xn ), чтобы Perr (S) < ε,то выберем параметр N таким, чтоpcN <ε.n2nКаждый контакт заменим подсхемой с вероятностью ошибки меньшеε/(n2n ). ТогдаεPerr (S) < L(S) n 6 εn2nпри L(S) 6 n2 и p < 1/4.§ 5.2. Тупиковый тестДопустим, S0 — исправная контактная схема, реализующая функцию f0 , а S1 , . . .
, Sq — неисправные состояния той же схемы, реализующие, соответственно, функции f1 , . . . , fq . Требуется, анализируя fj ,определить неисправность. Можно, например, подстановкой тех или49иных наборов в функцию проводимости проверять замкнут или разомкнут соответствующий контакт.Формально, имеется таблица M, в которой по столбцам выписанызначения каждой из функций f (1) , . . . , f (t) на наборах α1 , . .
. , αs , причем все столбцы различны. Множество наборов, по которым можноразличить все функции, называется тестом. Минимальный тест —тест, содежащий наименьшее число наборов. Тупиковый тест — тест,который при удалении любого набора перестает быть тестом. Минимальный тест является также и тупиковым.Пусть A(M) — длина минимального теста для таблицы M. Тогдаlog2 t 6 A(M) 6 t − 1.(12)Докажем нижнюю оценку в (12). Предположим, что тест содержитk < log2 t наборов.
Но тогда различных столбцов t > 2k , чего не можетбыть, поскольку по условию все столбцы различны. Остается тольковозможность, когда в точности t = 2k .В доказательстве верхней оценки в (12) используетсяТеорема 10. Для произвольной булевой матрицы M, содержащей mпопарно различных столбцов, существует тест, длина которого непревосходит m − 1.Докажем индукцией по числу столбцов. Если столбец один, то тестпустой. Если столбцов два, то обязательно найдется строка, по которойони отличаются.
Предположим, что утверждение теоремы имеет местодля числа столбцов равного k и менее. Покажем его справедливостьдля k + 1 столбцов. Возьмем произвольную j–ю строку Sj , в которойразличны, например, первая и вторая компоненты. Будем считать дляопределенности, что первая компонента нулевая, а вторая единичная.Рассмотрим теперь матрицы M0 и M1 , составленные соответственноиз m0 столбцов матрицы M с нулевой и m1 столбцов с единичной j–йкомпонентой. Понятно, что mi 6 k, i = 1, 2 и m0 + m1 = k + 1. Тогдапо предположению индукции существуют тесты T0 для M0 и T1 дляM1 такие, что|T0 | 6 m0 − 1, |T1 | 6 m1 − 1.Пусть T = T0 ∪ T1 ∪ {Sj }. Покажем, что T — тест для M.
Действительно, рассмотрим произвольные столбцы Â и B̂ матрицы M. Еслиих компоненты из Sj неодинаковы, то столбцы уже различены с помощью T , если обе их компоненты из Sj нулевые (единичные), то столбцысодержатся в M0 (M1 ) и различены по предположению индукции. Оценим длину теста: |T | 6 m0 − 1 + m1 − 1 + 1 = k. Теорема доказана.50x1 , . . . , xn−1 , xnf···g1gl0, . . . , 0, 0...1, . . . , 1, 1Табл. 2§ 5.3. Диагностические тесты дляконтактных схемРассмотрим произвольную контактную схему S, в которой между полюсами a и b реализуется некоторая функция проводимости fa,b (x1 , . . .
, xn ). В результате неисправности схема S преобразуется в некоторую схему S ′ , реализующую функцию неисправностиga,b (x1 , . . . , xn ). Выпишем значения функции f и всех попарно различных функций неисправности g1 , . . . , gl по столбцам таблицы (см.табл. 2).Полным диагностическим тестом T для контактной схемы S называется множество наборов такое, что для любой пары функций{g, g ′} ⊂ {f, g1 , . . . , gl } найдется элемент σ̃ ∈ T , g(σ̃) 6= g ′ (σ̃).
Понятно,что множество всех 2n наборов тривиальным образом является полнымдиагностическим тестом. Длина D(T ) полного диагностического тестаT есть число наборов теста. Определим такжеD(S) = min D(T ).T =T (S)Здесь минимум берется по всем полным диагностическим тестам T длясхемы S. Аналогично,D(f ) = min D(S),S=S(f )D(n) =maxf (x1 ,...,xn )D(f ).Теорема 11. D(n) = 2n для любого n ∈ N.Доказательство.
Поскольку D(n) — максимум, взятый по всем функциям f , то достаточно показать, что для любой контактной схемы S,реализующей функцию f (x̃) = ln (x̃) = x1 ⊕ · · · ⊕ xn , всякий полный диагностический тест содержит все 2n наборов (максимально возможноеколичество).511. Пусть f (σ̃) = 1. Следовательно, если схема S исправна, между ееполюсами должна существовать цепь Z с контактами xσ1 1 , . . . , xσnn . Еслипредположить, что в цепи Z отсутствует один из контактов, например,xσ1 1 , то получится, что наборам σ̃ = (σ1 , σ2 , . . .
, σn ) и σ̃ ′ = (σ1 , σ2 , . . . , σn )соответствует единичная проводимость. Но это неверно, так какf (σ̃) 6= f (σ̃ ′ ). Значит, все контакты xσ1 1 , . . . , xσnn содержатся в Z. Разомкнем теперь все контакты схемы S кроме контактов цепи Z. Полученная схема будет иметь функцию неисправности g(x̃) = xσ1 1 · · · xσnn , ичтобы отличить g от нуля необходимо включить набор σ̃ в тест.
Аналогично придется поступить с каждым σ̃ ∈ Nf , а это 2n−1 наборов.2. Пусть f (σ̃) = 0. Если схема S исправна, в ней будут разомкнутыконтакты xσ1 1 , . . . , xσnn . Найдется такое множество контактов схемы S,которое образует сечение схемы, но, сечение, возможно, нетупиковое.Однако, лишние“ контакты нетупикового сечения можно удалить за”конечное число шагов, поэтому будем заранее считать сечение тупиковым.
Обозначим его через A. Допустим, что какой–то из контактовсистемы xσ1 1 , . . . , xσnn , например, xσ1 1 не содержится в A. Аналогично, получим противоречие, поскольку по предположению проводимость нанаборах σ̃ = (σ1 , σ2 , . . . , σn ) и σ̃ ′ = (σ1 , σ2 , . . . , σn ) должна быть нулевая, хотя f (σ̃) 6= f (σ̃ ′ ). Значит, все контакты xσ1 1 , . . . , xσnn содержатсяв тупиковом сечении A. Предположим теперь, что все контакты вне Aнеисправны и разомкнуты.
Это означает, что функция неисправностипринимает нулевое значение на наборе σ̃, а на остальных наборах онаединична. Таким образом, чтобы отличить функцию xσ1 1 ∨ · · · ∨ xσnn отединицы, нужно обязательно включить набор σ̃ в тест. И так для всехнаборов σ̃ ∈ En2 \ Nf , которых тоже 2n−1 . Следовательно, в сумме тестобязан содержать 2n наборов. Теорема доказана.§ 5.4. Задача на покрытие и градиентныйалгоритм ее решенияВ общем случае постановка задачи такова. Имеется множествоS = {a1 , . .
. , an }. Пусть семейство S1 , . . . , Sk подмножеств множестваS таково, чтоk[Si = S.i=1В этом случае семейство множеств S1 , . . . , Sk называется покрытием S.Будем говорить, что строка A покрывает столбец B булевой матрицы,52если элемент, находящийся в строке A и столбце B, равен 1. В противном случае строка A не покрывает столбец B. Подмножество строкматрицы, покрывающее все ее столбцы, называется покрытием матрицы. Минимальное покрытие — покрытие, содержащее наименьшеевозможное число строк.
Задача на покрытие состоит в нахожденииминимального покрытия.Рассмотрим градиентный алгоритм построения минимального покрытия R булевой матрицы T .0. T — исходная матрица, R = ∅.1. Выберем в T строку A, покрывающую наибольшее число столбцов. Включим A в R.2. Вычеркнем из T все столбцы, покрытые строкой A, и вычеркнемтакже саму строку A.
Если матрица T оказалась пустой, то выполнять3. Если матрица T содержит непокрытые столбцы, то выполнять 1.3. Алгоритм завершен, в качестве покрытия возьмем полученноемножество R.Теорема 12. Пусть булева матрица T имеет M строк и N столбцов, причем, каждый столбец содержит не менее P единиц. Тогдадля R = |R| градиентный алгоритм гарантирует оценкуMPN+ 1 + 1.(13)R6lnPMДоказательство. Обозначим через βt долю охваченных алгоритмомстолбцов матрицы T после t–го шага.
Считаем, β0 = 0. Переставим напервые места βt N охваченных алгоритмом столбцов и t строк с единицами. Тогда в правой нижней подматрице размера (M − t) × (1 − βt )Nне менее (1 − βt )NP единичных элементов. Следовательно, найдется еще не охваченная алгоритмом строка матрицы T , содержащаяпо меньшей мере (1 − βt )NP/(M − t) единиц. Выберем эту строку на(t + 1)–м шаге алгоритма.
Тогда в силуполучим(1 − βt )NP(1 − βt )NP>,M −tMβt+1 N > βt N + (1 − βt )Отсюдаβt+1 >P1−M53βt +NP.MP.M(14)Докажем по индукции справедливость равенстваtPβt > 1 − 1 −M(15)для всех целых t > 0. При t = 0 имеем β0 > 0, что верно. Предположим,что (15) справедливо для t, и докажем его справедливость для t + 1.Согласно (14)t !PPPPPβt +> 1−1− 1−+>βt+1 > 1 −MMMMMt+1t+1PPPP>1−− 1−+=1− 1−.MMMMТаким образом, (15) выполняется для всех целых t > 0.Как уже было сказано, после t0 –го шага алгоритма неохваченныхстолбцов будет не более N(1 − βt0 ). Следовательно, на них алгоритмомбудет потрачено не более N(1−βt0 ) строк матрицы T .
Это очень грубаяоценка. Значит, в общей сложности использованных строкR 6 t0 + N(1 − βt0 ).Возьмемt0 = ⌈тогдаM PNln⌉,PMM PNM PNln6 t0 <ln+ 1.PMPMВ силу (15) имеемM PNR6ln+1+NPMM PN6ln+1+NPMПоследнее равноtP 01−6M M ln P NP P M1−.M M PNP M PNln+ 1 + N exp ln 1 −ln<PMM PMM PNMMPN<ln+1+N=ln+ 1 + 1,PMPNPM54посколькуPln 1 −MM< −1.PТеорема доказана.Ранее было отмечено, что градиентный алгоритм в силу своей жадности рационален далеко не всегда.
Действительно, рассмотрим матрицу1 ··· 11 ··· 11 ··· 1 0.10101 .... .... .... . ··· . . ··· . . ··· . 01 01 01В ней m + 3 строк и 3 · 2m столбцов. В трех верхних строках по 2m единиц, а в m нижних по столбцам трижды размещены наборы единичного куба Em2 . Понятно, что минимальное покрытие матрицы состоитиз трех ее верхних строк. Градиентный же алгоритм в первую очередьначнет работать по m нижним строкам матрицы, поэтому в результатеполучится покрытие, включающее все m + 3 строк.Отметим связь задачи на покрытие с дизъюнктивными нормальными формами. Пусть столбцы Âi и Âj булевой матрицы различаются на наборахα̃ij1 , α̃ij2 , . .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
