С.А. Ложкин - Элементы теории синтеза дискретных управляющих систем (1160764)
Текст из файла
Московский государственный университет имени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиС. А. ЛожкинЭЛЕМЕНТЫТЕОРИИ СИНТЕЗА ДИСКРЕТНЫХУПРАВЛЯЮЩИХ СИСТЕММосква — 2016Оглавление1 Асимптотически наилучшие методы синтеза схем в некоторых моделях дискретныхуправляющих систем§13Формулы и СФЭ в произвольном базисе, функционалы их сложности. Верхниеоценки числа формул и СФЭ . .
. . . . . . . . . . . . . . . . . . . . . . . . . .§23Некоторые модификации контактных схем, итеративные контактные схемы.Верхние оценки числа схем контактного типа . . . . . . . . . . . . . . . . . .6§3Нижние мощностные оценки функций Шеннона . . . . . . . . . . . . . . . .8§4Универсальные множества ФАЛ и их построение. Асимптотически наилучшийметод синтеза СФЭ и ИКС в произвольном базисе . .
. . . . . . . . . . . . .§511Асимптотически наилучший метод синтеза формул и контактных схем впроизвольном базисе . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .Литература15212Глава 1Асимптотически наилучшие методы синтеза схем внекоторых моделях дискретных управляющих систем§1Формулы и СФЭ в произвольном базисе, функционалы их сложности. Верхние оценки числа формул и СФЭПродолжим начатое в [3, Гл. 2, 4] изучение формул и схем из функциональных элементов(СФЭ) над произвольным конечным полным базисом Б = {Ei }bi=1 , где функциональныйэлемент (ФЭ) Ei реализует ФАЛ ϕi (x1 , . . . , xki ), которая в случае ki > 2 существенно зависитот всех своих переменных.Будем по-прежнему (ср.
[3, Гл. 2, §3]) представлять СФЭ Σ в виде Σ = Σ(x; z), еслиx = (xi1 , . . . , xin ) и z = (zj1 , . . . , zjn ) — наборы, составленные из всех её различных входныхи выходных булевых переменных (БП), перечисленных в порядке возрастания их номеров валфавитах X = {x1 , x2 , . . . , xn , .
. . } и Z = {z1 , z2 , . . . , zm , . . . }, соответственно. Сложность,то есть число ФЭ, глубину, то есть максимальное число последовательно соединённых ФЭ,и ранг, то есть число дуг, исходящих из входов, в схеме Σ, следуя [3], будем обозначать черезL(Σ), D(Σ) и R(Σ) соответственно.Введём теперь «взвешенные» функционалы сложности и глубины СФЭ. Будем считать,что каждому функциональному элементу Ei , i = 1, . . . , b, сопоставлены положительные действительные числа Li и Ti , называемые его «весом» и «задержкой», которые характеризуютсложность («размер») и время срабатывания Ei соответственно.
Предполагается, что «вес»и «задержка» любого ФЭ стандартного базиса Б0 = {&, ∨, ¬} равны 1. Если (v0 , vt )-цепь Cдлины t в СФЭ Σ проходит через вершины v1 , . . . , vt−1 , и вершине vj , j = 1, . . . , t, при этомсоответствует ФЭ Eij базиса Б, то число T (C) = Ti1 + · · · + Tit будем называть задержкойэтой цепи.По аналогии с глубиной определим задержку вершины v СФЭ Σ как максимальнуюзадержку тех цепей Σ, которые начинаются в одной из ее входных вершин и заканчиваютсяв вершине v.
Для каждой СФЭ Σ над базисом Б помимо сложности L(Σ), глубины D(Σ) иранга R(Σ) определим следующие параметры (функционалы сложности):1) L(Σ) — размер Σ, то есть сумма «весов» всех её ФЭ;2) T (Σ) — задержка Σ, то есть максимальная задержка её вершин.Заметим, что функционал L (D) является частным случаем функционала L (соответственно34Глава 1.T ), когда веса (соответственно задержки) всех ФЭ базиса Б равны 1. Введем также «частичный» размер LБ0 (Σ) (задержку TБ0 (Σ)), который равен сумме весов ФЭ Σ типа Ei , гдеEi ∈ Б0 , в СФЭ Σ (соответственно максимальной сумме задержек ФЭ указанного вида, лежащих на одной цепи Σ).
Аналогичным образом вводится «частичная» сложность LБ0 (Σ) и«частичная» глубина DБ0 (Σ) для СФЭ Σ.Напомним (см. [3]), что СФЭ называется приведённой, если выход любого её ФЭ, не являющийся выходом схемы, поступает на вход другого ФЭ этой схемы. Приведённая СФЭ(системы формул) считается строго приведённой, если в ней нет эквивалентных вершин,то есть вершин, в которых реализуются равные ФАЛ (соответственно нет эквивалентныхвершин, лежащих на одно цепи). Заметим, что для любой СФЭ (системы формул) Σ существует эквивалентная ей строго приведённая СФЭ (соответственно система формул) Σ0 , длякоторойLБ0 (Σ0 ) 6 LБ0 (Σ) и TБ0 (Σ0 ) 6 TБ0 (Σ)при любом Б0 ⊆ Б. Легко видеть также, что в строго приведённой формуле или СФЭ неттрёх или более последовательно соединённых одновходовых ФЭ.b = { Ei | ki > 2 } и заметим, что множество Бb неДля базиса Б = {Ei }bi=1 положим Бb определим его приведённый вес ρi ипусто в силу полноты базиса Б.
Для ФЭ Ei , Ei ∈ Б,приведённую задержку τi следующим образом:ρi =Li,ki − 1τi =Ti.log kiВведём, далее, величиныρБ = min ρiEi ∈bБи τБ = min τi ,Ei ∈bБкоторые назовём приведённым весом и приведённой задержкой базиса Б соответственно. Дляb0 = {&, ∨}, ρБ0 = τБ0 = 1. Для функционаластандартного базиса Б0 = {&, ∨, ¬}, очевидно, Бbсложности ψ типа L, L, D, T через ψ(Σ)будем обозначать величину ψb (Σ).БФСледуя [3] обозначим через UCБ , UУСБ и UБ множество СФЭ над базисом Б, множествоусилительных СФЭ над Б и множество формул над Б соответственно. При этом для каждогоAA, A ∈ {C, Ф}, определим размер LAБ (F ) ФАЛ или системы ФАЛ F в классе UБ и еёзадержку TБ (F ) обычным образом, а через LAБ (n) и TБ (n) обозначим соответствующиефункции Шеннона.Лемма 1.1.
Для любой формулы F, F ∈ UФБ , выполняются неравенстваR(F) 61bL(F) + 1,ρБR(F) 6 2b(F)TτБ.(1.1)Доказательство. Пусть для каждого i, i = 1, . . . , b, формула F содержит si ФЭ Ei . При этомдля числа ребер квазидерева F будут выполняться равенства|E(F)| =bXi=1si · ki = R(F) +bXi=1si − 1.§1.5Следовательно,R(F) =bXsi (ki − 1) + 1 =i=1X ki − 1· Li si + 1 6Liki >21 X1bLi si + 1 = L(F)+1ρБ k >2ρБiи первое неравенство (1.1) доказано.Второе неравенство (1.1) доказывается индукцией по D(F). Действительно, при D(F) == 0, когда F = xj , оно, очевидно, выполняется.
Пусть теперь второе неравенство (1.1) вернодля любой формулы глубины меньше, чем d, и пусть F = ϕi (F1 , . . . , Fki ), где D(F) = d иD(Fj ) < d, Tb(Fj ) = tj при всех j = 1, . . . , ki . ТогдаR(F) =kiXtR(Fj ) 6 ki · 2 τБ ,j=1где t = max16j6ki tj . Следовательно, при ki = 1 формула F удовлетворяет второму неравенству (1.1), так как в этом случае Tb(F) = t. При ki > 2 в соответствии с определением τБвыполняется неравенствоTiki 6 2 τБ ,используя которое и учитывая, что в данном случае Tb(F) = t + Ti , получимtR(F) 6 ki · 2 τБ 6 2t+TiτБ=2b(F)TτБ.Лемма доказана.Замечание.
Аналогично первому неравенству (1.1) доказывается, что число рёбер дерева,соответствующего формуле F, в которой нет трёх и более последовательно соединённыходновходовых ФЭ, удовлетворяет неравенству|E(F)| 6 6 R(F) − 1 .(1.2)Действительно, если F содержит si ФЭ Ei , i = 1, . . .
, b, тоR(F) =bXbsi (ki − 1) + 1 > L(F)+ 1,i=1b|E(F)| 6 3 R(F) + L(F)− 1 6 3 2R(F) − 2 = 6 R(F) − 1 .Неравенство (1.2) выполняется, в частности, для строго приведённой формулы F.Для приведённой одновыходной СФЭ Σ на базисом Б её остовом будем называть такуюформулу F(x1 ) над Б, дерево которой получается в результате применения к каждой вершинеΣ операций отсоединения всех исходящих дуг, кроме одной, и объявления начальных вершинэтих дуг листьями указанного дерева.Ф1Пусть для UCБ hL, ni (UФБ hL, ni, UБ {T, n}) — множество всех строго приведённых схем изфункциональных элементов вида Σ(x1 , . . . , xn ; z1 ) из UCБ (соответственно формул F(x1 , .
. . , xn )из UФБ ), для которых L(Σ) 6 L (соответственно L(F) 6 L, T (F) 6 T ).1Напомним [3], что СФЭ является приведённой, если в ней нет «висячих» вершин и строго приведённой,если в ней, кроме того, нет вершин, в которых реализуются равные ФАЛ.6Глава 1.Лемма 1.2. Для любых L > 0, T > 0 и любого натурального n справедливы неравенства2 : C1UБ hL, ni 6 (c1 (L + n)) ρБ L+1 , Ф1UБ hL, ni 6 (c2 n) ρБ L+1 ,T ФUБ {T, n} 6 (c2 n)2 τБ .(1.3)(1.4)(1.5)Доказательство. Пусть Σ ∈ UC hL, ni, a F̌ — остов Σ. В силу леммы 1.1 и замечания к нейчисло рёбер в дереве формулы F̌ не больше, чем bc1 L, где bc1 =не изоморфных формул не превосходитL/ρc2 Б ,6,ρБа число таких попарногде c2 6 46 .
Любая формула F (СФЭ Σ) изUC hL, ni может быть получена в результате присоединения каждого из R(F̌) 61L(F̌)ρБ+1(в силу леммы 1.1) листьев дерева формулы F̌, являющейся её остовом, к входам x1 , . . . , xn(соответственно к входам x1 , . . . , xn и внутренним вершинам F̌), которое можно осуществитьне более, чем nR(F̌) (соответственно (bc1 · L + n)R(F̌) ) способами.
Перемножая полученныеоценки и учитывая (1.1) приходим к (1.3) с константой c1 = c2 max{bc1 , 1} и (1.4).В случае Σ = F ∈ UФБ {T, n}, рассуждая аналогично, приходим к (1.5) с учётом того,что число рёбер в формуле F̌ не больше, чем 6 · 2T /τБ , число таких формул не превосходитT /τБ(c2 )2, а их ранг ограничен сверху в силу (1.1) числом 2T /τБ .Лемма доказана.§2Некоторые модификации контактных схем, итеративные контактные схемы. Верхние оценки числа схем контактного типаРассмотрим теперь классы контактных схем (КС) и итеративно-контактных схем (ИКС)над заданным базисом функционально-проводящих элементов (ФПЭ) или, для краткости,контактов, частными случаями которых являются известные классы схем «проводящего»типа — классы «обычных» КС и ИКС (см., например, [3]).Рассматриваемые схемы строятся из ФПЭ базиса Б = {K1 , .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
