Теормин по методичке 2013 (1133411), страница 3
Текст из файла (страница 3)
е. циклов) сЭК проводимости x1 x2 x1 и x1 x2 x1 является минимальным дизъюнктивным контактнымдешифратором порядка 2.Лемма. Если для ФАЛ f ∈ P2 (n) и ∀σ ∈ {0, 1} ФАЛ fσ (x1 , . . . , xn−1 , σ) 6≡ const, тоССLС&,∨ (f ) = min{L&,∨ (f0 ), L&,∨ (f1 )} + 2.Следствие. LС (µn ) > 2n+1 + n − 1.Замечание. Формула x1 y0 ∨ x1 y1 является минимальной СФЭ, реализующей ФАЛ µ1 иLС (µ1 ) = 4.Следствие. D(µn ) > n + 1.1119. Метод каскадов для КС и СФЭ, примеры его применения.
Метод Шеннона.Метод каскадов позволяет строить КС и СФЭ, многократно использующие «промежуточные результаты».Лемма. ∀n ∈ N и ∀σ ∈ {0, 1} выполняются неравенства 1LК (`σn ) 6 4n − 4 +,nn→−LК ( P 2 (n)) 6 2 · 22 ,→−LК ( J n ) 6 2n+2 − 6.Метод Шеннона позволяет строить КС и СФЭ и установить порядок роста функцийШеннона LС (n) и LК (n).Метод Шеннона основан на разложении Шеннона по q переменным.
При этом мыраскладываем функцию на подфункции от q переменных, которые в разложении домножаσq+1ются на функции вида xq+1· · · xσnn от (n − q) переменных. Все указанные подфункции отq переменных мы реализуем с помощью универсального многополюсника порядка q (т.
е.схемы, которая реализует все функции от q переменных). Потом присоединяем к выходамуниверсального многополюсника, к q информационным входам мультиплексора порядка(n − q), т. е. у него (n − q) адресных переменных, с помощью которых «адресуются»конкретные функции, реализуемые универсальным многополюсником.Полагаем q = blog2 (n − 2 log2 n)c.Теорема.
Для функций Шеннона в классах СФЭ и КС выполяется:LС (n) . 82n,nLК (n) . 42n.n20. Нижние мощностные оценки функций ШеннонаМощностной метод Шеннона основан на том, что число ФАЛ от БП x1 , . . . , xn неменьше числа попарно неэквивалентных схем, сложность которых не превосходит соответствующего значения функции Шеннона от n.Обозначим через U(Ψ, n) множество тех схем Σ ∈ U, которые реализуют одну ФАЛ fиз P2 (n) и для которых Ψ(Σ) 6 Ψ(f ).nИмеет место «мощностное» равенство ||U(Ψ(n), n)|| = 22 .Верхние оценки, установленные ранее (в части II): СU (L, n) 6 (8 (L + n))L+1 ,12 ФU (L, n) 6 (8n)L+1 , КU (L, n) 6 (8nL)L ,LkUπ (L, n)k 6 (12n) , ФDU [D, n] 6 (8n)2 .Лемма. ∀a, y, q ∈ R+ (> 0) : a log q > 1, (ay)y > q ⇒log log(a log q)log q1+,y>log(a log q)log(ae log q)где e — основание натурального логарифма.∀a, y, q ∈ R+ (> 0) : a > 1, ay > q ⇒y>log q.log aТеорема. Для некоторых последовательностей εi = εi (n), где i = 1, 5 и n ∈ N : (εi (n) >0 при n > n0 ), (εi (n) → 0 при n → ∞) для почти всех ФАЛ f ∈ P2 (n) выполняются неравенстваLС (f ) > (1 + ε1 (n))2n,nLФ (f ) > (1 − ε2 (n))2n,log n2n,n2n,Lπ (f ) > (1 − ε4 (n))log nLК (f ) > (1 − ε3 (n))D(f ) > n − log log n − ε5 (n).Следствие.LС (n) &2n,nLФ (n) &2n,log n2n,n2nLπ (n) &.log nLК (n) &1321.
Дизъюнктивно-универсальныемножестваФАЛ.Асимптотически наилучший метод О. Б. Лупанова для синтеза СФЭ в базисе Б0 .Метод О. Б. Лупанова позволяет строить СФЭ и установать асимптотику функцииШеннона LС (n).Множество ФАЛ G ∈ P2 (m) называется дизъюнктивно-универсальным множеством(ДУМ ) порядка m и ранга p, если любая ФАЛ g ∈ P2 (m) м. б. представлена в видеg = g1 ∨ · · · ∨ gp , где gi ∈ G.Метод О. Б. Лупанова также основан на разложении Шеннона по q переменным и такжеиспользует мультиплексор порядка (n − q). Но подфункции от q переменных из разложенияреализуются не универсальным многополюсником, а как дизъюнкция функций из ДУМпорядка q.TODO: построение ДУМ, связанные определения, методичка III часть, стр.
35. mЛемма. ∀m, s ∈ N и p = 2s существует стандартное ДУМ порядка m и высоты s,которое является ДУМ ранга p и для которого:1) λ = |G| 6 p · 2s ;2) система из p характеристических ФАЛ ψ1 , . . . , ψp ДУМ G обладает тем свойством,что ∀ ФАЛ g ∈ P2 (m) и соответствующих ФАЛ g1 , . . . , gp из G справедливо не только представление g = g1 ∨ · · · ∨ gp , но и g = ψ1 g1 ∨ · · · ∨ ψp gp .Теорема. ∀ ФАЛ f ∈ P2 (n) ∃ СФЭ Σf ∈ UС , реализующая f и такая, что2n5 log n + O(1)L(Σf ) 61+.nnСледствие. LС ∼2nn .В классе СФЭ, в отличии от класса ДНФ, имеет место эффект Шеннона, т. к. сложностьLС (f ) ∈ P2 (n) для почти всех ФАЛ f ∈ P2 (n) асимптотически равна функции ШеннонаLС (n), то есть сложности самой сложной ФАЛ из P2 (n).Недостающее••••Вопросы 22—26 в данном файле отсутствуют.Вопросы 25—26 не должны быть в билетах (только как дополнительные вопросы).Частей IV и V (вопросы 27—30) в данном файле нет.Часть V (вопросы 29—30) не должна быть в билетах (только как дополнительныевопросы).14.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
