ОК_Часть_1_2015 (С.А. Ложкин - Лекции по основам кибернетики (2015)), страница 7

Пусть NK1 , . . . , NKq — все максимальные грани ФАЛ f , причем грани NKp+1 , . . . , NKt , где1 6 p 6 t 6 q, являются ядровыми, а грани NKt+1 , . . .. . . , NKq — регулярными гранями ФАЛ f , и пусть множеb состоит из всех ядровых и регулярных точек ФАЛство Nf . ПоложимbN = Nf \ N,N = {N1 , . . . , Np } ,b при всех i, i ∈ [1, p], и заметим, что задагде Ni = NKi \ Nча построения всех тупиковых ДНФ ФАЛ f эквивалентна44Глава 1. Дизъюнктивные нормальные формызадаче выделения всех тупиковых подпокрытий из покрытия N множества N. Действительно, если система подмножеств Ni1 , . .

. , Nir , где 1 6 i1 < · · · < ir 6 p, является тупиковым покрытием множества N, то система максимальных граней NKi1 , . . . , NKir , NKp+1 , . . . , NKt задает тупиковоепокрытие множества Nf , то есть соответствует тупиковойДНФ ФАЛ f , и обратно.Так, применяя указанную модификацию к ФАЛ g 0 изP2 (4), показанной на рис. 3.1 (см. также (3.1) и (4.3)), получим тривиальную задачу о покрытии множества N == {(1000)} двумя совпадающими с ним подмножествами N1и N2 .§6Градиентный алгоритм и оценка длины градиентного покрытия. Использование градиентного алгоритма для построения ДНФВыделение всех тупиковых подпокрытий из заданного покрытия и, в частности, построение всех тупиковых ДНФявляется трудоемкой задачей. В связи с этим, вместо того, чтобы строить все тупиковые ДНФ и выбирать срединих, например, кратчайшую, часто используют эвристические алгоритмы, позволяющие получать не очень «длинные» ДНФ.

К числу таких алгоритмов относится и градиентный алгоритм, ориентированный на выделение из заданного покрытия достаточно «коротких» подпокрытий, или,иначе, на построение достаточно «коротких» покрытий длязаданной матрицы. На каждом шаге градиентного алгоритма в матрице выбирается и включается в покрытие такаястрока, которая покрывает наибольшее число еще не покрытых столбцов (если таких строк несколько, из них выбирается строка с наименьшим номером). Алгоритм заканчиваетсвою работу после того шага, на котором получилось покрытие.§6. Градиентный алгоритм45Следующее утверждение дает верхнюю оценку длиныпокрытия, получаемого с помощью градиентного алгоритма для матриц с заданной «густотой».Теорема 6.1 ([6]).

Пусть для действительного γ, 0<γ 61,в каждом столбце матрицы M, M ∈ B p,s , имеется неменьше, чем γ · p, единиц. Тогда покрытие матрицы M , получаемое с помощьюl градиентногоалгоритма, имеет длиm+111ну не больше, чем γ ln (γs) + γ .Доказательство. Пусть для построения покрытия матрицы M с помощью градиентного алгоритма потребовалосьсделать q шагов, причем на шаге с номером t, t ∈ [1, q], была выбрана строка с номером it . Для каждого t, t ∈ [1, q),рассмотрим матрицу Mt , которая получается из матрицы Mв результате удаления строк с номерами {i1 , .

. . , it }, а такжепокрываемых ими столбцов, и которая принадлежит множеству B pt ,st , где pt = p − t и st = s · δt , 0 6 δt 6 1. Для определенности будем считать, что M0 = M, p0 = p, s0 = s, δ0 = 1и pq = p−q, sq = δq = 0. Заметим, что при любом t, t ∈ [0, q],справедливо неравенствоq 6 t + δt · s,(6.1)так как после выполнения первых t шагов алгоритма остаются не покрытыми δt · s столбцов матрицы M , а на каждомследующем шаге покрывается не менее одного столбца.Заметим, далее, что в каждом столбце матрицы Mt , t ∈ [0, q),имеется не менее, чем γ · p, единиц и поэтому общее числоединиц в матрице Mt не меньше, чем γpsδt , а значит среднее число единиц в ее строках не меньше, чем γsδt .

