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

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

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

. , 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 , если выполненысоотношения:LC (n)LΦ (n)LK (n)Lπ (n)D(n)≥≥≥≥≥• 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 — его характеристическими ФАЛ.4Для любых натуральных p, m, s, где p =порядка m и ранга p такое, что:Лемма 2m s, существует ДУМ G• λ = |G| ≤ p2s• в G имеется система из p ортогональных ФАЛ φ1 , . . . , φp , обладающих темсвойством, что для любой ФАЛ g, g ∈ P2 (m), и некоторых ФАЛ g1 , . . . , gp изG справедливо не только представление g = g1 ∨ · · · ∨ gp , но и представлениеg = φ1 g1 ∨ · · · ∨ φp gp .nLC (Q(n)) ∼ 43 · 2nМножество δ, δ ⊆ B q , называется m-регулярным множеством наборов куба B q ,если m < q , |δ| = 2m и все префиксы длины m наборов из δ различны.qЛемма Для любого m-регулярного множества наборов δ, δ ⊆ B , система множеств ∆ = (δ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 существует реализующая ее фор2 log log n+O(1)2nL(Ff ) ≤ log n 1 +log nмула Ff , для которойD(Ff ) ≤ n − log log n + 8 + o(1)2nΦD(n) ∼ n − log log n ± O(1)Следствие L (n) ∼ log n2nπСледствие L (n) ∼ log nKBCЛемма Для функции Шеннона L(n) имеет место асимптотическое равенn2KBCство L(n) ∼ nТеорема Для любой ФАЛ f, f ∈ P2 (n), существует реализующая ее КС ΣfОценкатакая, что L(Σf ) ≤2nn1 + O( √1n )nОтсюда с учетом нижней оценки вытекает, что LK (n) ∼ 2n~2nKСледствие Отсюда с учетом нижней оценки вытекает, что L (n) ∼ nЛемма Для системы ФАЛ Qn при n = 1, 2, 3, .

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

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

. . имеет место следующие асимптотические равенства2nKLK(1,0) (n) ∼ L(0,1) (n) ∼ nKLK(p,q) (f )6.

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

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