Материалы для подготовки к экзамену (2012-2013 учебный год)

Московский государственный университет имениМ. В. ЛомоносоваФакультет вычислительной математики и кибернетикиС. А. ЛожкинДополнительные главыкибернетикиМосква 2013Оглавление1 Асимптотически оптимальные методы синтеза схем и оценки высокойстепени точности для ряда функций Шеннона. Синтез схем дляфункций из специальных классов4§1 Некоторые модификации контактных схем. Итеративные контактныесхемы. Верхние оценки числа схем контактного типа, нижние мощностныеоценки функций Шеннона . . . .

. . . . . . . . . . . . . . . . . . . . .4§2 Формулы и СФЭ в произвольном базисе, усилительные СФЭ. Верхниеоценки числа формул и СФЭ, нижние мощностные оценки функцийШеннона . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12§3 Универсальные системы ФАЛ и их построение на основе селекторныхразбиений БП . . . . . . . . . .

. . . . . . . . . . . . . . . . . . . . . . 18§4 Асимптотические оценки высокой степени точности для сложностиитеративных контактных схем и контактных схем из ориентированныхконтактов . . . . . . . . . . . . . . . . . . . . .

. . . . . . . . . . . . . . 23§5 Асимптотически наилучший метод синтеза СФЭ в произвольном базисе.Асимптотические оценки высокой степени точности для сложностиусилительных СФЭ в некоторых базисах . . . . . . . . . . . . . . . . . 28§6 Асимптотически наилучший метод синтеза формул в произвольномбазисе. Асимптотические оценки высокой степени точности для сложностиформул в некоторых базисах .

. . . . . . . . . . . . . . . . . . . . . . . 33§7 Мультиплексорные ФАЛ и обобщённое разложение. Оптимальная позадержке реализация мультиплексорных ФАЛ в произвольном базисе 37§8 Задача синтеза схем для функций из специальных классов, примерыеё решения и мощностные нижние оценки. Инвариантные классыС. В. Яблонского, теорема о числе инвариантных классов . . . . . . . 42§9 Принцип локального кодирования О. Б.

Лупанова и примеры его применения. 48§10 Синтез схем для не всюду определённых функций . . . . . . . . . . 532 Синтез схем для индивидуальных функций и оценки их сложности 59§1 Средняя проводимость схемы. Асимптотика контактной сложностиуниверсальных систем функций . . . . . . . . . .

. . . . . . . . . . . . 59§2 Забивание переменных константами. Сложность линейной функциив классе схем из функциональных элементов . . . . . . . . . . . . . . 612Оглавление§3§4§53Незабиваемые множества переменных. Асимптотика сложности мультиплексорав некоторых классах схем . . . . . . . . . . . . . .

. . . . . . . . . . . 65Сферические функции. Сложность линейной и других функций вклассе контактных схем и самокорректирующихся контактных схем68Теорема Храпченко. Сложность линейной функции в классе π–схем . 71Литература75Глава 1Асимптотически оптимальные методы синтеза схем иоценки высокой степени точности для ряда функцийШеннона. Синтез схем для функций из специальныхклассов1§1Некоторые модификации контактных схем. Итеративные контактные схемы. Верхние оценки числа схем контактного типа,нижние мощностные оценки функций ШеннонаРассмотрим одну модификацию контактных схем (КС), которая является, по существу, частным случаем т.н.