Отсюдавытекает, что строка матрицы M с номером it+1 , котораявыбирается на (t + 1)-м шаге алгоритма и является строкой матрицы Mt с наибольшим числом единиц, содержит не1Полагаем, что ln+ x = ln x, если x > 1, и ln+ x = 0, если 0 < x < 1.46Глава 1. Дизъюнктивные нормальные формыменьше, чем γsδt , единиц, то есть покрывает не меньше, чемγsδt , еще не покрытых столбцов матрицы M . Таким образом, для любого t, t ∈ [0, q), выполняются соотношенияsδt+1 = st+1 6 st − γsδt = sδt (1 − γ) ,из которых, с учетом δ0 = 1, следует, чтоδt 6 (1 − γ)t 6 e−γt(6.2)при любом t, t ∈ [0, q).Выбирая значение параметра t так, что1 +t=ln (γs) ,γподставляя его в (6.2) и учитывая (6.2), получимq6+1 +1 +1ln (γs) + s · e− ln (γs) 6ln (γs) + .γγγТеорема доказана.В качестве примера применения градиентного алгоритмарассмотрим задачу о «протыкании» граней куба его точками. Задача о «протыкании» системы N, состоящей из подмножеств N1 , N2 , .

. . , Np множества N = {α1 , . . . , αs }, заключается в нахождении такого подмножества множестваN, в котором при любом i, i ∈ [1, p], имеется хотя бы одинэлемент из Ni . Эта задача сводится к задаче о выделенииподпокрытия из покрытия отрезка [1, p] его подмножествами I1 , . .

. , Is , где Ii = {j : αi ∈ Nj } при всех i, i ∈ [1, s].Заметим, что матрица построенной таким образом системыподмножеств отрезка [1, p] получается из матрицы системы(N, N) в результате транспонирования.§7. Оценки параметров ДНФ47Лемма 6.1 ([19]). При любых натуральных n и m, m 6 n,в кубе B n всегда найдется подмножество мощности не более, чем n · 2m , протыкающее все грани ранга m.Доказательство.

Применяя указанный выше подход, рассмотрим множествосостоящее из всех граней ранга m N,n· 2m , а также систему N = {Nα }α∈B n егокуба B n , |N| = mподмножеств, где Nα — множество тех граней из N, которые проходят через точку α. Очевидно, что каждая граньиз N содержится в тех 2n−m подмножествах Nα , для которых точка α принадлежит этой грани. Следовательно, матрица M ,связанная с парой (N, N), состоит из p = 2n строкnиs= m· 2m столбцов, в каждом из которых имеется p · γ,−mгде γ = 2 , единиц. Искомое множество наборов получается в результате применения к матрице M теоремы 6.1 ипостроения покрытия длины q, где nnmm+ 2 6 2 log+ 2m 6q 6 2 lnmm6 2m (n − 1) + 2m = n · 2m .m+Лемма доказана.§7Задача минимизации ДНФ.

Поведение функций Шеннона и оценки типичных значенийдля ранга и длины ДНФКак уже отмечалось, ДНФ представляет собой удобную инаглядную (с «геометрической» точки зрения) форму задания ФАЛ. С другой стороны, ДНФ можно рассматриватькак простейшую модель, предназначенную для структурнойреализации ФАЛ (см. гл. 3).Заметим, что различные параметры ДНФ (ранг, длина и т.

п) характеризуют различные48Глава 1. Дизъюнктивные нормальные формы«меры» сложности указанного представления или структурной реализации. В связи с этим часто возникает необходимость построения оптимальной в том или ином смысле ДНФдля заданной ФАЛ, то есть необходимость решения соответствующей задачи минимизации ДНФ, которая являетсячастным случаем задачи синтеза управляющих систем (см.гл.

3).В общем виде задача минимизации ДНФ может бытьсформулирована следующим образом. Пусть для каждойДНФ A определена ее «сложность» ψ (A), ψ (A) > 0, длякоторой ψ (A0 ) > ψ (A00 ), если ДНФ A00 получается из ДНФA0 удалением букв или ЭК. В этом случае будем говорить,что на множестве ДНФ задан неотрицательный функционалсложности ψ, обладающий свойством монотонности. Примерами таких функционалов могут служить длина λ (A),ранг R (A) или «формульная» сложность L (A) ДНФ A, атакже число вхождений БП с отрицаниями и другие параметры ДНФ. Задача минимизации ДНФ относительно функционала сложности ψ состоит в том, чтобы по заданнойФАЛ f построить реализующую ее ДНФ A такую, чтоψ (A) = min ψ A0 ,где минимум берется по всем ДНФ A0 , реализующим ФАЛ f .При этом ДНФ A считается минимальной относительнофункционала ψ, или, иначе, ψ-минимальной ДНФ, а значение ψ (A) называется сложностью ФАЛ f относительнофункционала ψ, или, иначе, ψ-сложностью ФАЛ f в классеДНФ.

