Материалы для подготовки к экзамену прошлых лет, страница 5
Описание файла
PDF-файл из архива "Материалы для подготовки к экзамену прошлых лет", который расположен в категории "". Всё это находится в предмете "дополнительные главы кибернетики и теории управляющих систем" из 7 семестр, которые можно найти в файловом архиве МГУ им. Ломоносова. Не смотря на прямую связь этого архива с МГУ им. Ломоносова, его также можно найти и в других разделах. .
Просмотр PDF-файла онлайн
Текст 5 страницы из PDF
Для любого множества ФАЛ Q, Q ⊆ P2 (n), и любого натуральногоr, r 6 n, справедливо неравенство −5 bK →L ( Q ) > 2 |Q| 1 − √− 2 Q(1.4),rb состоит из тех ФАЛ f, f ∈ Q, у которых во множестве N fгде множество Qесть грани размерности больше, чем (n − r).Доказательство. Пусть Σ - минимальная приведенная (1, |Q|)-КС, реализующая→−систему ФАЛ Q , и пусть V - множество её выходных вершин. Пусть, далее, s иt - натуральные параметры, для которых (s − 1)(t − 1) 6 r, а V 0 - множество техвыходных вершин Σ, степень которых не меньше, чем s.
Достаточно рассмотретьслучай, когда 0V 6 4 |Q| ,(1.5)sтак как иначе число контактов Σ инцидентных вершинам из V 0 уже было бы неменьше, чем 2 |Q|.Для произвольного набора α, α ∈ B n , множество c (α) связанных компонентсети Σ|α разобьем на непересекающиеся подмножества ci (α) , i ∈ [1, 4], так, чтосвязная компонента G, G ∈ c (α), входит в подмножество:1. c1 (α), если V (G) * V ;2. c2 (α), если G ∈/ c1 (α) и V (G) ∩ V 0 6= ∅;3. c3 (α), если G ∈/ (c1 (α) ∪ c2 (α)) и |V (G)| > t;4. c4 (α) в остальных случаях.Заметим, что произвольная связная компонента G из ci (α) удовлетворяет неравенству|E (G)| > |V ∩ V (G)| ,(1.6)если i = 1 и состоит только из выходных вершин Σ в остальных случаях. При этомв случае i = 2 она содержит хотя бы одну вершину из V 0 , в случае i = 3 - состоитне менее, чем из t вершин, а в случае i = 4 включает в себя не более (t − 1) вершин,которые отделяются от остальных вершин сети Σ|α сечением, состоящим не более,чем из (s − 1)(t − 1) 6 r, контактов множества E (Σ|α ).
Таким образом, в каждой§2. Незабиваемые множества переменных23b и,вершине компоненты G из множества c4 (α) реализуется ФАЛ из множества Q,учитывая все вышесказанное, получим |Q| b|c2 (α)| 6 V 0 , |c3 (α)| 6, |c4 (α)| 6 Q(1.7).tИз (1.5) – (1.7) в силу (1.2) вытекает неравенство4 |Q| |Q| b −− Q ,st√из которого в соответсвии с 1.1 при δ = B n и s = t = d re следует (1.4).Теорема доказана.nСледствие 1. Полагая Q = P2 (n) и учитываято,чтоприr=2 множество 2n b = Pb2 (n) удовлетворяет соотношению Pb2 (n) = o 2√Q, получимn|E (Σ|α )| > |Q| −→−12nL ( P 2 (n)) > 2 · 21−O √.nKСледствие 2. Оценки следствия 1 и леммы 3.1 из[2, глава 4] дают асимптотическое неравенство→−nLK ( P 2 (n)) ∼ 2 · 22 .§2Забивание переменных константами и незабиваемые множества переменных.Асимптотика сложности мультиплексора в некоторых классахсхемОпределим сначала операцию подстановки констант вместо переменных в функциии схемы.
Будем считать, что любая ЭК K ранга r от БП X(n) вида K = xσi11 . . . xσirrзадает подстановку констант xi1 = σ1 , . . . , xir = σr . Результат применения указанной подстановки к системе ФАЛ F, F ∈ P2m (n), и схеме Σ от БП X(n) будемобозначать через F |K и Σ|K соответственно. При этом система ФАЛ F |K определяется обычным образом, а преобразование схемы Σ в схему Σ|K в классе UC (UK )связано с заменой вершин xij , j = 1, . . . , r, константой σj и применением, до техпор, пока это возможно, тождеств подстановки констант из §§1–2 [2, глава 3] (соσответственно отождествлением концевых вершин контактов вида xijj и удалениемσконтактов вида xijj , j = 1, .
. . , r) с последующим переходом к эквивалентной приведенной схеме. Заметим, чтоK · f = K · f |Kдля любой ФАЛ f и что схема Σ|K реализует систему ФАЛ F |K , если схема Σреализует систему ФАЛ F . Заметим также, что для КС Σ от БП X(n) и набора24Глава 2. Синтез схем для индивидуальных функцийα = (α1 , . . . , αn ) схема Σ|xα1 ...xαnn в отличие от сети Σ|α (см.
§§1,5 из [2, глава 2])1состоит из (кратных) изолированных полюсов.Будем говорить, что подмножество 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 . Заметим также, что примером незабиваемого множества БП является множество всех существенных(информационных) БП линейной(соответственно мультиплексорной) ФАЛ.Теорема 2.1. Если ФАЛ f имеет незабиваемое множество, состоящее из n ееБП, тоLC (f ) > 2n − 2, LK (f ) > 2n − 1(2.1)Доказательство.
Первое из равенств (2.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 и реализуемую1ею ФАЛ 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,которые устанавливают справедливость рассматриваемого индуктивного переходаи доказывают первое из равенств (2.1).§2.
Незабиваемые множества переменных25Докажем теперь второе из равенств (2.1). Пусть, по-прежнему, Y ={y1 , . . . , yn } — незабиваемое множество БП ФАЛ f и пусть Σ — минимальнаяприведенная (1, 1)-КС, реализующая ФАЛ f со сложностью L(Σ) = LК (f ). Если каждая из БП yi , i ∈ [1, n] имеет в КС Σ не менее двух контактов, то второе неравенство (2.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).(2.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 0 ФАЛ00f 0 . Аналогичное противоречие в случае |c(Σ )| > 3 связано с тем, что при этом в Σ0найдется контакт БП y 0 , y 0 ∈ Y 0 , соединяющий между собой две различные компо00ненты Σ , одна из которых не содержит полюсов Σ, и, следовательно, множествоБП Y 0 \ {y 0 } вновь забивает БП y 0 при подстановке константы 0.00Учитывая установленные свойства схем Σ00 и Σ , а также соотношения (1.2) и(1.3) из [2, глава 2], получим:0000L(Σ ) + 2 > |V (Σ )| = |V (Σ0 )| = |V (Σ00 )| > m + 1.Следовательно, выполняется неравенство00L(Σ0 ) = L(Σ ) + m > 2m − 1,из которого, в силу (2.2) вытекает второе неравенство (2.1).
Теорема доказана.Следствие.LC(µn ) > 2n+1 − 2, LK (µn ) > 2n+1 − 1.Установим теперь верхние оценки сложности реализации мультиплексорной−→ФАЛ µn в классах схем UC , UФ , UК , U К .26Глава 2. Синтез схем для индивидуальных функцийТеорема 2.2.
Для n = 1, 2, . . . справедливы неравенства:LC (µn ) 6 LФ (µn ) 6 2n+1 + O(2n/2 )(2.3)√LK (µn ) 6 2n+1 + O(2n / n)(2.4)−→L K (µn ) 6 2n + O(2n/2 )(2.5)Доказательство. Построим в классе UC схемный мультиплексор Σn порядка n,сложность которого дает оценку (2.3) для LC (µn ), следующим образом:0001. разобьем n набор БП X(n) на группы x = (x1 , . .
. ,q xq ), x = (xq+1 , . . . , xn ), гдеq = 2 , а набор БП y = (y0 , . . . , y2n −1 ) — на 2 последовательных наборовqy (0) , . . . , y (2 −1) длины 2n−q каждый;2. возьмем дешифраторы Σ0 и Σ00 от БП x0 и x00 порядка q и n − q, построенныепо лемме 2.1 из [2, глава 4];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 , .