С.А. Ложкин - Элементы теории синтеза дискретных управляющих систем (1160764), страница 2
Текст из файла (страница 2)
. . , Kb }, каждый элементKi , i = 1, . . . , b, которого представляет собой тройку hϕi , Li , τi i, где ϕi — ФАЛ, существеннозависящая от БП x1 , . . . , xki , Li — положительное действительное число, а τi — булевскаяконстанта. Предполагается, что число Li характеризует сложность («вес») ФПЭ Ki , которыйсостоит из ориентированного в случае τi = 0 и неориентированного в случае τi = 1контакта Ki , проводящего на наборе α значений БП x1 , . . .
, xki тогда и только тогда, когдаϕi (α) = 1, причём указанная проводимость в случае τi = 0 имеет место только в направленииориентации Ki .Таким образом, с формальной точки зрения ФПЭ Ki представляет собой контакт (ребро)Ki с пометкой ϕi . При этом из содержательных соображений можно считать, что ФПЭ Kiсостоит из контакта Ki и функционального элемента Ei , реализующего ФАЛ ϕi , выходкоторого «управляет» проводимостью Ki .2Буквой c с различными индексами будем обозначать константы, зависящие только от базиса Б§2.7Следуя [3], определим (одновходовую) КС Σ = Σ(x1 , . .
. , xn ; z1 , . . . , zm ) над базисом Бкак частично ориентированный граф с единственным (проводящим) входом, помеченнымсимволом 1, и m (проводящими) выходами, помеченными выходными БП z1 , . . . , zm , каждоеориентированное (соответственно, неориентированное) ребро которого помечено одной избазисных ФАЛ ϕi , где τi = 0 (соответственно, τi = 1), зависящей от ki переменных измножества входных (управляющих) БП X(n) = {x1 , . . . , xn }. Для любой упорядоченнойпары (u, v) вершин данной КС стандартным образом вводится ФАЛ проводимости от u к v,зависящая от БП X(n).
Будем, как обычно, считать, что в каждой вершине рассматриваемойКС Σ реализуется ФАЛ проводимости от входа 1 к этой вершине, и что сама КС Σ реализуетсистему ФАЛ FΣ = (f1 , . . . , fm ), где fj — ФАЛ, реализуемая в вершине Σ с пометкой zj ,j = 1, . . . , m.Пусть UКБ — класс КС над базисом Б, входные и выходные БП которых берутся изсчётных упорядоченных непересекающихся алфавитов X = {x1 , x2 , . .
. , xn , . . .} и Z ={z1 , z2 , . . . , zm , . . .} соответственно. Предполагается, что базис Б является полным, то естьлюбая ФАЛ от БП из X может быть реализована схемой из UКБ . Заметим, что любой базис,содержащий «обычные» неориентированные замыкающий и размыкающий контакты, т. е.контакты с базисной ФАЛ xi и x̄i соответственно, является полным. Базис Б0 , состоящий иззамыкающего и размыкающего контактов веса 1, будем считать стандартным.Для удобства будем считать, что при построении схем над базисом Б разрешаетсяподставлять константы вместо БП его контактов.
В этом случае необходимым и достаточнымусловием полноты Б является наличие среди его базисных как ФАЛ, которая не являетсямонотонной, так и ФАЛ, которая не является антимонотонной.Под сложностью L(Σ) КС Σ, Σ ∈ UКБ , понимается, как обычно, сумма весов всех еёФПЭ, а под сложностью LКБ (F ) системы ФАЛ F = (f1 , . . . , fm ) от БП из X — минимальнаяиз сложностей схем класса UКБ , её реализующих. Для указанного функционала сложностиобычным образом вводится соответствующая функция ШеннонаLКБ (n) = max LКБ (f ),f ∈P2 (n)(2.1)где, как обычно, P2 (n) — множество всех ФАЛ от БП X(n), n = 1, 2, . . ..Определим далее класс UИКС— класс итеративно-контактных схем над базисом Б,Бкоторый обобщает класс UКБ аналогично тому как класс «обычных» ИКС [3] обобщает классобычных КС UКБ0 .Для этого рассмотрим счётный упорядоченный алфавит итеративных БП Y == {y1 , y2 , .
. . , yp , . . .}, где Y ∩ X = Y ∩ Z = ∅, и индукцией по t, t = 0, 1, . . ., введёмкласс UИКСБ,t — класс ИКС итеративного ранга t над базисом Б. Базис указанной индукцииКсоставляет класс UИКСБ,0 — класс ИКС итеративного ранга 0, который совпадает с классом UБ .Заметим, что класс UИКСявляется полным тогда и только тогда, когда полон класс UКБ .БИндуктивный переход, позволяющий от ИКС Σ = Σ(x1 , . .
. , xn ; z1 , . . . , zm ) из классаUИКСБ,t ,реализующей систему ФАЛ (f1 , . . . , fm ) от БП x = (x1 , . . . , xn ), переходить к реали-000зующей систему ФАЛ (f10 , . . . , fj−1, fj+1, . . . , fm) от БП x0 = (x1 , . . . , xi−1 , xi+1 , . . . , xn ) ИКС8Глава 1.Σ0 = Σ0 (x0 , z1 , . . . , zj−1 , zj+1 , . . . , zm ) из класса UИКСБ,t+1 , связан с применением операции присоединения выхода zj ИКС Σ к её входу xi . Эта операция применима, если ФАЛ fj не зависитсущественно от xi и состоит в замене пометки zj выходной вершины v ИКС Σ, а также всехпометок БП xi на контактах Σ пометками БП yt+1 .
При этом предполагается, что ФАЛ fs0 (x0 ),где s 6= j, получается из ФАЛ fs (x) подстановкой ФАЛ fj (x0 ) вместо БП xj .Будем считать, что для описанных выше схем ИКС Σ является базовой ИКС ранга t дляИКС Σ0 и что переходя от ИКС Σ к её базовой ИКС ранга (t − 1) и т. д. мы придём к базовойb Заметим, что сложности всех построенных ИКС одинаковы и равны L(Σ).bдля ИКС Σ0 КС Σ.Определим, наконец, класс UИКСкак объединение классов UИКСББ,i по всем i, i = 0, 1, .
. ..Для полного класса UИКСи произвольной системы ФАЛ F = (f1 , . . . , fm ) обычнымБобразом определяется сложность LИКС(F ) — сложность реализации системы F в классеБUИКС, а затем аналогично (2.1) вводится соответствующая функция Шеннона LИКС(n).ББWПусть, как обычно, UWБ (L, n), где W ∈ {К, ИКС}, — множество всех схем из UБ , реали-зующих одну ФАЛ из P2 (n). Следуя [3] для (конечного) множества схем G через |G| и ||G||будем обозначать число попарно не изоморфных и число попарно не эквивалентных схемв G соответственно.Для базиса Б = {K1 , . .
. , Kb } положимLi,16i6b ki + 1πБ = min Li ,ρ̂Б = min16i6bkБ = max ki .16i6bСправедливы следующие утверждения.Теорема 2.1.||UКБ {L, n}|| 6 c3 LnkБ πLБТеорема 2.2.||UИКС{L, n}|| 6 c4 (L + n)Б§3 ρ̂LБНижние мощностные оценки функций ШеннонаУстановим ряд нижних оценок для введённых в §1, §2 функций Шеннона. Все эти оценкиполучены с помощью мощностного метода, предложенного Шенноном [16, 6], которыйоснован на том, что число ФАЛ от БП x1 , .
. . , xn не может быть меньше числа тех попарноне эквивалентных схем, сложность которых не превосходит значения соответствующейфункции Шеннона от аргумента n.Пусть U — один из рассмотренных в §1, §2 классов схем, Ψ — введённый там функционалсложности, а Ψ(n) — функция Шеннона для класса U относительно Ψ.
Обозначим черезU(Ψ, n) множество тех схем Σ, Σ ∈ U, которые реализуют одну ФАЛ из P2 (n) и для которыхΨ(Σ) 6 Ψ. Следующее «мощностное» равенство вытекает непосредственно из определений:n||U Ψ(n), n || = 22 .(3.1)§3.9b δ, где 0 < δ < 1,Заметим также, что если для некоторого натурального n и действительных Ψ,выполняется неравенствоb n || 6 δ · 22n ,||U Ψ,то(3.2)b для не менее чем (1 − δ) · 22n ФАЛ f из P2 (n).то Ψ(f ) > ΨВерхние оценки величины ||U(Ψ, n)||, установленные в §1, §2 для различных классовсхем и функционалов сложности, а также соотношения (3.1)–(3.2) служат основой дляполучения нижних мощностных оценок соответствующих функций Шеннона и сложностипочти всех ФАЛ.
Напомним, что (см. [3, Гл. 2, теорема 3.1 и лемма 5.3]) для каждогонатурального n справедливы неравенства:|UC (L, n)| 6 32(L + n)L+1|UФ (L, n)| 6 32n,L|UК (L, n)| 6 8nL ,2T|UФ (T, n)| 6 64n .L+1,(3.3)(3.4)(3.5)(3.6)Лемма 3.1. Для γ ∈ {0, 1} и положительных действительных чисел a, α, y, q таких, что(ay γ )αy > q,в случае γ = 1 иaα(3.7)log q > 1 выполняется неравенствоlog qy>α log αa log qlog log αa log q1+logqlog aeα!,(3.8)где e — основание натуральных логарифмов, а в случае γ = 0 и a > 1 — неравенствоy>log q.α log a(3.9)Доказательство. В случае γ = 0 и a > 1 неравенство (3.9) получается в результате логарифмирования (3.7) и деления обеих частей полученного неравенства на α log a.Рассмотрим теперь случай, когда γ = α = a = 1 и log q > 1.
В этом случае неравенство (3.8) следует из того, что левая часть (3.7) монотонно возрастает по y, и дляy 0 = (1 + ε)log q,log log qгдеε=log log log q,log (e log q)справедливы соотношенияy 0 log y 0 = (1 + ε)log qlog log q − log log log q + log e ln(1 + ε) 6log log qlog log log qε log e6 log q(1 + ε) 1 −+=log log qlog log q= log q(1 + ε)(1 − ε) = log q 1 − ε2 6 log q.Заметим, что в случае γ = 1, α > 0, a > 0 неравенство (3.7) эквивалентно неравенствуa(ay)ay > q α ,10Глава 1.и поэтому неравенство (3.8) получается из неравенства y > y 0 в результате замены y на ay иlog q наaαlog q, если выполнено условиеaαlog q > 1.Лемма доказана.Теорема 3.1.
Для некоторой последовательности ε = ε(n), n = 1, 2, . . ., такой, что ε(n) >> 0 при n > n0 и ε(n) стремится к 0 при n стремящемся к бесконечности, выполняютсянеравенства2n1 + ε(n) ,n2nLФ (n) >1 − ε(n) ,log n2n1 − ε(n) ,LК (n) >nD(n) > n − log log n − ε(n).LC (n) >(3.10)(3.11)(3.12)(3.13)Доказательство.
Неравенства (3.10)–(3.12) выводятся из соответствующего рассматриваемому классу схем U с функционалом сложности L неравенства (3.3)–(3.5) на основеnмощностного равенства (3.1) с использованием леммы 3.1, где q = 22 , α = 1 иγ = 1, a = 32,y = LC (n) + n, если U = UC ;γ = 0, a = 32n, y = LФ (n) + 1, если U = UФ ;γ = 1, a = 8n,y = LК (n),если U = UК .Действительно, подставляя указанные значения в (3.8) и (3.9), получимlog(n + 5)2nlog n − 5 − o(1)2nC1+−n>1+,L (n) >n+5n+7nn2n2n5 + o(1)ФL (n) >−1>1−,log n + 5log nlog nlog(n + 3 + log n)2n3 + o(1)2nК1+>1−.L (n) >n + 3 + log nn + 5 + log nnn(3.14)(3.15)(3.16)Следовательно, неравенство (3.10) ((3.11), (3.12)) будет справедливо для достаточно больших n при ε(n) =log n−6n(соответственно ε(n) =6,log nε(n) = n4 ).Аналогичным образом на основе неравенства (3.6) и равенства (3.1) c использованиемnлеммы 3.1, где q = 22 , y = 2D(n) , γ = 0, α = 1 и a = 64n, устанавливается справедливость (3.13) при ε(n) =12.log nТеорема доказана.Следствие 1.LC (n) &2n,nLФ (n) &2n,log nLК (n) &2n,nT (n) > n − log log n − o(1).Следствие 2.
Нижние оценки (3.10)–(3.13) при указанных в доказательстве значениях ε(n)справедливы для сложности (глубины) почти всех ФАЛ f , f ∈ P2 (n), при их реализации всоответствующих классах схем.§4.11nДействительно, замена величины q = 22 величиной q =1 2n2nпри получении оце-нок (3.14)–(3.16) с помощью леммы 3.1 повлияет только на участвующие в их последнихb — правая часть соотнеравенствах функции вида o(1). При этом, в силу (3.2), где q = 1 , а Ψnветствующего неравенства (3.10)–(3.12), вновь полученная оценка будет справедлива дляпочти всех ФАЛ f , f ∈ P2 (n).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