В соответствии с введенными ранее определениями,λ-минимальную ДНФ, то есть ДНФ минимальную по длине,будем называть кратчайшей, а R-минимальную ДНФ, тоесть ДНФ минимальную по рангу, — просто минимальной.Функциюψ (n) = max ψ (f ) ,f ∈P2 (n)§7. Оценки параметров ДНФ49которая характеризует максимальное значение ψ-сложностиФАЛ из P2 (n), называют, обычно, функцией Шеннона длякласса ДНФ относительно функционала ψ.Установим поведение функций Шеннона λ(n) и R(n) длядлины и ранга ДНФ ФАЛ из P2 (n) соответственно.Лемма 7.1. Для любого n, n ∈ N, имеют место соотношенияλ(n) = 2n−1 , R(n) = n · 2n−1 .(7.1)Доказательство.

Нижние оценки (7.1) следуют из того,чтоλ(ln ) = 2n−1 и R(ln ) = n · 2n−1 , так как единственной ДНФлинейной ФАЛ ln = x1 ⊕ · · · ⊕ xn является ее совершенная ДНФ. Для получения требуемых в (7.1) верхних оценоквозьмем произвольную ФАЛ f из P2 (n) и, в соответствии с(2.5), разложим ее по БП x2 , . . . , xn следующим образом:_f (x1 , . .

. , xn ) =xσ2 2 · · · xσnn · f x1 , σ 00(7.2)σ 00 =(σ2 ,...,σn )Легко видеть, что после замены в разложении (7.2) каждойФАЛ f (x1 , σ 00 ) равной ей ФАЛ из множества {0, 1, x1 , x1 } иприведения подобных мы получим ДНФ Af длины не больше, чем 2n−1 , что доказывает верхние оценки в (7.1).Лемма доказана.При изучении того или иного связанного с ДНФ функционала ψ наряду с его максимальным значением, то естьфункцией Шеннона ψ (n), представляет интерес соответствующий отрезок "типичных" значений, то есть отрезок [ψ 0 (n) , ψ 00 (n)],в который попадают значения ψ (f ) для почти всех ФАЛ fиз P2 (n).

Если при этом границы ψ 0 (n) и ψ 00 (n), где n =1, 2, . . ., асимптотически равны ψ (n), то говорят, что дляпараметра ψ имеет место эффект Шеннона. Выясним некоторые особенности строения ДНФ у почти всех ФАЛ и установим, в частности, отсутствие эффекта Шеннона для параметров λ и R - длины и ранга ДНФ соответственно.50Глава 1. Дизъюнктивные нормальные формыВведем дискретную векторную случайную величину ξ (n) =ξe0 , . .

. , ξe1 , состоящую из 2n независимых случайных величин ξα , α ∈ B n , принимающих значения 0 и 1 с вероятностью 12 . При этом, очевидно, для любого α, α ∈ B n , выполняются равенства1Eξα = ,21Dξα = ,4(7.3)где Eθ и Dθ - математическое ожидание и дисперсия случайной величины θ (см., например, [25]).Будем считать, что любая ФАЛ f из P2 (n) является реализацией величины ξ, при которой ξα = f (α) для любогоnα, α ∈ B n , и что вероятность такой реализации равна 2−2 .Отсюда следует, что для любого множества Q, Q ⊆ P2 (n),nотношение |Q| /22 , то есть доля тех ФАЛ f из P2 (n), которые принадлежат Q, равна вероятности того, что реализация случайной величины ξ принадлежит Q.Из независимости случайных величин ξα , α ∈ B n , вытеe которая равна мощностикает, что для их суммы ξe(n) = ξ,множества Nf для ФАЛ f , являющейся реализацией случайной величины ξ (n) = ξ, в силу (7.3) справедливы равенства(см., например, [4])Eξe(n) = 2n−1 ,Dξe(n) = 2n−2 ,(7.4)Полагаяlmnt = n · 22 ,I = 2n−1 − t, 2n−1 + tи применяя к случайной величине ξe с учетом (7.4) неравенство Чебышева [4], получим, что вероятность события ξe ∈/ I,то есть доля тех ФАЛ f из P2 (n), для которых |Nf | ∈/ I, небольше, чемDη16 22t4n§7.

Оценки параметров ДНФ51и, следовательно, стремится к 0 при n стремящемся к бесконечности. Это означает, в частности, что для почти всехФАЛ f из P2 (n), выполнено равенство|Nf | = 2n−1 1 ± O n · 2−n/2(7.5)то есть длина совершенной ДНФ у почти всех ФАЛ из P2 (n)асимптотически равна 2n−1 .Лемма 7.2. Для почти всех ФАЛ f , f ∈ P2 (n), выполняются неравенства3λ(f ) 6 2n−1 1 + O n · 2−n/2 ,43λ(f ) 6 n · 2n−1 1 + O n · 2−n/2 ,4(7.6)(7.7)Доказательство. Пусть ФАЛ f , f ∈ P2 (n), является реализацией случайной величины ξ.