релейно-контактных схем (см., например, [4]) и связанас операцией присоединения управляющих булевых переменных (БП) или, иначе,управляющих входов КС к ее выходам.Для КС Σ = Σ(x1 , . . . , xn ; 1; z1 , . . . , zm ) определим операцию присоединения еёуправляющей БП xi к выходу zj , которая применима, если БП xi входит в Σ без отрицаний, и в результате выполнения которой в графе КС Σ происходит снятие БПzj , сопоставление связанной с ней вершине внутренней БП y и замена всех пометокxi на пометку y. Аналогично определяется операция (одновременного) присоединения нескольких управляющих БП КС Σ к её выходам, при выполнении которойкаждой участвующей в присоединениях выходной вершине Σ сопоставляется только одна внутренняя БП, причём разным вершинам сопоставляются разные БП.Любая из полученных таким образом схем называется итеративной контактнойсхемой (ИКС) на базе КС Σ. Под сложностью L(Σ0 ) ИКС Σ0 на базе КС Σ понимается сложность L(Σ).Функционированние итеративной контактной схемы Σ(x1 , .

. . , xn ; z1 , . . . , zm ) наb 1 , . . . , xn , y 0 , . . . , y 0 ; 1; y 00 , . . . , y 00 , z1 , . . . , zm ) с внутренними БПбазе КС вида Σ(x11llyi = yi0 = yi00 , i = 1, . . . , l, рассматривается в дискретные моменты времени t,t = 0, 1, . .

. . Для любого входного набора α = (α1 , . . . , αn ) ∈ B n при t = 0, 1, . . .происxодит последовательное установление в различных вершинах значения 1 в результате образования цепей, соединяющих эти вершины с входом 1 и состоящих изпроводящих к данному моменту контактов, а также значение 0 в результате образования разрезов, отделяющих рассматриваемые вершины от входа 1 и состоящих1Те понятия и обозначения, которые здесь не определяются могут быть найдены в [3], гл. 2, §34§1.51•x1•y1x1y2••x2x2 x2y1•••x3x3x2•z1 = x 1 ⊕ x 2 ⊕ x 3y2Рис. 1.1: Пример комбинационной ИКСиз непроводящих к данному моменту контактов. При этом вершина ui , связаннаяс БП yi , 1 6 i 6 l, в которой установилось значение σ, начинает в следующиймомент времени управлять проводимостью контактов yi и т.д. Обозначим черезV (σ) (Σ, α, t), σ ∈ B, множество тех вершин Σ, в которых к моменту времени t установилось значение σ, а через V (2) (Σ, α, t) — множество всех остальных вершин Σ,и заметим, чтоV (σ) (Σ, α, t) ⊆ V (σ) (Σ, α, t + 1),V (γ) (Σ, α, t) ∩ V (δ) (Σ, α, t) = ∅(1.1)для любого σ, σ ∈ B, и любых γ 6= δ из [0, 2].

Будем считать, что в момент времени tв вершинах множества V (2) (Σ, α, t) имеется неопределенное значение 2.Из (1.1) следует, что, начиная с некоторого T , T > 0, множества V (σ) (Σ, α, t),σ ∈ [0, 2], стабилизируются, то есть V (σ) (Σ, α, t + 1) = V (σ) (Σ, α, t) = V (σ) (Σ, α),при t > T , и будем говорить, что в момент времени T процесс функционированияИКС Σ на наборе α завершается, причем завершается он установлением значенияσ, σ ∈ [0, 2], во всех вершинах множества V (σ) (Σ, α). При этом ИКС Σ называется комбинационной схемой (схемой без памяти), если для любого входного набора α, α ∈ B n , её функционирование на наборе α завершается определённымизначениями во всех выходных вершинах z1 , .

. . , zm , которые определяют значенияf1 (α), . . . , fm (α) ФАЛ f1 , . . . , fm от БП x1 , . . . , xn , реализуемых Σ.На рис. 1.1 показана комбинационная ИКС, реализующая ФАЛ x1 ⊕x2 ⊕x3 ⊕1, ана рис. 1.2 — некомбинационная ИКС, которая реализует систему функций (f1 , f2 ),где f1 = f2 = 2x1 · x2 . Будем называть ИКС Σ(x1 , .

. . , xn ; z1 , . . . , zm ) на базеb 1 , . . . , xn , y 0 , . . . , y 0 ; 1; y 00 , . . . , y 00 , z1 , . . . , zm ) упорядоченой, если существуКС Σ(x11llет такая перестановка j1 , . . . , jl чисел 1, . . . , l, при которой для любого i, i ∈ [1, l],b может существенно зависеть только от БПФАЛ проводимости от 1 к yji в КС Σx1 , . . . , xn , yj1 , . .

. , yji−1 . Заметим, что упорядоченная ИКС Σ является комбинационной и что ИКС, показанная на рис. 1.1, является упорядоченной.6Глава 1.1•x1•x2•y2y1y1••y2Рис. 1.2: Пример некомбинационной ИКС−→По аналогии с классами UКС и UКС (см. [3]) контактных схем из неориентированных и ориентированных контактов соответственно обозначим через UИКС классвсех комбинационных ИКС из неориентированных контактов, а через UA (L, n), где−→A ∈ {КС, КС, ИКС} — множество схем от БП X(n) = {x1 , . . .

, xn } из UA , которыепредставляют собой связный граф, имеют один выход, один вход и сложность неболее L. В соответствии с [3] для конечного множества G, состоящего из графов,сетей или схем, через |G| и kGk обозначим число попарно не изоморфных и попарно не эквивалентных элементов в G.

В частности,число попарнонеэквивалентныхИКС из UИКС (L, n) будем обозначать через UИКС (L, n).Лемма 1.1. Число попарно неизоморфных связных графов с параллельными рёбра 2 q−p+13pми, содержащих p вершин и q, q > p − 1, рёбер, не больше, чем 4p−1 q−p+1,еслиp(p + 1)p−1<q 6− 2,(1.2)2и не больше, чем 4p−1 · 6q−p+1 , в остальных случаях.Доказательство. Подсчёт указанных графов можно организовать следующим образом: сначала выбирается остовное дерево, а потом оставшиеся рёбра распределяются по всевозможным парам вершин с возможными повторениями. Остовноедерево можно выбрать 4p−1 способами, а число возможных распределений оставшихся рёбер по парам вершин можно оценить сверху числом сочетаний с повторениями, при условии, что число пар вершин равно p(p−1).