ОКИ (2014) (15 - 23_ 29) (1133299)
Текст из файла
Определение инвариантного класса ФАЛ и его мощностной последовательности. Формулировка утверждения о поведении указанной последовательности и идея его доказательства. Часть 3 – страница 58 Множество ФАЛ , ⊆ ! называется инвариантным классом ФАЛ, если оно замкнуто относительно трех операций: 1) добавление или изъятие фиктивных БП (переход к равной ФАЛ) 2) переименование БП без отождествления (переход к конгруэнтной ФАЛ) 3) подстановка констант 0 или 1 вместо БП (переход к подфункции) Часть 3 – страница 58 Мощностная последовательность ФАЛ Q, где n = 1, 2, … log ()! = 2!Часть 3 – страница 59 Утв-‐ие о поведении мощностной последовательности: Пусть Q – инвариантный класс ФАЛ.
Тогда его мощностная последовательность ! монотонно не возрастает и сходится к пределу log ()! = lim ! = lim !→!!→!2!где ! удовлетворяет нер-‐вам 0 ≤ ! ≤ 1 Док-‐во: Из опр-‐ия последовательности ! следует, что для каждого n выполнено неравенство 0 ≤ ! ≤ 1, то есть эта последовательность ! ограничена. Покажем, что она монотонно не возрастает, откуда будет следовать ее сходимость.
В силу инвариантности класса Q, всякую функцию f из множества Q(n + 1) можно представить в виде ! , … , !!! = !!! ! ! , … , ! ∨ !!! ! (! , … , ! ) где ! ! , … , ! = (! , … , ! , ), ∈ и обе ФАЛ ! , ! принадлежат множеству Q(n). Отсюда сразу вытекает нер-‐во log ( + 1)log ! + 1 = ≤= ! 2!!!2!Монотонное невозрастание и, следовательно, сходимость последовательности ! , = 1, 2, … доказана, а принадлежность ее предела ! действительному отрезку [0, 1], следует из того, что ему принадлежат все члены данной последовательности. ч.т.д.
Формулировка утв-‐ия о построении − схем, формул и СФЭ, реализующих ФАЛ (мультиплексорную ФАЛ порядка n), об оценках их сложности и глубины; асимптотическое поведение сложности и поведение глубины ( ). Описание разложения (представления) ФАЛ , на котором основано доказательство приведенной в нем оценки для ее глубины, и структуры соответствующей формулы. Часть 3 – страница 14 ! ! ≥ 2! + ; ! ! ≥ 2! + 2 Часть 3 – страница 16 ! ! ≤ 3 ∗ 2! − 2; ! ! ≤ 2!!! − 3 Часть 3 – страница 21 ! ! ≥ 2!!! + − 1; ! ≥ + 1 -‐ метод Каскадов Часть 3 – страница 44 !!22! ! ≤ 2 ∗ 2! + ; ! ! ≤ 2 ∗ 2! + ; ! ≤ + 6 Часть 3 – страница 46 ! ! ≥ 2!!! ; ! = + (1) Доказательство приведенной оценки для глубины (Часть 3 – страница 44) основывавется на формуле ! для ФАЛ ! ! ! , … , ! , ! , … , !! !!!!! `! ` & &! `` ∈!!!! (! `` `` ∨ = !!!! ! !(! ` ,! `` ) ) ! ` ∈!!!`где ! – совершенная ДНФ ФАЛ ! , i = 1, …, и ! `` `` = ! `` ( `` ) Fn реализует мультиплексорную ФАЛ ! , бесповторна по БП ! , … , !! !! и что ! ≤ 3 Определение КС, корректирующей q замыканий, сложности реализации ФАЛ в классе таких схем и соответствующей функции Шеннона, асимптотическое поведение этой функции при q = 1.
Построение минимальных КС, реализующих линейные ФАЛ и корректирующих 1 обрыв, формулировка утв-‐ия о соответствующей сложности этих ФАЛ, идея получения нижней оценки. Часть 5 – страница 13 КС ∑ является (p, q) – самокорректирующейся КС (корректирует p обрывов и q замыканий), если любая КС ∑ `, которая может быть получена из КС ∑ в результате обрыва не более чем p, и замыкания не более чем q контактов, эквивалентна ∑. Часть 5 – страница 15 Для ФАЛ и ≥ 0, ≥ 0 определим ее (p, q) – контактную самокорректирующуюся сложность !!,! () как минимальную !сложность КС ∑, ∑ принадлежит (!,!), реализующей f, а затем введем соответствующую функцию Шеннона !! !,! = max! ∈!! (!) !,! () Часть 5 – страница 16 2!!! !,! ≈ !,! ≈ Часть 5 – страница 16 КС, реализующая ФАЛ ! и корректирующая 1 обрыв получается из схемы Кардо добавлением 4 дополнительных контактов, проведенных следующим образом: для каждого , ∈ из входа (выхода) этой схемы проведем контакт вида !! (соответственно !! ) и вершину, соединенную контактом вида !! (соответственно !! ) с ее выходом (соответственно входом).
Указанная схема является минимальной и, следовательно, справедливо утв-‐ие Для n = 1, 2, … имеют место равенства !!,! ! = !!,! ! = 4 Определение функции Шеннона ( ) и ( ) для сложности реализации ФАЛ из класса Q схемами из функциональных элементов и контактными схемами соответственно. Формулировка утверждения о нижней мощностной оценке этих функций. L! (Q n ) = max ! , где ! = min! ∑! !! ∈! !L! (Q n ) = max ! , где ! = ! ∈! !∑! ∈ ! ,реализующ.!∑!min ∈ ! ! ,реализующ.!Часть 3 – страница 56 Утверждение о нижней мощностной оценке Для класса ФАЛ Q такого, что = (!"# !(!)!"# !"# !(!)! ∑! ) ( log =(log log () ) выполняются следующие асимптотические неравенства log ()L! Q n ≽ log log ()соответственно log ()L! Q n ≽ log log () Утверждение о сложности формул, получаемых асимптотически наилучшим методом синтеза, и вытекающая из него верхняя оценка соответствующей функции Шеннона; поведение функции Шеннона для глубины ФАЛ.
Описание разложения (представления) ФАЛ, на котором основано доказательство этого утверждения, и структуры соответствующей формулы. Часть 3 – страница 46 Для любой ФАЛ , ∈ ! в Ф существует реализующая ее формула ! , для которой 2!2 ∗ log log + (1) ! ≤ (1 + ) log log ! ≤наилучший − log log метод+ 8 +синтеза(1) формул 47§7. Асимптотически 0Часть 3Положим – страница x 4=8 (x1 , . .
. , xq ) и заметим, что произвольнаяПоведение глубины ФАЛh, h 2 дPля 2 (q), на любой компонентеi , i 2 [1, 2 ], в силу!2ее m-регулярности совпадаетФАЛ ĥ(x1 , . . . , xm ).Ф ∼с некоторой log p ФАЛ из ДУМ G, кажПри этом ФАЛ ĥ равна дизъюнкции= − log log+ (1) на i с буквойдая из которых в силулеммы6.1 совпадаетЧасть 3 – сизтраница 47 , . . . , xq . Следовательно, ФАЛ h совпадаетоднойБП xm+1Описание ля указанныхдоказательства на i сразложения ЭД ранга pдотБП.
утверждения Для ФАЛ f (x) из P2 (n), где x = (x1 , . . . , xn ), x00 =(xq+1 , . . . , xn ) рассмотрим ее представление в видеf (x) =_=00 =(=2q_mi=1гдеiq+1 ,..., n )i0x0 @0q+1xq+1· · · xnn @00 =(_q+1 ,..., n )2q_mi=1ix0 fq+1xq+1· · · xnn J00,i001x0 A =1x0 A, (7.3)(x0 ) � характеристическая ФАЛ множества i , i = 1, . . . , 2qа ЭД J 00,i ранга p от БП xm+1 , . . . , xq , совпадает на i с ФАЛf 00 (x0 ) = f (x0 , 00 ).e f с подПостроим для ФАЛ f на основе (7.3) формулу Fнятыми отрицаниями, которая имеет вид2m,Определение КС, корректирующей p обрывов, сложности реализации ФАЛ в классе таких схем и соответствующей функции Шеннона, асимптотическое поведение этой функции при p = 1.
Построение КС, корректирующих 1 замыкание, на основе самокоррекции в подсхемах («звездах») из однотипных контактов, формулировка утверждения о сложности полученных КС и идея его доказательства. Часть 5 – страница 13 КС ∑ является (p, q) – самокорректирующейся КС (корректирует p обрывов и q замыканий), если любая КС ∑ `, которая может быть получена из КС ∑ в результате обрыва не более чем p, и замыкания не более чем q контактов, эквивалентна ∑. Часть 5 – страница 15 Для ФАЛ и ≥ 0, ≥ 0 определим ее (p, q) – контактную самокорректирующуюся сложность !!,! () как минимальную !сложность КС ∑, ∑ принадлежит (!,!), реализующей f, а затем введем соответствующую функцию Шеннона !! !,! = max! ∈!! (!) !,! () Часть 5 – страница 16 2!!! !,! ≈ !,! ≈ Часть 5 – страница 15 .
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
