Основы кибернетики - Теормин (часть 3) 2010 (1133257), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

. . ,такои,что ε(n) ≥ 0 при n ≥ n0 и lim ε(n) → 0, выполняются неравенства:x→∞nLC (n) ≥ (1 + ε(n)) 2nLC (n) &n2LΦ (n) ≥ (1 − ε(n)) lognnLK (n) ≥ (1 − ε(n)) 2nLΦ (n) &Следствие LK (n) &n2Lπ (n) ≥ (1 − ε(n)) lognLπ (n) &2nn2nlog n2nn2nlog nD(n) ≥ n − log log n − ε(n)T (n) ≥ n − log log n − o(1)Следствие Нижние оценки из теоремы при указанных в доказательствезначениях ε(n) справедливы для сложности (глубины) почти всех ФАЛ f, f ∈P2 (n), при их реализации в соответствующих классах схем.6LC (n) ε =LΦ (n) ε =log n−6n6log n4nLK (n) ε =Лемма Для класса ФАЛ Q такого, что log n = o(log log |Q(n)|), выполняютсяследующие асимптотические неравенстваМножество ФАЛ G,G∈LK (Q(n) &log Q(n)log log Q(n)log Q(n)log log Q(n)LC (Q(n) &P2 (m), называется дизъюнктивно-универсальным множеством (ДУМ) порядка m и ранга p, если любая ФАЛg, g ∈ P2 (m), может быть представлена в виде g = g1 ∨ · · · ∨ gp , gi ∈ G ∀i =1, . . . , p.Пусть Π = (π1 , .

. . , πp ) - разбиение куба B m , и пусть для всех i , i = 1, . . . , pФАЛ ϕi (x1 , . . . , xm ) — характеристическая ФАЛ множества πi , а G(i) — множество всех таких ФАЛ g, g ∈ P2 (m), которые обращаются в 0 не в πi . Тогдамножество ФАЛ G = G(0) ∪ · · · ∪ G(p) является ДУМ порядка m и ранга p. ДУМG будем называть стандартным ДУМ порядка m и высоты s, где s ≤ 2m , есливыполнены соотношения:• p=⌈ 2m ⌉s, s1 = s2 = · · · = sp−1 = s , sp = 2m − (p − 1)s ≤ s.• Π = (π1 , . . . , πp ) — разбиение куба Bm на последовательные отрезки, тоесть такое разбиение, что номер любого набора из множества πi меньшеномера любого набора из множества πj , если i < j• Для любого i ∈ [1 .

. . p] мощность |πi | = si .Компоненты разбиения Π будем при этом называть полосами ДУМ G, а ФАЛϕ1 , . . . , ϕp — его характеристическими ФАЛ.Лемма Для любых натуральных p, m, s, где p =⌈ 2m ⌉s , существует ДУМ G по-рядка m и ранга p такое, что:• λ = |G| ≤ p2s• в G имеется система из p ортогональных ФАЛ ϕ1 , . . . , ϕp , обладающих темсвоиством, что для любои ФАЛ g, g ∈ P2 (m), и некоторых ФАЛ g1 , .

. . , gp изG справедливо не только представление g = g1 ∨ · · · ∨ gp , но и представление g = ϕ1 g1 ∨ · · · ∨ ϕp gp .7Оценка LC (Q(n)) ∼34·2nnМножество δ, δ ⊆ B q , называется m-регулярным множеством наборов кубаB q , если m < q, |δ| = 2m и все префиксы длины m наборов из δ различны.Лемма Для любого m-регулярного множества наборов δ, δ ⊆ B q , системамножеств ∆ = (δ1 , . . .

, δ2q−m ), где δi = δ⊕α и ν(α) = i−1 при всех i, i = 1, . . . , 2q−m, образует разбиение куба B q на m-регулярные подмножества.Лемма Для любых натуральных m, λ, q = m + λ и для любои системыФАЛ g = (g1 , . . . , gλ ) из P2λ (m) существует m-регулярное разбиение ∆ =(δ1 , . . . , δ2q−m ) куба B q такое, что любая ФАЛ gi на любои компоненте δj совпадает либо с однои из БП xm+1 , . . .

, xq , либо с ее отрицанием.ΦТеорема Для любои ФАЛ f, f ∈ P2 (n),( в U существует) реализующая ее фор-мула Ff , для котороиL(Ff ) ≤2nlog n1+2 log log n+O(1)log nD(Ff ) ≤ n − log log n + 8 + o(1)2nСледствие LΦ (n) ∼ logn D(n) ∼ n − log log n ± O(1)Следствие Lπ (n) ∼2nlog nЛемма Для функции Шеннона LKBC (n) имеет место асимптотическое равенство LKBC (n) ∼2nnТеорема Для любои ФАЛ f, f ∈ P2 (n), существует реализующая ее КС Σf та)(2n1√кая, что L(Σf ) ≤ n 1 + O( n )Следствие Отсюда с учетом нижнеи оценки вытекает, что LK (n) ∼⃗Следствие Отсюда с учетом нижнеи оценки вытекает, что LK (n) ∼2nn2nnЛемма Для системы ФАЛ Qn при n = 1, 2, 3, .

. . выполняется неравенствоnLK (Qn ) ≤ 2n + O( 2n )Следствие LK (Qn ) ∼ 2nЛемма Для системы ФАЛ Jn при n = 1, 2, 3, . . . выполняется неравенствоnLK (Jn ) ≤ 2n+1 + O( 2n )Следствие LK (Jn ) ∼ 2n+1Самокорректирующиеся КС. 2 возможных неисправных состояния:• Состояние обрыва – контакт не проводит• Состояние замыкания – контакт проводит при любых значениях управляющеи им БП8КС Σ является (p, q)-самокорректирующеися КС или, иначе, корректирует pобрывов и q замыкании, где p ≥ 0, q ≥ 0, если любая КС Σ′ , которая может бытьполучена из КС Σ в результате обрыва не более, чем p, и замыкания не более,чем q, контактов, эквивалентна Σ.Обозначим через UK( p, q) множество всех (p, q)- самокорректирующихся КСKи заметим, что UK( 0, 0) = U .Лемма Для любых p ≥ 0, q ≥ 0 и любои КС Σ существует эквивалентная еи′КС Σ′ , Σ′ ∈ UK( p, q), для которои L(Σ ) ≤ (p + 1)(q + 1)L(Σ).Будем называть однородной любую связную КС с неразделенными полюсами, состоящую из контактов одного и того же типа.

Представление КС Σ ввиде объединения ее однородных подсхем без общих контактов будем называть однородным разбиением КС Σ, а минимальное число подсхем в такихразбиениях будем обозначать через ζ(Σ).Лемма Для любои КС Σ существуют эквивалентные еи (1, 0)- и (0, 1)самокорректирующиеся КС Σ и Σ′′ соответственно такие, что L(Σ′ ) ≤ L(Σ) +ζ(Σ) L(Σ′′ ) ≤ L(Σ) + ζ(Σ)Этот способ позволяет установить асимптотику функции Шеннона для сложности КС из UK(0,1) и UK(1,0).KФункция Шеннона: LK(p,q) (n) = max L(p,q) (f ).Очевидно, что L (f ) ≤KLK(p,q) (f )f ∈P2 (n)KL (n) ≤ LK(p,q) (n).Теорема Для n = 1, 2, .

. . имеет место следующие асимптотические равенKства LK(1,0) (n) ∼ L(0,1) (n) ∼2nn9.

Характеристики

Список файлов ответов (шпаргалок)