В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций), страница 23

То же имеет место и для множества верхних нулей функции f.Значит d M ≤ 2i . Теорема доказана.Из теоремы 2 следует, что для выделения произвольной монотоннойфункции на М достаточно знать ее значения не более, чем в 2i элементах. Однакодля оценивания сложности задачи необходим алгоритм, который бы находил этиэлементы.Теорема 3. Для функции ω(M) справедливы оценкиi ≤ ω(M)≤  i log2M+i ,i где [ x] - целая часть x.Доказательство. Необходимо доказать только верхнюю оценку, посколькуиз ω(M)≥ d M и d M ≥ i следует нижняя оценка.Опишем конкретный алгоритм A, позволяющий выделять произвольнуюдвоичную функцию f на M.

Если i - максимальное число попарно несравнимыхэлементов, то по теореме Дилуорса [11, параграф 3] существует разбиениемножества М на i непересекающихся цепей. Пусть это цепиС1,С2,...,С i , C p = l p, p = 1, i . Будем считать, что это разбиение задано, т.е.для любых p,r можно указать элемент с номером r в цепи C p . Пусть a1,a2,...,al1- цепь C1 в порядке убывания. Пусть r = ]log 2 l1 [ - ближайшее сверху к log 2 l1целое число. На первом шаге алгоритм А определяет значение f ( a2r −1 ) . Еслиf ( a2r −1 ) =0, то f ( at ) =0 при t > 2r−1 в силу монотонности f и на втором шагеалгоритм А применяется к цепи a1,...,a2r −1 −1 .

Если f ( a2r −1 ) =1, то f ( at ) =1 при t< 2r−1 и на втором шаге алгоритм А применяется к цепи a2r −1 +1,...,al1 и т.д.Число обращений к отображению f : М → {0,1}, достаточное для определениязначения f на цепи C1 не превосходит r = ]log 2 l1 [ .Проделаем эту процедуру со всеми цепями С2,...,С i независимо. ТогдаимеемMt= it= iω( M) ≤ ∑t=1 ]log 2 lt [ ≤ i + ∑t=1 log 2 lt ≤ i + log( l1...li ) ≤ i +  i log 2  ,i 127i Mпоскольку справедливо неравенство l1...li ≤   , если l1 +...+ li = M . iТеорема доказана.Применим теперь полученные результаты к конкретному частичноупорядоченному множеству. Пусть Е n - множество двоичных наборов длины n собычным отношением частичного порядка:x ≤ y ⇔ xi ≤ yi , i ∈1,n, x = ( x1,...,xn ), y = ( y1,...,yn ) .Множество L ⊂ Е n называется цепью, если любая пара элементов из L сравнима.Теорема 4. Множество Е n может быть представлено в виде объединения nn попарно непересекающихся цепей, обладающих свойством: число цепей    2  n  n  nдлины n-2p+1 равно   −  , 0 ≤ p ≤   , при этом минимальный p  p − 1 2элемент цепи имеет вес p, максимальный - вес n-p .Доказательство.

Доказательство индукцией по n . При n=1,2 утверждениепроверяем непосредственно. Разобьем множество Е n на два подмножества E1n−1 иE2n−1 , получаемые фиксацией первой координаты 0 и 1 соответственно. Пусть n −1 12утверждение верно для E n−1 и множества E n−1 и E n−1 , покрыты   n − 1 цепями  2 с указанными свойствами.

Образуем покрытие множества Е n следующимобразом: Пусть C1 - цепь множества E1n−1 и y1 - ее максимальный элемент. Тогдаудлиним цепь C1 , добавив к ней максимальный элемент y2 цепи C2 , изоморфнойC1 в множестве E2n−1 , удаляя при этом из C2 элемент y2 . Проделаем этуоперацию со всеми цепями из E1n−1 . Ясно, что цепи, покрывающие Е n , не будутпересекаться.

Число цепей длины n-2p+1 будет равно n − 1  n − 1   n − 1  n − 1  −  +  − .112pppp−−− Действительно, цепи длины n-2p+1 получаются из цепей длины n-2pудлинением и из цепей длины n-2p+2 укорочением. Однако, n-2p= n-1-2p+1 и поиндукции128 n − 1  n − 1n-2p+2= n-1-2(p-1)+1 и по − . Далее, p   p − 1 n − 1  n − 1индукции имеем число таких цепей  − . Отсюда получаем p − 1  p − 2 n − 1  n − 1  n − 1  n − 1  n  n  − + − =   −. p   p − 1  p − 1  p − 2  p  p − 1число таких цепей равно Тем самым получено требуемое число цепей длины n-2p+1. Общее число цепей nравно, очевидно,   n  .    2 Теорема доказана.Следствие.

Максимальное число попарно несравнимых элементов в Е n nравно   n  .    2 Доказательство. Пусть i - максимальное число попарно несравнимых nэлементов в Е n . Рассмотрим в Е n множество наборов веса k =   . Таких 2 nнаборов, очевидно,   n  . Ясно, что наборы одного веса из Е n несравнимы.    2  nТогда i ≥   n  . С другой стороны, если взять покрытие Е n цепями, то    2 несравнимые наборы не могут лежать на одной цепи.

Поэтому по доказанному, i n≥   n  . Следствие доказано.    2 Теорема 5. Справедливо соотношение n  n  ω(E n ) =   n  +   n   .      + 1  2   2  Доказательство. Оценку снизу устанавливаем предъявлением конкретнойфункции129 n0,есливес(x,...,x)≤n1 2f ( x1,...,xn ) = .n 1, если вес ( x ,...,x ) >  n1 2 n nФункция f ( x1,...,xn ) имеет   n  верхних нулей (это наборы веса   ) и 2    2  n  nнижнихединиц(этонаборывесаn   +1 2 +1). Следовательно, выполнено    2  n  n  ω(E n ) ≥   n  +   n   .      + 1  2   2  Оценку сверху получим предъявлением конкретного алгоритма,выделяющего произвольную монотонную функцию.1.Определяются значения f на цепях длины 1 (если n четно) или цепяхдлины 2 (если n нечетно).2.Если значения f определены на цепях длины n-2p-1, то рассматриваетсяцепь С длины n-2p+1: α 1 , α 2 ,..., α n−2 p+1 . Рассматриваем элементы α 2′ ,..., α ′n−2 p ,такие, что α 1 < α 2′ < α 3, α 2 < α 3′ < α 4 ,..., α n−2 p−1 < α ′n−2 p < α n−2 p+1 .

Этиэлементы лежат на цепях длины n-2p-1 и поэтому там значения f определены. Помонотонности значения f определены на всей цепи С кроме, быть может, двухточек. Если f (α ′q ) = 1 для q = 2,...,n − 2p , то требуется найти f (α 1 ) иf (α 2 ) . Если f (α ′q ) = 0 для q = 2,...,n − 2p , то требуется найти f (α n−2 p ) иf (α n− 2 p+1 ) . Если для некоторого i имеем f (α ′i ) = 0, f (α ′i +1 ) = 1, то требуетсянайти f (α i ), f (α i +1 ) . Тем самым алгоритм A определен.Число элементарных операций (обращений к функции f) удовлетворяетнеравенству ω (E n ) ≤ c(1) + 2( c(2) +...+ c( n + 1)) ,где c(i) - число цепей длины i, i ∈1,n + 1. Тогда имеем при n=2k n   n   n  n  n  n ω(E n ) ≤   −  + 2 − +... =   + . k  k − 1k1k2kk1−−−При n=2k+1 имеем n  n   n   n  n  n  n ω(E n ) ≤ 2  −  + +... =   +   =   + .kk1k1kkkk1−−+Тем самым теорема доказана.Данный результат имеет различные приложения в теоретическойкибернетике.

Укажем два из них.1301. Для булевой функции f( x1 ,..., xn ) переменные x1 ,..., xt называютсясущественными (в совокупности), если∑ f (α 1 ,..., α t , xt+1,..., xn ) ≠ 0 (сумма по модулю 2).α 1 ,...,α tПример:Булева функция f ( x1 , x2 , x3 , x4 ) = x1 x2 x3 + x1 x4 имеет областисущественных переменных {x1 , x2 , x3 }, {x1 , x2 } , а также области, в нихсодержащиеся.Доказано, что задача нахождения всех областей существенных переменныхпроизвольной булевой функции n переменных равносильна задаче выделенияпроизвольной монотонной функции.2. Для частичной булевой функции F( x1 ,..., xn ) переменные x1 ,..., xtназываются существенными, если существует частичная булева функцияf( x1 ,..., xt ), такая, что f( x1 ,..., xt )=F( x1 ,..., xn ) в области определения функцииF.Пример:Частичная булева функция F( x1 , x2 , x3 , x4 , x5 , x6 ), заданнаятаблицейFx1 x2 x3 x4 x5 x60 0 0 0 0 000 0 1 0 0 110 1 0 0 1 011 0 0 1 0 011 1 1 1 1 11имеет области существенных переменных {x1 , x2 , x3 }, {x4 , x5 , x6 } , а такжеобласти, содержащие по крайней мере одну из них.Доказано, что задача нахождения всех областей существенных переменныхпроизвольной частичной булевой функции n переменных равносильна задачевыделения произвольной монотонной функции.Рассмотрим теперь задачу поиска максимального верхнего нулямонотонной булевой функции.

Верхний нуль α булевой функции f называютмаксимальным верхним нулем, если для любого верхнего нуля β функции fвыполнено β ≤ α ( x - означает число единиц в наборе x).Аналогично предыдущему определяем функцию сложностиµ (E n ) = min max µ (B, f ) ,B∈Bfгде B - класс алгоритмов, решающих данную задачу,µ(B, f ) - число обращений к функции f, достаточное для нахождениямаксимального верхнего нуля функции f при помощи алгоритма B∈B.Имеет местоТеорема 6.1 Справедливо равенство1АН СССР, 1975, т.224, №3, Катериночкина Н.Н.131 nµ(E n ) =   n  + 1 .    2 В данном разделе мы ограничились рассмотрением основных результатов,связанных с доказательством оптимальности алгоритмов. Для знакомства сразвитием данных результатов следует обратиться к журнальной литературе.132§ 20.Оптимальность жадного алгоритмаПредметом данного раздела является выяснение условий оптимальностиопределенного класса алгоритмов.

Предварительно рассмотрим два примера.Пусть дана матрица Α с действительными элементами, где 10 8 4A =  6 7 6 5 6 4и сформулируем следующую оптимизационную задачу.α)Найти такое подмножество S элементов матрицы, для котороговыполнены условия:1) каждый столбец содержит не более одного элемента.2) сумма выбранных элементов максимальна.Будем решать поставленную задачу с помощью, так называемого, жадногоалгоритма, т.е. алгоритма, который на каждом шаге выбирает наибольшийэлемент из возможных.Очевидно, что данный алгоритм даст решение задачи α)S= {a11 , a12 , a 23 } = {10, 8, 6} , причем 10+8+6=24 и данное решение действительнонаибольшее.Рассмотрим другую оптимизационную задачу относительно матрицы А.β )Найти такое подмножество S элементов матрицы А, для котороговыполнены условия:1) каждый столбец и каждая строка матрицы содержит не болееодного элемента множества S.2) сумма выбранных элементов максимальна.Применяя жадный алгоритм к матрице А получим решение задачи β)S= {a11 , a 22 , a 33 } = {10, 7, 4} , причем 10+7+4=21.

Но это не максимальноерешение, т.к. решение S’= {a11 , a 23 , a 32 } = {10, 6, 6} дает 10+6+6=22.В связи с приведенными примерами возникает вопрос: когда жадныеалгоритмы дают оптимальные решения? В данном разделе дается ответ на этотважный в практическом отношении вопрос в терминах матроида. Понятиематроида возникло в ЗО-х годах нашего столетия, и соответствующая теория,лежащая на стыке алгебры и геометрии, получила глубокое развитие, однакорассматривалась как весьма абстрактная и далекая от практического применения.Нам понадобятся предварительные определения.Системой подмножеств S=(Е,J) будем называть конечное множество Евместе с семейством J подмножеств множества Е, замкнутое относительновключения (т.е.