В.Б. Алексеев, С.А. Ложкин - Элементы теории графов, схем и автоматов (DJVU) (1055625), страница 9
Текст из файла (страница 9)
Теорема 7.1. Для любой ФЛЛ Хнах!,.... х„) можно Г(осп!р(и!ть СФЗ Еу, ((;оторал реалпзуеп! Х н для кон!ор(!а Х%)б — „+ О Док((заг!!Вльсгг!((о. Разобьем набор БП х = (х!....,х,„) на поднаборы х' = ~т1,..., х/,.) и х" = 1х!+1„...,ха), где й', 1Ь! — Некоторый параметр. Для лк!бого набора о. =1о!,...,(Г!.) из В положим: 1 1 ~.г ) = Х((7,.:1: ). ТО1гда для ФАЛ ! будет справедливо представление: 41 Построим СФЭ ЕХ из универсального многополюсника Еи порядка ())в А:) от БП х" и мульгиплексора Е' порядка А".
с адресными БП г', на информа)ц10нные Входы котО1)ОГО пода1отся ВыхОды ~ В соотВетствии с (7.1) ~см. рис. 7.1). Если мультиплексор х Р построить по лемме 5.2, а универсальный МНОГОПОЛ1ОСНИК ~ ПО ТЕО1)ЕМЕ 'Э.ч„'1О Следовжге.'1Ь1И), пол)И'ая 11 =)11 — 1ак(,11 — 2 1ОК п) 1, ПОЛУЧИМ 2'й 2" 2" Р'2" 1ос п'1 Ц~Х)6 + 0(11 2'Р~) + — = 6 — + 0 ~ и — 21ояп Теорема доказана. 'ЕРиь, 7.1 Следствие. Х,1)1)6 ° — ',' + О( — „'4 — ").
Рассмотрим теперь Вопрос о нижних оценках функции Шеннона Х.(11) и сложности некоторых конкретных ФАЛ. Пусть ~~~Х~„Г1) числО Всех тех Г!опа1)НО неиа1)мо1)фн1ъ)х неп1)и" водимых СФЭ с входными БП х), ...,х„и выходной БП ='1, сложность ко Горых не больше, чем Х,. Лемма 7.1. ХХ1)и,Р)н)бьс): ниткуральньи: Х., п. С))рииедлиио не1)пиен; Ю71ЙО ",;~Х.„)1)1Х, + и) Докави)пельстно.
Пусть Š— неприводимаи СФЭ с входными БП х1....,.1:,„и Выходной БП,-1„для которой Х ~К)Х,. Для задания СФ3 К доста'Гоч нО: 1) Выбрать целые неотрицательные числа Х,),Хь, Х) так„чтобы Х,1+Х2+А~Մ— нто можно сделагь не более, чем ~Х+ 1) спосооами: 2) взять Х1 ФЭ Й, Е~ ФЭ Ч и Хв ФЭ вЂ”, а затем каждый вход каждого из них "присоединить" к выходу некоторого другого ФЭ или к одному из входов Е это можно сделать не более, чем (Е+ и) способами; 3) поместить единственный сток СФЭ Е к выходной БП =:1.
Следовательно, ~(Е,п)(Е+ 1)4 (Е+ и)~~(Е+ п)~~+4. Лемма доказана. Лемма 7.2. ХХри любых патпуралъньт Х, и справедливо неравен; стпвсс у(Е, п)(32(Е+ п))~~~. Доказатпелъстпво. Пусть Е неприводимая СФЭ с входными БП х~....,х„и выходной БП -1, для которой Е(Е) = Е'Е. Сопоставим СФЭ Е ориентированное корневое упорядоченое помеченное дерево Х>, получающееся из графа Х в результате 'снятия' нходных БП с истоков Е, 'отсоединения ' от каждой вершины в графа 1'., такой, т го д+(в) > 1, каких-либо ~И+(о) — 1) исходящих из нее дуг и обьявления начальных вершин этих дуг новыми нершинами-листьями Л (см.
рис. 7.2). Замегим, что пометки внутренних нершин дерева Ртипами ФЭ базиса Бо сохраняются, и что в каждую такую вершину Р с пометкой ФС . входит одна дуга, а с пометкой Й или ~/ две дуги. Заметим также, что для получения СФЭ Е из дерева Р достаточно ка кдый лист 'П присоединить либо к одной из входных нершин СФЭ Е, помеченных БП х1, х~,..., х„, либо к одной из внутренних вершин самого дерева Р. Из построения дерева Х~ следует, что число внутренних вершин ~т.
е. вершин, отличных от листьев) в нем равно Е', а число ребер не больше, чем 2Е', и поэтому число листьев в Ю' не больше, чем Е'+ 1 (см. ~2). Следовагельно, число различных СФЭ Е, связанных с одним 1 и тем же деревом 'Р, не болыпе., чем (Е'+ и) х+, а из Ц2 вытекает, что число различных деревьев Р рассмазриваемого вида не больше, чем 421' 2с' 2 аг' Следовательно, у~Е,п) 2 32с (Е'+ тт)с ~~(32(Е+ тт))ь~~. Лемма доказана. Доказательство двух следующих утверждений основано на т.н. 'мощностном' принципе получения нижних оценок функции Шенно- Теорема 7.2. Для любого натпурилъного и справедливо неривенстпво 2п — ! Х (и) (1 — о(1) ). и Дот'изатттелъство. Из определения функции Шеннона Х(т!) и величины 7(Х,т!) следует, что ;:(Х (и), п)2 Логарифмируя зто неравенство и применяя лемму 7.1, получим: (2Х (т!) + 4) 1ор;(Х (и) + и) 2 „ откуда в силу теоремы 7.1 вытекает, что (2Х,(тт) + 4) .
(и + о(1) ) 2". Следовательно, Лемма доказана. Теорема 7.3. Для любого натпурального и справедливо неравенстпво: 2" 1оц и — 6 — о(1) Х,(и) — 1+ и и Х(Х)Х(и) = Х (и) — и, (7.2) где (7.3) Доказательство. Рассмотрим множество Рг(т!)., состоящее из тех ФАЛ ~'., Х Е Р2(тт), для которых Из 17.2)„опредег!ения величины 7! Х, 1!.) и леммы 7.1 следует„что ~Е )1-Ф ). и '~ ))""' 17-4) Логари4)мируя 17.-1) и используя 17.3), получим: 1ОВ ~Р~~)!)~Х,'~и)~ээ.
— 1о и+5+ о~1)) «)В 1о(» )1 — 6'( 1о~» 1). — 5 — о~1) В ( ьз и 7~ 1— С:!Г«»«1(эва! ельно, 2" — 1ор;~Р)~(э)~ — ) эо и „-+ О !Ф м при и. — Ф ж, а значит, множество Р~((!) ~Р~(11,) не пусто при дос:гаго»!Но больших )1, и поэтому найдется такая ФАЛ Х„Х ~ Р~~(!), для которой 17.5) 1еорема доказана.
Следствие. Неу)(1()енсы!Во ~7.5) ((ьи!олняегг!с(я дан аочпти всех ФАЛ ~ а.э Р~~э!). 1)ассм(э ! ри«к! Теперь н(.ко горые х!е»!О»!1»1 получения нижних оценок сложности конкретных ФАЛ. Соображении, связанные с тем„что сложность СФЭ Е, которая реализует си(тему из 1»э, разл!!чных ФА»:1. Отличных О1' БП„е1е может бьг! ь м((ныне. чем )п, мы уж(э испОльзОВН )1и в .!ео1)еж!ах 5.1„5.3.
В с.:!учае ден!ИФраэора„а так ке в некоторых НО- добных с:!у!(эях эгу г1)ивиа«!ьнуи) оиенкъ Можно и~сколько у!О»!1!и гь. Лемма 7.3. Слоэ(снос)г!ь схсмноео дешнфраюор(! гэо))ядка н» н 2, ие м((иы(ас, чвм 2В + ~~2 ° 2'«~2 — ьч — 1. ДО)э()гз(()В(:льсгг!Во. Пус'Гь ( ГроГО приВеденный схемн1»1й де,- шифрагор порядка н» а 2. с входными БП х1,... »х„. Из строгой приведенности Е следует, что каждый его Выходной ФЭ являе гся либо ФЭ А:, лино ФЭ -). Дей(гэв!г!ельно.
если бы на выходе ФЭ 'э»' СФЭ К р(эа»!Ггзов((."!а('ь КОн'1*к)нкция Хэ. = х! ' ... ' х "„1О хОтя бы на ОчнОм из («Го Вход~в !акже 1)еаэпеэова.эа(ь бы кон ьи)нк(г!!я ь, и в СФЭ к оказалось бы две различных эквивалентных вершины 1(м. ~4). По этой же причине, на Входы всех двухвходовых ФЭ СФЭ э пода)()!тя различные ФАЛ. Заметим также, что выход ФЭ о»» который одновре- меннО яв«!»1((тся ВыхОдОм «. не мОжет НО( т)«п((! ь н«»а ВхОд друГОГО ФЭ Е") выход которого также является выходом Еу т.к. при чтом ФЭ 8' и Г'" должны быль Фэ в.
Нли -, Г!а выходах ко!Орых 1)еа)!Нзу)от»я Разн ьн кОн ьк)нкдии из Я~у) ~ чтО нево )можно. ПУсть 0 числО веРН!ин СФЭ «л отличных»и ее выходов. Из Указанных особенн»кггей СФЭ « следует. что „а~»1 — 1) а1»1 + 1) + а И ПОВ'ГОМ«' е)л, 2»)/2 1 Таким образом, ЦЕ)2'+ и — »а2' + «/2 2" — и — 1. ,: 1емма доказана. Следствие. Х) силу сле»)с)Г)е)ил,") вв Гпее)ремы,").1 2" +Л 2"~' — — 1Х.~О„)2" +-,Л 2 ~'+О(.
2 ~'). ЛЕММа 7.4. ЕЕ:.Т»1 СЕ»"Э К р»1»)ЛиауЕГ)1 Суч»)СПтвлНН»)Ю ФАЛ ~~Х!»...,Х))). Гиа Х~«') и — 1л а ЕСЛИ. КРОМЕ тагО, ФАД ~ НЕМОНОГаОННа, то Х~Е) п,. До))аве)тел»лсгг)е)о. Перейдем от СФЭ Е, содержа!цей Х ФЭ Й и «/. к дел1)е)ву Ху зйк как л)'1О бы.*'!О сдел»1нО п~)и дОказГГГельсГв»! те;О1)емы 7.1. Заметим, что число БП ~ не больш»",, чем чи»:ло лис гаев дерева Ху. которое, в»1вок) очередь, не больше.
чем Х" + 1. Следовательно. Х.(К) Х."п — 1. Если же в СФЭ Х есть хотя бы один ФЭ -) ~в том случае, когда ФАЛ немОно говна„ФЭ -) в СФ ); ~ Обязаг»)льно наййеггся) '1О Лемма „т!Оказана. Применяя лемму Т.З к ФАЛ Х = х! «l... «~У„) получим, что Х»Х)11. ( другой стороны, ФАЛ )' можно р»увлизов»вгь формулой:Г! °... ° х,„„ лл: холу Ц)! л. Слпллллгллллл, ф рмулл У~" .".. л;; мвльной !'в классе СФЭ).
и Х® = и. Будем говорить, что подмножество Г множества БП ФАЛ ~ з»)й)»зае))1 БП Г. ув ф Г, ФАЛ ~, если подстановки некоторых констан г вместо БП Г из ФАЛ ~ можно получить ФАЛ» не завис)1НГук) су!цественно от Г. МГ!Оже»)тво переменных Л ФАЛ ~ будем называть незаое»1»)аемь)м, если лк)ба)! Неременна)1 т из Х не забивается множеством Л ~ 1х1. ЛеГКО видеть. чтО е(ре! л(обой ПОдстанОвке кОнстан'Г Вме( 1О не" которых переменных незабиваемого множе("Гва Х ФАЛ Х оставшиеся переменные из Х образуют незабиваемое множество переменных для Ф Т Л нолус(аюи(ей(я в резул1 1»а(е э п»Й иод( Гановкн О~(евидн(» также что в(е переменные незабиваемо(о множества Л ФАЛ Х явля(ОГ((я суще«1венными ие1»сменными Х, если !Х! 2.
ТЕОрЕМа 7.4. ЕС»111 у ФАЛ ~ сеть Е(ЕЗа(»(1(З(1ЕМ(»Е ВОдМНОжв«тва иа И ЬЗЕРЕМЕИНЪИ;, Е»1(» Х®4 — 1)- Д(»ка,затек(ъсп1(»(». При ьз = 1 оценка теоремы, очевидно, верна. Предположив, что эта оценка верна для любой ФАЛ Х и любого а 11' — 1), 1«де 1 2, докажем ее справедливость для произвольной ФАЛ Ь, КОГО1»ая вмажет не:»вбиваемое иодме1(»хкество„составленное из (,утцественных переменных х1,..., х1 ФАЛ Ь. Пусть Х вЂ” минимальная СФЭ, реализующая ФАЛ Ь со сложностьк» ЦЬ). Рассмо(рим вершину г СФЭ в кото1»ун» ведет ду(а из входной 1и»1инины х1, и кото1»ой П1»ииисана ФАЛ д баЗИСа БО. Пу«тЬ О = О, ЕСЛИ Ез = Н1 112, И (т = 1 В ОСтаЛЬНЫХ слъ"!аях.
Ве1нпина и не МОжеГ бьГГЬ ВыхОдОм ..~, '1»ак как иначе п1»и х1 — — О на выходе Е появлялась бы константа и пе1и менная х1 забивала бы, тем самым, переменные х»...., х( ФАЛ 1». С".1('д(»на1(',.:1ьно, найдется Ве1ипина 'и/ СФЭ ~, в КО ГО1»ъ'ю ведет г1уга из вершины о Пъ"( ть СФЭ, ио.(у Еаю(цая(я из СФЗ в 1»(зультвте подстановки константы' О вместо переменной х1. Схема Е р(..ализует некоторую ФАЛ Х с незабиваемым множ(*.«твом из ие1»емее(ИЕ,ЕХ х»,....х1 и не сод(,1»я(егт ве1»ни(н н„ш, то е(.:Гь им(1("Г «ложен»сть не более, чем .1;(.~) — 2. В «ил» индуктивного предположения Ц~') 211 — 2), и поэтому Х4Ь) = 14,-) И,-') + 2У 7 ) + 22(1 — 1). Теорема доказана. Следствие.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
