Теормин по методичке 2013 (1133411), страница 2
Текст из файла (страница 2)
Аналогично понимаетсяпокрытие одного множества строк M другим множеством строк.Покрытие матрицы M , в котором ни одна строка не покрывается другой строкойназывается неприводимым. Покрытие, не имеющее собственных подпокрытий, называетсятупиковым.ФАЛ F (y) называется функцией покрытия матрицы M без нулевых столбцов, еслиF (β) = 1 ⇔ когда система строк матрицы M с номерами из I(β) = {i|βhii = 1} образует еёпокрытие.Лемма.
Функция покрытия F (y1 , . . . , yp ) матрицы M ∈ B p,s без нулевых столбцов задаётся КНФ видаF (y1 , . . . , yp ) =s^j=1_yi .16i6pM hi,ji=15Следствие. В результате раскрытия скобок и приведения пободных из КНФ для F (см.лемму) можно получить сокращённую ДНФ ФАЛ F (y), простые импликанты которойвзаимно однозначно соответствуют тупиковым покрытиям матрицы M .Задача построения всех тупиковых ДНФ ФАЛ f на основе её сокращённой ДНФ сводится к рассмотренной выше задаче о покрытии, если N = Nf , а N — система всех максимальных граней f .5.
Градиентный алгоритм и оценка длины градиентногопокрытия, лемма о «протыкающих» наборах. Использование градиентного алгоритма для построения ДНФ.Градиентный алгоритм ориентирован на выделение из заданного покрытия достаточно«коротких» подпокрытий или, иначе, на построение достаточно «коротких» покрытий длязаданной матрицы.Шаг: в матрице выбирается и включается в покрытие такая строка, которая покрываетнаибольшее число ещё не покрытых столбцов (если таких строк несколько, из них выбирается строка с наименьшим номером).Останов: после того шага, на котором получилось покрытие.Теорема.
Пусть для действительного γ, 0 < γ 6 1, в каждом столбце матрицыM ∈ M p,s имеется не меньше чем γ · p единиц. Тогда покрытие матрицы M , получаемое с помощью градиентного алгоритма, имеет длину не больше чем d γ1 ln+ (γs)e + γ1 , гдеln+ (x) = 0 при 0 < x < 1 и ln+ (x) = ln(x) при x > 1.Задача о «протыкании» системы N, состоящей из подмножеств N1 , . . . , Np множестваN = {α1 , . . . , αs }, заключается в нахождении такого подмножества множества N , в котором∀i ∈ [1, p] имеется хотя бы один элемент из Ni .Лемма. ∀m, n ∈ N, m 6 n в кубе B n всегда найдётся подмножество мощности не болеечем n · 2m , протыкающее все грани ранга m.6.
Задача минимизации ДНФ. Поведение функции Шеннона и оценки типичных значений для ранга и длиныДНФ.На множестве ДНФ задаётся неотрицательный функционал сложности ψ, обладающийсвойством монотонности, т. е. ∀ДНФ A ∃ψ(A) > 0 : ψ(A0 ) > ψ(A00 ), если ДНФ A00получается из ДНФ A0 удалением букв или ЭК.Примеры: длина λ(A), ранг R(A), «формульная» сложность L(A).Задача минимизации ДНФ относительно функционала сложности ψ состоит в нахождении для заданной ФАЛ f ДНФ A, такую что ψ(A) = min ψ(A0 ), где минимум берётся повсем ДНФ A0 ФАЛ f .6При этом ДНФ A называется минимальной относительно функционала ψ илиψ-минимальной ДНФ.
Значение ψ(A) называется сложностью ФАЛ f относительнофункционала ψ или ψ-сложностью ФАЛ f в классе ДНФ.λ-минимальную (по длине) ДНФ будем называть кратчайшей, а R-минимальную (порангу) — просто минимальной.Функция Шеннона для класса ДНФ относительно функционала ψ:ψ(n) = max ψ(f ).f ∈P2 (n)Лемма. ∀n ∈ N имеют место соотношения λ(n) = 2n−1 , R(n) = n · 2n−1 .Рассмотрим отрезок [ψ 0 (n), ψ 00 (n)], в который попадают значения ψ(n) для почти всехФАЛ f ∈ P2 (n). Если границы ψ 0 (n) и ψ 00 (n) асимптотически равны ψ(n), то говорят, чтодля параметра ψ имеет место эффект Шеннона.Для параметров λ и R эффект Шеннона отсутствует.Попытка интерпретации стр. 50—51. Вообще, вряд ли это будет в теорминена «3».Введём дискретную векторную случайную величину ξ состоящую из 2n случайныхвеличин, принимающих с равной вероятностью значение 0 или 1.
Введём дискретнуюe равную сумме элементов ξ.случайную величину ξ,Каждая реализация ξ соответствует какой-либо ФАЛ f от n переменных (равна еёвектору значений). Если зафиксировать реализацию ξ и соответствующую ФАЛ f , тосоответствующая реализация ξe будет равна мощности множества Nf для ФАЛ f .Eξe = 2n−1 , отступим влево и вправо на t = dn · 2n/2 e, получим интервалI = (2n−1 − t, 2n−1 + t).Применяем к случайной величине ξe неравенство Чебышева и устанавливаем, что долятех ФАЛ f ∈ P2 (n), для которых |Nf | 6∈ I стремится к 0 при n → ∞.Это означает, что для почти всех ФАЛ f ∈ P2 (n) выполнено (для проверки раскрытьскобки)|Nf | = 2n−1 1 ± O n · 2−n/2 .То есть длина совершенной ДНФ у почти всех ФАЛ из P2 (n) асимптотически равна2n−1 .Лемма.
Для почти всех ФАЛ f ∈ P2 (n) выполняются неравенстваλ(f ) 63 n−1·21 + O n · 2−n/2 ,4R(f ) 63n · 2n−1 1 + O n · 2−n/2 .477. Алгоритмические трудности минимизации ДНФ иоценки максимальных значений некоторых связанныхс ней параметров. Теорема Ю. И. Журавлёва о ДНФсумма минимальных.Функция Шеннона для параметра ψ в классе ДНФ: ψ(n) = max ψ(f ).f ∈P2 (n)Обозначим значение функции Шеннона для следующих параметров: число тупиковыхДНФ — τ (n), число минимальных ДНФ — µ(n) и длина сокращённой ДНФ у ФАЛ из P2 (n)— λсокр.
(n) (ДНФ рассматриваются с точностью до перестановки ЭК и букв в них).Лемма. Для ФАЛ f из P2 (n), n > 4, вида f (x1 , . . . , xn ) = g(x1 , x2 , x3 ) · (x4 ⊕ · · · ⊕ xn ), гдеn−4N g = {(000), (111)}, число тупиковых (минимальных) ДНФ равно 52(соответственноn−422).n−4Следствие. τ (n) > 52n−4, µ(n) > 22.Выберем множество номеров I ⊆ [0, n], зафиксируем объединение всех слоёв куба B n сномерами из I, обозначим характеристичесую функцию этого объединения как sIn . Числаиз I назовём рабочими числами ФАЛ sIn .ФАЛ sIn является симметрической, т.
е. не изменяет своё значение при любой перестановке аргументов. Наоборот тоже верно: любая симметрическая ФАЛ совпадает с однойиз ФАЛ вида sIn .Симметрическая ФАЛ, отличная от константы, является существенной. Рабочимичислами симметрических ФАЛ `n и `n являются все нечётные и все чётные числа отрезка[0, n] соответственно.Симметрическая ФАЛ является поясковой, если её рабочие числа образуют отрезок.
Видеё сокращённой ДНФ:_σn+r−p.s[r,p]xσi11 · · · xin+r−pn (x1 , . . . , xn ) =16i1 <···<in+r−p 6nσ1 +···+σn+r−p =rnЛемма. λсокр. (n) > e1 3n , где e1 — некоторая константа.Функция f (x1 , . . . , xn ) называется цепной (циклической) функцией длины t, если её сокращённая ДНФ с «геометрической» т. з. представляет собой цепь (соответственно цикл)из t последовательно соединённых рёбер N1 , . .
. , Nt куба B n .Теорема. ∀n ∈ N, n > 3, в P2 (n) существуют ФАЛ f 0 и f 00 , имеющие общую простуюимпликанту K, которая входит в ДНФ ΣM одной, но не входит в ДНФ ΣM другой изэтих ФАЛ и для которой Sn−3 (NK , f 0 ) = Sn−3 (NK , f 00 ).Недостающее• Часть II (вопросы 8—16) в данном файле отсутствует.8• Вопрос 16 не должен быть в билетах (только как дополнительный вопрос).Часть IIIСинтез и сложность управляющихсистем17. Задача синтеза. Методы синтеза схем на основе ДНФи связанные с ними верхние оценки сложности функций.Введём обозначения: U — некоторый полный класс схем (из рассмотренных во II части),Ψ > 0 — функционал сложности схем класса U со свойством монотонности.Сложность системы ФАЛ F относительно функционала Ψ в классе U: Ψ(F ) =minΨ(Σ).
При этом схема Σ, реализующая F , для которой Ψ(Σ) = Ψ(F ), называ-Σ∈U реализ. Fется минимальной схемой в классе U относительно Ψ.Если функционал Ψ совпадает с L, D, R (введены во II части), будем называть егосложностью, глубиной, рангом системы ФАЛ F соответсвенно.Функция ШеннонаΨ(n) = max Ψ(f ).дляклассаUотносительнофункционаласложностиΨ:f ∈P2 (n)Будем обозначать сложность и функцию Шеннона для некоторого класса A как ΨAБ (F )и ΨAБ (n) соответственно, будем опускать нижний индекс Б, если Б = Б0 .ФКπЕсли U0 ⊇ U00 , то Ψ0 (F ) 6 Ψ00 (F ).
В частности ΨСБ (F ) 6 ΨБ (F ) и ΨБ (F ) 6 ΨБ (F ).Для сложности системы ФАЛ F = (f1 , . . . , fm ) в любом из рассматриваемых классовmPсхем выполняется max L(fi ) 6 L(F ) 6L(fi ).16i6mi=1Лемма (моделирование совершенной ДНФ). ∀ ФАЛ f (x1 , . . . , xn ) 6≡ 0 ∃ формула Ff ∈UФ и π-схема Σf ∈ Uπ , реализующие ФАЛ f , для которых выполняетсяL(Ff ) 6 2n · |Nf | − 1,L(Σf ) 6 n · |Nf |.Следствие.
Если учесть, что ФАЛ 0 можно реализовать π-схемой и формулой из UФ ,имеющими сложность 2, то выполняетсяLС (n) 6 LФ (n) 6 n · 2n+1 − 1,LК (n) 6 Lπ (n) 6 n · 2n .9Следствие. D(n) 6 n + dlog2 (n)e + 2.Получается из доказанного в части II соотношения для подобных формул с поднятымиотрицаниями D(F̆) 6 dlog2 (L(F) + 1)e + Alt(F).Лемма (моделирование совершенной ДНФ с использованием КД). ∀ ФАЛ f (x1 , .
. . , xn ) 6≡0 ∃ формула Ff ∈ UФ и π-схема Σf ∈ Uπ , реализующие ФАЛ f , для которых выполняетсяL(Ff ) 6 2n+1 + |Nf | − 4,L(Σf ) 6 2n + |Nf | − 2.Следствие.LФ (n) 6 3 · 2n − 4.Lπ (n) 6 2n+1 − 2,Результатом применения операции присоединения вершины v к вершине w называетсяСФЭ Σ0 , получаемая из СФЭ Σ в результате удаления вершины v, переноса началаисходивших из v дуг в w и переноса всех выходных БП v в w.Две вершины СФЭ называются эквивалентными, если в них реализуются равные ФАЛ.Приведённая (т. е. без висячих вершин) схема называется строго приведённой, если вней нет эквивалентных вершин.
Из любой СФЭ можно получить эквивалентную ей строгоприведённую СФЭ с помощью операции присоединения эквивалентных вершин и операцииудаления висячих вершин.Аналогичным образом определяется операция присоединения вершин в КС, с тойлишь разницей, что на неё не накладываются какие-либо ограничения, связанные сдостижимостью вершин.→−Для множества ФАЛ G ⊆ P2 (n) через G будем обозначать систему, состоящую изразличных ФАЛ множества G, упорядоченных в соответствии с номерами их столбцовзначений.Обозначения дял некоторых функций порядка n:• `n и `n — линейные ФАЛ;• µn — мультиплексорная ФАЛ;→−→−• Q n и J n — дешифратор и дизъюнктивный дешифратор;→−• P 2 (n) — универсальная система.Лемма. ∀n ∈ Nn22 − n.→−∃ СФЭ Un ∈ UСБ , которая реализует систему ФАЛ P 2 (n), сложности→−2nСледствие.
LС− n.Б P 2 (n) 6 218. Нижние оценки сложности ФАЛ, реализация некоторых ФАЛ и минимальность некоторых схем.Лемма. Если ФАЛ f (x1 , . . . , xn ) существенно зависит от всех своих БП, тоLС (f ) > n − 1,10LК (f ) > n.Если при этом ФАЛ f не является монотонной ФАЛ, тоLС (f ) > n,Если есть существенная зависимость от всех своих БП и каждая БП xi , i ∈ [1, k], неявляется ни монотонной, ни инмонотонной БП ФАЛ f , тоLК (f ) > n + k.Следствие.LС (`n ) > n,LК (`n ) > 2n,LС (µn ) > 2n + n,LК (µn ) > 2n + 2n.Замечание. Формула f = (x1 · · · xn ) и π-схема, моделирующая ЭД f = x1 ∨ · · · ∨ xn ,являются минимальными в классах СФЭ и КС соответственно, при этом LС (f ) = n,LК (f ) = n.Лемма.
Для системы F = (f1 , . . . , fm ), состоящей их попарно различных ФАЛ от переменных (от констант), справедливоLС (F ) > m(соответственно LК (F ) > m).Следствие.→− LС Q n > 2n ,→− LС J n > 2n ,n→−LС P 2 (n) > 22 − n,→− LК Q n > 2n ,→− LК J n > 2n ,n→−LК P 2 (n) > 22 − 2.→− →−Лемма. ∀n ∈ N выполняются неравенства [тут было много верхних оценок для Q n , J n ,µn , `n и `n в разых классах, но формулировка билета не предусматривает верхних оценок.]→−→−Следствие. LС ( Q n ) ∼ LС ( J n ) ∼ 2n .Лемма. Если система ФАЛ F = (f1 , . . . , fm ) состоит из попарно различных ФАЛ от БПmPX(n), отличных от 0 и 1, то LК (F ) > 21−n|Nfj |.j=1Кn+1Следствие. L (Jn ) > 2− 2.Замечание. (1, 4)-КС с входом a из двух непересекающихся (a—a)-цепей (т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
