Материалы для подготовки к экзамену (2012-2013 учебный год), страница 13
Описание файла
PDF-файл из архива "Материалы для подготовки к экзамену (2012-2013 учебный год)", который расположен в категории "". Всё это находится в предмете "дополнительные главы кибернетики и теории управляющих систем" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 13 страницы из PDF
. . .При n = 2 неравенство (2.4) выполняется в силу (2.2), что составляет базис рассматриваемой индукции. Для обоснования индуктивного перехода возьмем произвольную минимальную линейную СФЭ Σ порядка n, n > 3, от БП X(n) и покажем,что для некоторых i, i ∈ [1, n], и σ, σ ∈ B, выполняется неравенствоL(Σ) > L(Σ|xσi ) + 4.(2.5)Будем считать, что на каждом шаге преобразования СФЭ Σ в СФЭ Σ00i,σ = Σ|xσiудаляется один ФЭ E с константой на входе. При этом вершина, с которой связан ФЭ E, обьявляется константной входной вершиной типа σ новой схемы, еслина выходе E реализуется константа σ, σ ∈ B, и удаляется вместе с E в остальныхслучаях. Заметим, что для любой промежуточной схемы Σ0 указанного преобразования выполняется неравенствоL(Σ00i,σ ) 6 L(Σ0 ) − IC(Σ0 ),(2.6)где IC(Σ0 ) — число дуг Σ0 , исходящих из её константных входов.
Будем предполагать также, что в любой вершине СФЭ Σ00i,σ реализуется неконстантная ФАЛ.64Глава 2.Полустепень исхода, то есть число исходящих дуг вершины v СФЭ Σ будемобозначать через d+ (v), а число исходящих из v дуг, которые ведут в вершины,связанные с ФЭ типа Φ, Φ ⊆ Б0 , — через d+Φ (v). Заметим, что для любой вершины vСФЭ Σ и для любого любого i, i ∈ [1, n], выполняются неравенстваd+¬ (v) 6 1,++d+ (xi ) = d+& (xi ) + d∨ (xi ) + d¬ (xi ) > 2,(2.7)первое из которых вытекает непосредственно из минимальности Σ, а второе — изследствия 1 леммы 2.1. Нетрудно убедиться в том, что неравенство (2.5) выполняется в следующих случаях:1. d+ (xi ) > 4 — при любом σ;++2.
d+& (xi ) > 2 или d& (xi ) = d¬ (xi ) = 1 — при σ = 0;++3. d+∨ (xi ) > 2 или d∨ (xi ) = d¬ (xi ) = 1 — при σ = 1.Действительно, в каждом из этих случаев СФЭ Σ0 , которая получается при переходе от СФЭ Σ к СФЭ Σ00i,σ в результате удаления d+ (xi ) ФЭ, связанных с входом xi ,имеет при d+ (xi ) < 4 не меньше, чем (4 − d+ (xi )), константных входных дуг и,следовательно, в силу (2.6) выполняется (2.5).Таким образом, с учётом (2.7) осталось рассмотреть основной случай — случай,++когда d+& (xi ) = d∨ (xi ) = 1 и d¬ (xi ) = 0 для каждого i, i ∈ [1, n]. В этом случае вСФЭ Σ найдутся два входа, связанные с одним и тем же ФЭ типа & или ∨. Пустьдля определённости, данными входами Σ будут БП x1 и x2 , котороые поступаютна входы одного и того же ФЭ &, связанного с вершиной v.
Пусть при этом втораядуга, исходящая из вершины xi , i = 1, 2, идёт в вершину wi , связанную с ФЭ ∨,на другой вход которого поступает дуга из вершины ui . Заметим, что в силу минимальности Σ для любого i, i = 1, 2, вершина ui отлична от вершины v, так какпри v = ui в вершине wi реализуется ФАЛ xi .Покажем, что в случае w1 6= w2 неравенство (2.5) выполняется. Действительно,рассмотрим в этом случае СФЭ Σ0 , которая пролучается при переходе от СФЭ Σк СФЭ Σ001,0 в результате удаления двух ФЭ, связанных с вершинами w1 и v, а также одного ФЭ, связанного с какой-либо вершиной v 0 , в котороую идет дуга из v.Так как u2 6= v и, следовательно, v 0 6= w2 , то вход x2 схемы Σ0 поступает толькона вход ФЭ ∨, связанного с вершиной w2 .
Из леммы 2.1 вытекает, что при этомв вершине u2 СФЭ Σ0 реализуется ФАЛ 0, то есть при переходе от Σ0 к Σ001,0 ещёодин ФЭ — ФЭ ∨, связанный с вершиной w2 , — будет удалён. Неравенство (2.5) вслучае w1 6= w2 доказано.Пусть, наконец, w1 = w2 и, следовательно, x1 = u2 , x2 = u1 и пусть, для опреде+лённости, либо d+ (v) > 2, либо d+ (v) = d+ (w) = 1 и d+&,∨ (v) > d∨,¬ (w).
РассмотримСФЭ Σ0 , которая получается при переходе от СФЭ Σ к СФЭ Σ001,0 в результатеудаления двух ФЭ, связанных с вершинами v и w, а также всех тех ФЭ, входыкоорых присоединены к v (число таких ФЭ равно d+ (v)). Заметим, что в случае§3. Незабиваемые множества переменных65d+ (v) > 2 неравенство (2.5) вытекает из неравенства L(Σ) − L(Σ0 ) > 4, а в слу0чае d+ (v) = d+&,∨ (v) = 1 — из неравенства L(Σ) = L(Σ ) + 3 и неравенства (2.6),++где IC(Σ) > 1. В оставшемся случае d+ (v) = d+∨ (v) = d (w) = d& (w) = 1 из вер0шины v (w) исходит единственная дуга, ведущая в вершину v (соответственно w0 ),связанную с ФЭ ∨ (соответственно &).
В этом случае СФЭ Σ0 имеет в вершине w2вход x2 степени 1, поступающий на вход ФЭ &, и, следовательно, в силу леммы 2.1удовлетворяет неравенству L(Σ0 ) − L(Σ001,0 ) > 1, из которого, с учётом равенстваL(Σ) − L(Σ0 ) = 3, вытекает (2.5).Теорема доказана.§3Незабиваемые множества переменных. Асимптотика сложности мультиплексора в некоторых классах схемБудем говорить, что подмножество U множества X, состоящего из всех БП ФАЛ f ,забивает БП x, x ∈ X \ U , этой ФАЛ, если существует ЭК K от БП U такая, чтоФАЛ f |K не зависит существенно от x. При этом будем считать, по определению,что пустое множество U = ∅ забивает любую несущественную БП ФАЛ f и незабивает её существенные БП. Непустое подмножество Y множества БП ФАЛ fназывается незабиваемым множеством переменных этой ФАЛ, если для любойБП y, y ∈ Y , множество Y \ {y} не забивает y.
Заметим, что если Y — незабиваемоемножество БП ФАЛ f , то:1. любая БП из Y является существенной БП ФАЛ f ;2. для любой ЭК K от БП Y множество её несущественных БП является незабиваемым множеством БП ФАЛ f |K . Заметим также, что примером незабиваемого множества БП является множество всех существенных (информационных) БП линейной (соответственно мультиплексорной) ФАЛ.Теорема 3.1.
Если ФАЛ f имеет незабиваемое множество, состоящее из n еёБП, тоLC (f ) > 2n − 2,LК (f ) > 2n − 1(3.1)Доказательство. Первое из равенств (3.1) докажем индукцией по n, n = 1, 2, . . . .При n = 1 это неравенство, очевидно, выполняется. Пусть оно верно для любойФАЛ f 0 , которая имеет незабиваемое множество, состоящее из n0 , n0 6 (n − 1), еёБП, и пусть Y = {y1 , . . . , yn } — незабиваемое множество БП ФАЛ f , где n > 2.Возьмём миниимальную приведённую СФЭ Σ в базисе Б0 , которая реализуетФАЛ f со сложностью LC (f ).
В силу существенной зависимости ФАЛ f от БП y1в СФЭ имеется цепь из последовательно соединённых вершин v1 , . . . , vt , где v1 —вход y1 СФЭ Σ, а vt — выход Σ. При этом в вершине v1 реализуется ФАЛ y1 и, таккак f 6= y1 , то, следовательно, t > 2. Для σ1 ∈ B и σ1 = 0 тогда и только тогда,когда вершина v2 связана с ФЭ &, рассмотрим СФЭ Σ0 = Σ|yσ1 и реализуемую166Глава 2.ею ФАЛ f 0 = f |yσ1 , которая имеет незабиваемое множество БП Y 0 = Y \ {y1 } и1поэтому отлична от констант.Заметим, что в вершинах v1 и v2 СФЭ Σ при y1 = σ1 реализуются константы σ1и σ2 соответственно, а так как f 0 6= σ2 , то значит t > 3.
При этом константа σ2из вершины v2 поступает на вход ФЭ вершины v3 и, следовательно, при переходеот СФЭ Σ к СФЭ Σ0 элементы, связанные с вершинами v2 и v3 будут устранены(«забиты»). Таким образом, выполняются неравенстваLC (f ) = L(Σ) > L(Σ0 ) + 2 > LC (f 0 ) + 2,которые устанавливают справедливость рассматриваемого индуктивного переходаи доказывают первое из равенств (3.1).Докажем теперь второе из равенств (3.1). Пусть, по-прежнему, Y ={y1 , . .
. , yn } — незабиваемое множество БП ФАЛ f и пусть Σ — минимальнаяприведённая (1, 1)–КС, реализующая ФАЛ f со сложностью L(Σ) = LК (f ). Если каждая из БП yi , i ∈ [1, n], имеет в КС Σ не менее двух контактов, то второенеравенство (3.1), очевидно, выполняется. Таким образом, достаточно рассмотретьслучай, когда множество Y 0 , состоящее из тех БП yi , i ∈ [1, n], которым в Σ соответствует ровно один контакт, не пусто. Пусть, для определённости, Y 0 = {y1 , . . . , ym },1 6 m 6 n, и пусть каждая из БП yi , i ∈ [1, m], имеет в Σ только один замыкающийконтакт (это предположение не ограничивает, очевидно, общности рассуждений).Рассмотрим КС Σ0 = Σ|ym+1 ·...·yn , которая реализует ФАЛ f 0 = f |ym+1 ·...·yn снезабиваемым множеством БП Y 0 и для которой в силу выбора Y 0 выполняетсянеравенствоL(Σ0 ) 6 L(Σ) − 2(n − m).(3.2)Схема Σ0 по построению является связным графом и для каждого i, i ∈ [1, m],содержит ровно один (замыкающий) контакт БП yi .
Пусть, далее, КС Σ00 являетсяостовной подсхемой КС Σ0 , содержащей все контакты БП Y 0 и только их, а остовная0000подсхема Σ схемы Σ0 служит дополнением Σ00 , то есть Σ = Σ0 \ Σ00 .Покажем, что в КС Σ00 нет циклов, то есть Σ00 представляет собой систему де00ревьев, и что |c(Σ )| 6 2. Действительно, если бы в КС Σ00 контакт БП y 0 , y 0 ∈ Y 0 ,принадлежал циклу, то множество БП Y 0 \ {y 0 } при подстановке константы 1 забивало бы БП y 0 в КС Σ0 , что противоречит незабиваемости множества БП Y 000ФАЛ f 0 . Аналогичное противоречие в случае |c(Σ )| > 3 связано с тем, что приэтом в Σ0 найдётся контакт БП y 0 , y 0 ∈ Y 0 , соединяющий между собой две различ00ные компоненты Σ , одна из которых не содержит полюсов Σ, и, следовательно,множество БП Y 0 \ {y 0 } вновь забивает БП y 0 при подстановке константы 0.00Учитывая установлённые свойства схем Σ00 и Σ , а также соотношения (1.2)и (1.3) из [3, глава 2], получим:0000L(Σ ) + 2 > |V (Σ )| = |V (Σ0 )| = |V (Σ00 )| > m + 1.§3.
Незабиваемые множества переменных67Следовательно, выполняется неравенство00L(Σ0 ) = L(Σ ) + m > 2m − 1,из которого, в силу (3.2) вытекает второе неравенство (3.1).Теорема доказана.Следствие.LC(µn ) > 2n+1 − 2,LК (µn ) > 2n+1 − 1.Установим теперь верхние оценки сложности реализации мультиплексорной−→ФАЛ µn в классах схем UC , UФ , UК , U К .Теорема 3.2. Для n = 1, 2, . . . справедливы неравенства:nLC (µn ) 6 LФ (µn ) 6 2n+1 + O 2 2 ,√ LК (µn ) 6 2n+1 + O 2n / n ,−→nL К (µn ) 6 2n + O 2 2 .(3.3)(3.4)(3.5)Доказательство.
Построим в классе UC схемный мультиплексор Σn порядка n,сложность которого даёт оценку (3.3) для LC (µn ), следующим образом:1. разобьём набор БП X(n) на группы x0 = (x1 , . . . , xq ), x00 = (xq+1 , . . . , xn ),где q = dn/2e, а набор БП y = (y0 , .
. . , y2n −1 ) — на 2q последовательныхqнаборов y (0) , . . . , y (2 −1) длины 2n−q каждый;2. возьмём дешифраторы Σ0 и Σ00 от БП x0 и x00 порядка q и n − q, построенныепо лемме ? главы ?;b 00 , которая содержит дешифратор Σ00 в качестве подсхе3. построим схему Σмы и для каждого σ 00 , σ 00 ∈ B n−q , на выходе zj , где j = ν(σ 00 ), реализуетФАЛ µn−q (x00 , z (j) ) по её сокращённой ДНФ, используя для этого 2n−q ФЭ &и (2n−q − 1) ФЭ ∨;b 00 в качестве подсхем и реализует4. искомая схема Σn содержит СФЭ Σ0 и Σ0000ФАЛ µn (x , x , y) = µq (x , z0 , . . .