А.А. Сапоженко - Некоторые вопросы сложности алгоритмов (PDF) (1132758), страница 2
Текст из файла (страница 2)
В силу (3) имеем| Qσ (k) |= 2σ2k (1+² )k,(7)где ²k → 0 при k → ∞. Можно считать, что функции f (x1 , x2 , . . . , xk ) из Q(k)пронумерованы числами от 1 до mk , где mk = |Q(k)|. Функции fi поставим всоответствие двоичный вектор (ti1 , ti2 , . . . , til ) длины l = dlog mk e, являющийсядвоичным разложением числа i−1, i = 1, . . . , mk . Этот вектор назовем кодомфункции f (x1 , x2 , . .
. , xk ). В силу (7) имеемl = dlog mk e = σ2k (1 + ²k ).Покажем, как вычислить значение произвольной функции f (x1 , x2 , . . . , xn ) изQ(n) на произвольном наборе (α1 , α2 , . . . , αn ). Разложим f (x1 , x2 , . . . , xn ) попоследним n − k переменным:f (x1 , x2 , . . . , xn ) =_αk+1xk+1, . .
. , xαnn &f (x1 , . . . , xk , αk+1 , . . . , αn ).(8)(αk+1 ,...,αn )Ясно, что функция f однозначно определяется набором из 2n−k своих подфункций f (x1 , . . . , xk , αk+1 , . . . , αn ), каждая из которых принадлежит множеству Q(k), а, значит, имеет свой код. Этот код однозначно определяется набором (αk+1 , . . . , αn ). Следовательно, для определения кода (ti1 , . . . , til )достаточно вычислить l функций от n − k переменных. По коду подфункции однозначно восстанавливается вектор ее значениий. Для этого достаточно вычислить 2k булевых функций, зависящих от переменных (ti1 , . . . , til )Далее, по вектору значений подфункции f (x1 , . . .
, xk , αk+1 , . . . , αn ) и вектору(α1 , . . . , αk ) значений переменных x1 , . . . , xk , однозначно определяется значение функции f (α1 , . . . , αk , αk+1 , . . . , αn ).В соответствии с вышесказанным можно следуюшим образом построитьсхему Sf , реализующую функцию f и состоящую из трех блоков (см. рис.1).Блок A вычисляет код (ti1 , . . . , til ) подфункции f (x1 , . .
. , xk , αk+1 , . . . , αn )по значениям αk+1 , . . . , αn переменных xk+1 , . . . , xn , т.е. вычисляет l функцийэтих переменных.7Положив k = d 12 log2 ne, в силу (5) получаем, что для сложности L(A)блока A выполнено следующее:L(A) ≤ l2n−k2n2n−k(1 + δn−k ) ≤ σ2k (1 + ²k )(1 + δn−k ) ∼ σ .n−kn−kn(9)Рис.1Блок B вычисляет по коду подфункции вектор ее значениий, т.е.
вычисляет 2k булевых функций, зависящих от l переменных. В силу (5) получаем,что сложность L(B) блока B удовлетворяет неравенствуlk2kµ¶2σ(1+²k )2kL(B) ≤ 2 (1 + δl ) ≤ 2(1 + δl ) = O 2σ(1+²k )2 .klσ(1 + ²k )2k(10)Блок C по столбцу значений подфункции f (x1 , . . . , xk , αk+1 , . . . , αn ) и вектору (α1 , . . . , αk ) вычисляет f (α1 , . . . , αk , αk+1 , . . . , αn ). Тем самым он вычисляет некоторую булеву, зависящую от k + 2k переменных.
В силу (5) получаем, для сложности L(C) блока C следующее неравенствоk22 +k(1 + δ2k +k ).L(C) ≤ k2 +k8(11)Из (9) — (11) вытекает, чтоL(Sf ) ≤ L(A) + L(B) + L(C) ≤ σОтсюда следует утверждение.√2n+ 2O( n) ).n2Определение 2.2 Последовательность функций f1 (x1 ), f2 (x1 , x2 ), . . . ,fn (x1 , . . . , xn ), . . . , называется сложной, если L(fn ) = L(n).Определение 2.3 Алгоритм A, строящий бесконечную последовательностьбулевых функций {fi (x1 , . . . , xi )}∞i=1 из P2 называется правильным, еслион строит все функции минимального инвариантного класса, содержащегоэту последовательность.Теорема 2.6 (С.
В. Яблонский) Любой правильный алгоритм, строящийсложную последовательность функций {fi (x1 , . . . , xi )}∞i=1 функций из P2 ,строит все множество P2 .Доказательство.Предположим противное. Тогда последовательность {fi (x1 , . . . , xi )} самыхсложных функций содержится в некотором инвариантном классе Qσ 6= P2 .При этом σ < 1 в силу cледствия 2.1. По Теореме 6 для любой функцииng ∈ Qσ (n) можно построить СФЭ Sg такую, что L(Sg ) ≤ σ 2n (1 + ∆n ). Нокласс Qσ содержит некоторую самую сложную функцию f (x1 , . .
. , xn ), длякоторой в силу (5) имеем L(f ) = L(n) > (1 − δn )2n /n, где δn → 0 при n → ∞.При достаточно больших n приходим к противоречию.2Список литературы[1] С.В.Яблонский, О невозможности элиминации перебора всех функций изP2 при решении некоторых задач теории схем// ДАН СССР, 124, 1, 1959,C.44-47.[2] С.В.Яблонский, Об алгоритмических трудностях синтеза минимальныхконтактных схем// В сб. Проблемы кибернетики, М: Наука, Вып. 2,С.75-121.[3] О.Б.Лупанов, Асимптотические оценки сложности управляющих систем,Изд-во МГУ, 1984.93Локальные алгоритмыВ параграфе дается понятие локального алгоритма, введенное Ю.И.Журавлевым (см. [1] и [2]), и излагаются некоторые результаты из теории локальных алгоритмов. В частности, доказывается неразрешимость в классе локальных алгоритмов произвольного конечного индекса задачи о вхожденииконъюнкции из сокращенной ДНФ булевой функции в хотя бы в одну минимальную ДНФ этой функции.В первой части параграфа дается определение локального алгоритма идоказываются утверждения о распознавании свойств конъюнкций входитьв тупиковые ДНФ.
Показано, что свойства конъюнкции “входить в во всетупиковые” или “входить хотя бы в одну тупиковую ДНФ” произвольнойфункции можно осуществить с помощью локального алгоритма ограниченного индекса, т.е. на основе информации о строении некоторой окрестностиограниченного порядка рассматриваемой конъюнкции (см. следствия 3.1 и3.2). Во второй части доказывается, что свойство конъюнкции входить хотябы в одну минимальную ДНФ не распознается в общем случае алгоритмамилюбого конечного индекса (следствие 3.4). Изложение ведется с некоторымиупрощениями по сравнению с [2].О вхождении конъюнкции в тупиковые ДНФНиже речь идет о локальных алгоритмах, предназначенных для упрощения ДНФ.
Входом алгоритма является сокращенная ДНФ. Алгоритм расставляет отметки над конъюнкциями. Отметки несут информацию о выполненииили невыполнении некоторых свойств. Вычисление отметок носит локальныйхарактер в том смысле, что значение пометок является однозначной функцией окрестности рассматриваемой конъюнкции и пометок конъюнкций изэтой окрестности. Понятие окрестности конъюнкции в ДНФ определяется поиндукции.Определение 3.1 Окрестность S0 (K, D) нулевого порядка конъюнкции K в ДНФ D определяется равенствомS0 (K, D) = {K}.Пусть окрестность Sr (K, D) порядка r ≥ 0 конъюнкции K в ДНФ D ужеопределена. Тогда окрестность порядка r + 1 конъюнкции K в ДНФ Dопределяется равенствомSr+1 (K, D) = {L ∈ D : ∃K ∈ Sr (K, D) : NK ∩ NL 6= ∅}.10Пример.
Пусть D = Dfсок р = K1 ∨∨K2 ∨ K3 ∨ K4 , гдеK1 = x̄1 x̄2 ,K2 = x̄1 x3 ,K3 = x2 x3 ,K4 =x1 x2 . Тогда (см. рис. ??) S0 (K2 , D) =K2 , S1 (K2 , D) = {K1 , K2 , K3 } и Sr (K2 , D) ={K1 , K2 ,K3 , K4 }, при r ≥ 2.Ниже рассматриваются следующиесвойства конъюнкций K:01 K входит во все тупиковые ДНФ функции f .20 K входит в хотя бы в одну тупиковую ДНФфункции f .03 K входит в хотя бы в одну минимальнуюРис.2ДНФ функции f .Значения функции ϕi , вычисляющей пометку, относящуюся к свойствуi = 1, 2, 3, выбираются следующим образом: 1,если свойство выполнено,ϕi (K, Sr (K, D)) = 0, если свойство не выполнено,−, если неизвестно, выполнено ли свойство.Функции ϕi обладают следующим свойством локальности: Для любых двухДНФ D и D0 , содержащих слагаемое K, выполняется равенствоϕi (K, Sr (K, D)) = ϕi (K, Sr (K, D0 ))(12)Равенство окрестностей подразумевает не только совпадение окрестностейкак множеств, но и равенство пометок над соответствующими конъюнкциями.Локальный алгоритм индекса r преобразует сокращенную ДНФ без пометок (или, что то же, с пометками вида “ − ”) в ДНФ, состоящую из тех жеконъюнкций, но с пометками, несущими информацию о вхождении их в ДНФтого или иного типа.
При вычислении пометки над очередной конъюнкциейалгоритм использует информацию о ее окрестности порядка r с учетом ужевычисленных пометок над конъюнкциями из этой окрестности. Алгоритм работает следующим образом:1. Нумеруются некоторым образом конъюнкции K из Dfсок р . Все пометкинад конъюнкциями в начальный момент равны “ − ”.2. Выбирается первая по номеру конъюнкция K. Вычисляются одна илинесколько функций ϕi , i = 1, 2, 3, по паре (K, Sr (K, D)). В результате вычисления либо хотя бы одна пометка изменилась, либо нет. В первом случае11заново нумеруем конъюнкции и продолжаем процесс с учетом новых пометок.
Во втором случае переходим к следующей по номеру конъюнкции. Еслиномер конъюнкции оказался последним, и ни одна отметка не измениласьпосле очередной перенумерации, алгоритм заканчивает работу. Результатомявляется ДНФ Dfсок р с теми пометками над конъюнкциями, которые удалосьвычислить.В дальнейшем используются следующие известные в теории ДНФ понятия и факты. Множество всех наборов (α1 , . . . , αn ) таких, что αi ∈ {0, 1}, i =1, .
. . , n, назывется n-мерным единичным кубом и обозначается через B n . Положим Nf = {α̃ ∈ B n : f (α̃) = 1}. Гранью куба B n называется множество g,для которого существует конъюнкция K, зависящая (не обязательно существенно) от переменных x1 , . . . , xn , такая, что g = NK . Размерностью граниназывается число log2 |g|. Грань размерности 1 называется ребром. Грань называется интервалом функции f , если g ⊆ Nf , и максимальным интерваломфункции f , если g не содержится ни в каком другом ее интервале.
Говорят,что вершина α̃ ∈ B n покрывается конъюнкцией K, если α̃ ∈ NK . Конъюнкция K поглощается функцией f (поглощается ДНФ D), если NK ⊆ Nf(соответственно, если NK ⊆ ND ). Через D \ K обозначим ДНФ, полученнуюиз D отбрасыванием слагаемого K.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
