Оценки параметров почти всех функций. Sapogenko DNF (1133221)
Текст из файла
Оценки параметров почти всехфункцийОценки длины сокращённой и кратчайшей д.н.ф.для почти всех функцийОценки максимальных значений параметров функций алгебры логики,приведённые ранее, показывают, что существуют весьма «плохие» функции, в том смысле, что процесс их минимизации связан с существенными вычислительными трудностями. Интерес представляет вопрос о том,насколько эти трудности типичны. Оценки параметров для почти всехфункций, приводимые ниже, показывают, что основные трудности решения задачи минимизации сохраняются.Определение. Пусть pn (Q) — число функций f ∈ Pn , обладающихсвойством Q. Говорят, что почти все функции алгебры логики обладаютnсвойством Q, если lim pn (Q)2−2 = 1.n→∞При оценке параметров почти всех функций существенную роль будут играть леммы о средних значениях и неравенства типа неравенстваЧебышёва.Пусть A = {a1 , a2 , .
. . , as } — конечное множество, а ϕ — функция,ставящая в соответствие каждому a ∈ A неотрицательноечисло ϕ(a).Pϕ(a) — среднее значениеБудем обозначать через ϕ = ϕ(A) число 1sa∈APфункции ϕ на множестве A, а через Dϕ — число 1s(ϕ(a) − ϕ)2 —a∈Aсреднее квадратическое отклонение или дисперсию функции ϕ.Лемма 1. Пусть θ > 0 и δθ — доля тех a ∈ A, для которых ϕ(a) > θϕ.Тогда δθ 6 1θ .Доказательство.ϕ=1X1ϕ(a) >s a∈AsXa:ϕ(a)>θϕ11ϕ(a) > sδθ θϕ > ϕδθ θ,sчто и требовалось.Следствие. Пусть p(f ) — целочисленный неотрицательныйпараn Pp(f ) стремитсяметр, заданный на множестве Pn .
И пусть p(n) = 2−2f ∈Pnк 0 с ростом n. Тогда p(f ) = 0 для почти всех функций. 4Лемма 2. (Неравенство Чебышёва). Пусть θ > 0 и δθ — доля техa ∈ A, для которых |ϕ(a) − ϕ| > θ. Тогда δθ 6 Dϕ.θ2Доказательство.X1X1(ϕ(a) − ϕ)2 >Dϕ =(ϕ(a) − ϕ)2 > δθ θ2 .s a∈Asa:|ϕ(a)−ϕ|>θОтсюда и вытекает утверждение.Утверждение 0.1. Пусть ik (f ) —Pчисло интервалов размерностиkn n−k−2k−2nфункции f ∈ Pn , и пусть ik (n) = 2ik (f ).
Тогда ik (n) = k 2.f ∈PnДоказательство. Пусть Ikn = {Ij , j = 1, nk 2n−k } — множество всехграней размерности k куба B n . Введём функцию(1, если I ⊆ Nf ,e(I, f ) =0, если I 6⊆ Nf ,определённую на парах (I, f ), I ∈ Ikn , f ∈ Pn . Пусть Φ(I) — число функций f ∈ Pn таких, что I ⊆ Nf . ТогдаXX XXnnnik (n) = 2−2ik (f ) = 2−2e(I, f ) = 2−2Φ(I).f ∈Pn I∈Iknf ∈PnI∈IknnkkНетрудно подсчитать, что Φ(I) = 22 −2 . Поэтому ik (n) = 2n−k−2 nk , чтои требовалось.2n Pik (f ) − ik (n) — дисУтверждение 0.2. Пусть Dik (n) = 2−2f ∈Pnперсия параметра ik (f ). ТогдаDik (n) = 2n−2k+1 Xk nn n−kj(22 − 1).k j=0 jk−jДоказательство.
Пусть Ikn — множество k-мерных граней куба B n .Рассмотрим функцию e(I, I 0 , f ), определённую на тройках вида (I, I 0 , f ),где I, I 0 ∈ Ikn , f ∈ Pn , такую, что(1, если I ∪ I 0 ⊆ Nf ,e(I, I 0 , f ) =0, если I ∪ I 0 6⊆ Nf .2Пусть Φ(I, I 0 ) — число функций f ∈ Pn таких, что I ∪ I 0 ⊆ Nf .
Нетрудnk+1jно видеть, что если |I ∩ I 0 | = 2j , то Φ(I, I 0 ) = 22 −2 +2 = Φj . Еслиnk+1же |I ∩ I 0 | = 0, то Φ(I, I 0 ) = 22 −2= Φ∅ . Преобразуем выражениедля Dik (n).nDik (n) = 2−2X2(i2k (f ) − 2ik (f )ik (n) + ik (n)) =f ∈Pnn= 2−2X2i2k (f ) − ik (n). (1)f ∈PnПодсчитаем S =Pf ∈PnS=i2k (f ). Имеем:X Xe(I, I 0 , f ) =I,I 0 ∈Ikn f ∈PnXΦ(I, I 0 ) =I,I 0 ∈Iknk Xn n−j n − jn−k=2Φj +jk−jk−jj=0 2 X!k n n−kn n−j n − jn−k+2−2Φ∅ =kjk−jk−jj=0 2k n n−k−2kn n−2k +2n X kn − k −j 2j2n=22 (2 − 1) + 22.kjk−jkj=0В последнем переходе использовалось равенствосюда и из (1) вытекает утверждение.njn−jk−j=nk kj.
От-Теорема 1. [21] Пусть ψ(n) → ∞ при n → ∞. Тогда для почти всехфункций алгебры логики f (x̃n ) число k-мерных интервалов функции fудовлетворяет неравенствам: ppnnkkn−k−2kn−k−22− ψ(n) 2< ik (f ) <2n−k−2 + ψ(n) 2n−k−2k .kk(2)Доказательство.Воспользуемся неравенством Чебышёва, положив√knn−k−2θ = ψ(n) k 2.
Необходимо показать, что Dik (n)/θ2 → 0 приjn → ∞. Оценим Dik (n). Величина aj = 2−j (22 − 1) возрастает по j,3посколькуaj+1ajj= 12 (22 + 1) > 1. Поэтому k n n−2k+1 X kn−kDik (n) =2aj 6kjk−jj=0 2k Xn n−2k+1 −k 2kkn−knk622 (2 − 1)62n−k−2 .kjk−jkj=0Отсюда Dik (n)/θ2 6 ψ −2 (n) → 0 при n → ∞.Следствие 1. У почти всех функций f (x̃n ) нет интервалов размерности большей, чем dlog2 ne.В самом деле, положим для краткости k0 = dlog2 ne, и пусть ψ(n) = n.Тогдаpnk0 +1n−k0 −1−2k0 +1n−k−1−20ik0 +1 (f ) <2.+n 2k0 + 1Выражение в правой части стремится к нулю с ростом n.
Следовательно,у почти всех функций f (x̃n ) нет интервалов размерности dlog2 ne + 1, азначит, и интервалов большей размерности.Следствие 2. Для почти всех функций√√2n−1 − n 2n−1 6 |Nf | 6 2n−1 + n 2n−1 .В самом деле, заметим, что |Nf | = i0 (f ). Тогда утверждение вытекаетиз теоремы 1, если положить в ней ψ(n) = n.Следствие 3. Пусть k1 = dlog2 log2 n + log2 log2 log2 ne, а Qk1 (f ) — число вершин α̃ ∈ Nf , содержащихся хотя бы в одном интервале функции fразмерности большей, чем k1 . Тогда у почти всех функцийQk1 (f ) 6 n−(1−δn ) log2 log2 n · 2n ,где δn → 0 при n → ∞.В самом деле, пусть Q0k1 (f ) — число вершин α̃ ∈ Nf , содержащихся хотя бы в одном интервале размерности, равной k1 + 1. Ясно, чтоQk1 (f ) = Q0k1 (f ) 6 2k1 +1 · ik1 +1 (f ), но у почти всех функций1k +1ik1 +1 (f (x̃n )) 6 ik1 +1 (n) 1 + ψ(n)2− 2 (n−k1 −1−2 1 ) .Полагая ψ(n) = n, получим для произвольного ε и достаточно больших nnk +1Qk1 (f ) 62n−2 1 (1 + ε) 6 (1 + ε)nk1 +1 2n−2 log2 n log2 log2 n 6k1 + 16 n−(1−δn ) log2 log2 n 2n , где δn → 0 при n → ∞.4Следствие 4.
Пусть k2 = blog2 log2 nc, i(f ) — число всех интерваловфункции f . Тогда для почти всех функций f (x̃n ) n n−k2 −2k2nn−k2 −1−2k2 +1i(f ) =2+2(1 + δn ),k2k2 + 1где δn → 0 при n → ∞.(n)n−k= (k+1)2. Ясно, что λk → ∞Рассмотрим отношение λk = ik+12k +1ik (n)при k < k2 и λk → 0 при k > k2 . Для достаточно больших n λk > 1при k < k2 и λk < 1 при k > k2 .
Поэтому max ik (n) достигается либо приkk = k2 , либо при k = k2 + 1.Полагая в (2) ψ(n) = n, получим, что для почти всех функций f (x̃n )и k 6 dlog2 neik (n)(1 − δn ) < ik (f ) < ik (n)(1 + δn ),где δn → 0 при n → ∞. Суммируя эти неравенства по k, 0 6 k 6 dlog2 ne,и учитывая, что λk > nc , c > 0 при k < k2 и λk < (log2 log2 n)−1 при k > k2 ,получим, что для почти всех функций(ik2 (n) + ik2 +1 (n))(1 − δ 0 (n)) < i(f ) < (ik2 (n) + ik2 +1 (n))(1 + δ 0 (n)),где δ 0 (n) → 0 при n → ∞.Следствие 5. Для почти всех функций f (x̃n )i(f ) = n(1−δn ) log2 log2 n 2n , где δn = O log1 n .2Вытекает из предыдущего следствия. 4ik (n)n(1−o(1))k2 · 2n2n−1k2k1k0 kНа рис.
1 показана зависимость ik (n) от k. Из теоремы 1вытекает, что для почти всехфункций f (x̃n ) параметр ik (f )зависит от k подобным же образом.Рис. 1Следствие 6. Для почти всех функций f (x̃n ) число максимальныхинтервалов не превосходит n(1−o(1)) log2 log2 n 2n . 4Следствие 7. Пусть lM (f ), l(f ) — длины, а L(f ), Lκ (f ) — сложностиминимальной и кратчайшей д.н.ф. функции f .
Тогда для почти всехфункций f (x̃n )lM (f ) = l(f )(1 + δn ),Lκ (f ) = L(f )(1 + δn0 ),5L(f ) = nl(f )(1 + δn00 ),где δn , δn0 , δn00 → 0 при n → ∞.В силу следствия 1 имеем:(n − dlog2 ne) l(f ) 6 (n − dlog2 ne) lM (f ) 6 L(f ) 6 Lκ (f ) 6 nl(f ).Отсюда и вытекает утверждение.Таким образом, для получения асимптотических оценок параметровMl (f ), l(f ), L(f ), Lκ (f ) достаточно найти асимптотическую оценку одного из параметров, например, l(f ).Теорема 2. [21] Для почти всех функций f (x̃n )L(f ) &cn2n−1,log2 n log2 log2 nl(f ) &c · 2n−1,log2 n log2 log2 n1< c < 1.2Доказательство. Рассмотрим подмножество Pn0 функций f ∈ Pn ,обладающих следующими√ свойствами:0n−11 .
|Nf | > 2− n · 2n−1 ,0−(1+o(1)) log2 log2 n n2 . Qk1 (f ) 6 n2 .nИз следствий 1,2,3 вытекает, что lim |Pn0 |2−2 = 1. Покажем, что дляn→∞всякой функции f ∈ Pn0 любое покрытие множества Nf интерваламиn−1имеет мощность > log nc·2log log n . В самом деле, из свойств 10 и 20 вытекает,222что по меньшей мере 2n−1 (1 − o(1)) вершин множества Nf покрываютсялишь интервалами размерности не большей, чемk1 = dlog2 log2 n + log2 log2 log2 ne .|N |−Q(f )n−1Отсюда l(f ) > f 2k1k1 > log nc·2log log n .222Упражнение 0.1. Пусть sk (f ) — число максимальных интерваловразмерности k функции f . ПустьXXnnsk (n) = 2−2sk (f ), Dsk (n) = 2−2(sk (f ) − sk (n))2 .f ∈Pnf ∈PnПоказать, что kkа) sk (n) = nk 2n−k−2 (1 − 2−2 )n−k ;2kб) Dsk (n) 6 (n2 + 1) nk 2n−k−2 ;в) Для почти всех функций f (x̃n ) и k < dlog2 ne sk (f ) ∼ sk (n);nPг) Для почти всех функций f (x̃n )sk (f ) ∼ sk2 (n) + sk2 +1 (n),k=0k2 = dlog2 log2 ne.Упражнение 0.2.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
