Оценки параметров почти всех функций. Sapogenko DNF (1133221), страница 2
Текст из файла (страница 2)
Пусть δn — доля тех функций f ∈ Pn , у которых число максимальных интервалов больше, чем число интервалов, не6являющихся максимальными. Показать, что существуют две монотонновозрастающие последовательности {nj }, {mk }, j, k = 1, 2, . . ., такие, чтодля всякого ε > 0 существует N = N (ε) такое, что δnj < ε, δmk > 1 − εдля всех j, k > N .s (n)+s(n)Указание. Рассмотреть отношение ik2 (n)+i k2 +1(n) .k2k2 +1Упражнение 0.3. Пусть ck (f ) —число ядровых интервалов размерn Pности k функции f , а ck (n) = 2−2ck (f ).f ∈Pnkkа) Показать, что ck (n) = nk 2n−k−2 1 − (1 − 2−n+k )2 ;nPб) Пусть c(n) =ck (n).
Показать, что c(n) = n(1−o(1)) log2 log2 n ;k=0в) Показать, что у почти всех функций f (x̃n )nPck (f ) 6 n(1−o(1))log2 log2 n.k=0Дадим теперь верхнюю оценку длины кратчайшей д.н.ф. для почтивсех функций.Пусть Pn (α̃) — множество всех функций f ∈ Pn таких, что f (α̃) = 1.nОчевидно, |Pn (α̃)| = 22 −1 . Пусть Ikn (α̃) — множество k-мерных граней куба B n , содержащих вершину α̃. Обозначим через vk (α̃, f ) число k-мерных интерваловфункции f , содержащихPP вершину α̃. Пустьnnvk (n) = 2−2 +1vk (α̃, f ), а Dvk (n) = 2−2 +1(vk (α̃, f ) − vk (n))2 .f ∈Pn (α̃)f ∈Pn (α̃)kn −2k +12k3k22Утверждение 0.3.
vk (n) = k 2, Dvk (n) 6 n + nvk 2 (n).(k )Доказательство. Аналогично тому, как это делалось при доказательстве утверждения 0.1, получаем, чтоXnvk (n) = 2−2 +1Φ(I),I∈Ikn (α̃)где Φ(I) — число функций f ∈ Pn (α̃) таких, что I ⊆ Nf . Если I ∈ Ikn (α̃),nkто Φ(I) = 22 −2 . Отсюда n −2k +1vk (n) =2.kPnПокажем теперь, что Dvk (n) 6 2−2 +1 · Φ(I, I 0 ), где Φ(I, I 0 ) — числофункций f ∈ Pn (α̃), для которых грани I, I 0 из Ikn (α̃) являются интервалами, а суммирование ведётся по всем парам граней I, I 0 таким, чтоI ∩ I 0 6= {α̃}, I, I 0 ∈ Ikn (α̃).В самом деле,XnDvk (n) = 2−2 +1vk2 (α̃, f ) − vk 2 (n).f ∈Pn (α̃)7Оценим сверху S =vk2 (α̃, f ). Нетрудно видеть, чтоPf ∈Pn (α̃)vk2 (α̃, f ) =XXe(I, I 0 , f ),I∈Ikn (α̃) I 0 ∈Ikn (α̃)где e(I, I 0 , f ) = 1, если I ∪ I 0 ⊆ Nf , и e(I, I 0 , f ) = 0, если I ∪ I 0 6⊆ Nf .ПоэтомуXXXXS=e(I, I 0 , f ) =Φ(I, I 0 ),I∈Ikn (α̃) I 0 ∈Ikn (α̃) f ∈Pn (α̃)(I,I 0 )где суммирование ведётся по всевозможным упорядоченным парам граней I, I 0 из Ikn (α̃).
Разобьём последнюю сумму на две: S = S1 + S2 , гдеXXS1 =Φ(I, I 0 ), S2 =Φ(I, I 0 ).I∩I 0 ={α̃}I∩I 0 6={α̃}nk+1Если I ∩ I 0 = {α̃}, то, очевидно, Φ(I, I 0 ) = 22 −2 +1 . Отсюда 2n −2k +1n n − k 2n −2k+1 +1n2n −1S1 =2622= 22 −1 vk 2 (n).kkkТеперь ясно, чтоn +1Dvk (n) = 2−2n +1(S1 + S2 ) − vk 2 (n) 6 2−2S2 .Оценим S2 .Пусть грани I, I 0 ∈ Ikn (α̃) пересекаются по грани размерности j. Тогдаnk+1jΦ(I, I 0 ) = 22 −2 +2 . Имеем:k Xn n−jn − k 2n −2k+1 +2jS2 =2=jk−jk−jj=1 k n − k 2jn 2n −2k+1 X k=22 .kjk−jj=1j 2jaj+122 (k−j)2Положим aj = kj n−k2.Отношение=меньше 1,aj(j+1)(n−2k+j+1)k−jесли j < blog2 log2 nc, и больше 1, если k > j > blog2 log2 nc. ПоэтомуkX n−1 22kaj 6 k(a1 + ak ) 6 k k2 +2.k−1j=18Таким образом, 2nnk+1S2 622 −2 +1k2k3nk22kk2k 3 k22+ nnk!k2n −1=2vk (n)2k 3 k22+ nnk!,vk 2 (n).(nk)Следствие.
Если k 6 k1 − 1 = dlog2 log2 n + log2 log2 log2 ne − 1, тоDvk (n) < c logn 2 n vk 2 (n), где c — константа. 4Утверждение 0.4. Пусть 1 6 k 6 k1 − 1. Тогда доля δn тех функций f ∈ Pn (α̃), для которых |vk (α̃, f ) − vk (n)| > log1 n vk (n), не превосхоа Dvk (n) 6+23дит c logn2 n .Доказательство. Применяя неравенство Чебышёва и полагаяθ=vk (n),log2 nполучаем утверждение.Утверждение 0.5. Пусть f ∈ Pn , bk (f ) — число тех вершин α̃ ∈ Nf ,k (n)для которых |vk (α̃, f ) − vk (n)| > vlog.
Пусть δn0 — доля тех функций, уnкоторых bk (f ) 6log42 n n2 .n2Тогдаδn0>1−c.log2 nnДоказательство. Оценим среднее bk (n) = 2−2Pbk (f ).f ∈Pnbk (n) = 2−2nXΦ(α̃),α̃∈B nгде Φ(α̃) — число функций таких, что α̃ ∈ Nf и |vk (α̃, f ) − vk (n)| >n −1Но Φ(α̃) = δn 226c log32 n.nvk (n).log2 nc log32 n n2 . В силу леммы 1nlog42 nbk (f ) > n , не превосходит4которых bk (f ) 6 logn2 n 2n , боль-Отсюда bk (n) 6доля тех функций f ∈ Pn , для которыхc/ log2 n. Значит, доля тех функций f , дляше, чем 1 − logc n , что и требовалось доказать.2Теорема 3. [22] Для почти всех функций f (x̃n ) существует д.н.ф.
Dnc·2nдлины l(D) . logи сложности L(D) . cn2.nlog nДоказательство. Рассмотрим подмножество Pn00 ⊂ Pn всех функций f (x̃n ), обладающих√ следующими свойствами:0n−11 . |Nf | 6 2+ n 2n−1 ;420 . bk (f ) < logn2 n 2n для всех k 6 k1 − 2;k −230 . ik1 −2 (f ) = k1n−2 2n−k1 +2−2 1 (1 + δn ), где δn → 0 при n → ∞.9Из следствия 2 и предыдущего утверждения вытекает, что почти всефункции обладают свойствами 10 и 20 .Свяжем теперь с каждой функций f ∈ Pn00 гиперграф Hf = (V, E),в котором V = Nf , а E совпадает с множеством всех интервалов функции f . Пусть F — множество всех интервалов размерностиk = dlog2 log2 n + log2 log2 log2 ne − 2,а Y — множество тех α̃ ∈ Nf , для которых vk (α̃, f ) > vk (n)(1 −41).log2 nПоложим ε = 2 logn 2 n .
Ясно, что условия леммы ?? выполняются, поэтомудлина всякого градиентного покрытия гиперграфа H не превосходит1+c · 2nlog42 n n2 + 2n−k1 +2 (1 + δn ) ln(e2k1 −2 (1 + δn0 )) ∼ k1 2n−k1 +2 ∼.nlog nОтсюда и вытекает утверждение теоремы.Таким образом, у почти всех функций f (x̃n ) длина кратчайшей д.н.ф.удовлетворяет неравенствамc · 2nc1 2n−16 l(f ) 6.log2 n log2 log2 nlog2 nОтметим, что верхняя оценка получена в теореме 3 с помощью градиентного алгоритма. Оказывается, что почти всегда с помощью весьмапростого алгоритма можно получить д.н.ф, «довольно близкую» к кратчайшей.10Литература[1] Яблонский С.
В. Функциональные построения в k-значной логике.Труды МИ АН СССР, 1958, 51, с. 5-142.[2] Яблонский С. В. Введение в теорию функций k-значной логики. Cб.«Дискретная математика и математические вопросы кибернетики»,т.1, М., «Наука», 1974, с. 9-66.[3] Журавлёв Ю. И. Алгоритмы построения минимальных д.н.ф. Сб.«Дискретная математика и математические вопросы кибернетики»,т.1, М., «Наука», 1974, с. 67-98.[4] Васильев Ю.
Л., Глаголев В. В. Метрические свойства д.н.ф. Сб.«Дискретная математика и математические вопросы кибернетики»,т.1, М., «Наука», 1974, с. 99-148.[5] Яблонский С. В. Об алгоритмических трудностях синтеза минимальных контактных схем. Сб. «Проблемы кибернетики», вып.
2,М., Физматгиз, 1960.[6] Карп Р. М. Сводимость комбинаторных проблем. Сб. «Кибернетический сборник», вып. 12 (нов. серия), М., «Мир», 1975.[7] Lubell D. A short proof of Sperner’s lemma. Journ. Comb. Theory 1,N2, 1966.[8] Ансель Ж. О числе монотонных булевых функций n переменных.Сб. «Кибернетический сборник», вып.
5, М., «Мир», 1968, с. 53-57.[9] Викулин А. П. Оценка числа конъюнкций в сокращённой д.н.ф. Сб.«Проблемы кибернетики», вып. 29, М., «Наука», с. 151-166.[10] Гаджиев М. М. Максимальная длина сокращённой д.н.ф. для булевых функций пяти и шести переменных. Сб. «Дискретный анализ»,вып. 18, Новосибирск, 1971, с. 3-24.11[11] Нигматуллин Р. Г. Метод наискорейшего спуска в задачах на покрытие. Сб. «Вопросы точности и эффективности вычислительныхалгоритмов» (труды симпозиума), вып. 5, Киев, 1969, с.
116-126.[12] Глаголев В. В. О длине тупиковой д.н.ф. Мат. заметки, 1967, 2, №6,с. 665-672.[13] Журавлёв Ю. И. Теоретико-множественные методы в алгебре логики. Сб. «Проблемы кибернетики», вып. 8, М., Физматгиз, 1962, с.5-44.[14] Лупанов О. Б. О реализации функции алгебры логики формуламииз конечных классов (формулами ограниченной глубины) в базисе&, ∨, ¬. Сб. «Проблемы кибернетики», вып. 6, М., Физматгиз, 1961,с. 5-14.[15] Васильев Ю.
Л. О сравнении сложности тупиковых и минимальныхд.н.ф. Сб. «Проблемы кибернетики», вып. 10, М., Физматгиз, 1963,с. 5-61.[16] Журавлёв Ю. И. Оценка для числа тупиковых д.н.ф. функций алгебры логики. Сиб. матем. журнал, 1962, 3, №5, с. 802-804.[17] Васильев Ю. Л. О «суперпозиции» сокращённых д.н.ф.
Сб. «Проблемы кибернетики», вып. 12, М., «Наука», 1964, с. 239-242.[18] Коспанов Э. Ш. О произведении кратчайших д.н.ф. Сб. «Дискретный анализ», вып. 18, Новосибирск, 1971, с. 35-40.[19] Левин А. А. Об относительной сложности сокращённой д.н.ф. Сб.«Дискретный анализ», вып. 15, Новосибирск, 1969, с. 25-34.[20] Левин А. А. Об отношении сложности д.н.ф.
функции к сложностид.н.ф. её отрицания. Сб. «Дискретный анализ», вып. 16, Новосибирск, 1970, с. 77-81.[21] Глаголев В. В. Некоторые оценки д.н.ф. функций алгебры логики.Сб. «Проблемы кибернетики», вып. 19, М., «Наука», 1967, с. 75-94.[22] Сапоженко А. А. О сложности д.н.ф., получаемых с помощью градиентного алгоритма. Сб. «Дискретный анализ», вып. 21, Новосибирск, 1972, с.
62-71.[23] Феллер В. Введение в теорию вероятностей и её применения, т.1. М.,«Мир», 1967.12[24] Сапоженко А. А. О наибольшей длине тупиковой д.н.ф. у почти всехфункций. Матем. заметки, 1968, 4, №6, с. 649-658.[25] Лин Синь-Лян. О сравнении сложностей минимальных и кратчайших д.н.ф. для функций алгебры логики. Сб. «Проблемы кибернетики», вып. 18, М., «Наука», 1967, с.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
