Тестирование по ОК2 big (1133189), страница 3

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

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

U ^C Э Σ

L^C (f)>=n-1

1. Определение функции Шеннона L^Ф(n) и её верхняя нижняя оценка, получаемая с помощью моделирования совершенной ДНФ на основе контактного дерева.

L(n) = max L(f), f принадлежит P2(n)-Функция Шеннона для класса U^Ф относительно функционала сложности L.

1. Нижняя мощностная оценка функции Шеннона L^k(n) и то соотношение, из которого она выводится.

γ = 1, a= 8n, y = LK(n), если U = UK;

1. Верхняя оценка функции Шеннона D(n), получаемая асимптотически наилучшим способом

1. Определение регулярного множества наборов единичного куба и формулировка утверждения о разбиении куба на такие подмножества.

Множество δ, δ ⊆ Bq, называется m-регулярным множеством наборов куба Bq, если m < q, |δ| = 2m, и все префиксы длины m наборов из δ различны. Для любого m-регулярного множества наборов δ, δ ⊆ Bq, система множеств ∆ = (δ1, . . . , δ2q−m), где δi = δ⊕α и ν (α) = i−1 при всех i, i = 1, . . . , 2q−m, образует разбиение куба Bq на m-регулярные подмножества.

1. Определение сложности L^k(f) ФАЛ f(x₁…x_n) в классе КС и её тривиальная нижняя оценка для существенной ФАЛ f.

L^k (f)>=n

1. Определение функции Шеннона D(n) и её верхняя оценка, получаемая с помощью моделирования совершенной ДНФ.

D(n) = max D(f), f принадлежит P2(n)-Функция Шеннона для класса U относительно функционала глубины D.

1. Нижняя мощностная оценка функции Шеннона L^C(n) и то соотношение, из которого она выводится.

γ = 1, a= 32, y= LC(n) + n, если U = UC;

1. Верхняя оценка функции Шеннона L^Ф(n), получаемая асимптотически наилучшим способом.

L^Ф(n)<2ⁿ/logn

1. Определение ДУМ и описание стандартного ДУМ.

Множество ФАЛ G, G ⊆ P2 (m), называется дизъюнктивно-универсальным множеством (ДУМ) порядка m и ранга p, если любая ФАЛ g, g ∈ P2 (m), может быть представлена в виде g = g1 ∨ . . . ∨ gp, где gi ∈ G при всех i, i = 1, . . . , p. Стандартный способ построения таких множеств связан с разбиениями единичного куба. Пусть Π = (π1, . . . , πp) — разбиение куба Bm, и пусть для всех i, i = 1, . . . , p, ФАЛ χi (x1, . . . , xm) — характеристическая ФАЛ множества πi, а G(i) — множество всех тех ФАЛ g, g ∈ P2 (m), которые обращаются в 0 вне πi. Заметим, что множество ФАЛ G вида

G = G(1) ∪ . . . ∪ G(p) является ДУМ порядка m и ранга p. Действительно, любая ФАЛ g, g ∈ P2 (m), может быть представлена в виде g = g1 ∨ . . . ∨ gp, где gi = χig и, следовательно, gi ∈ G(i) для всех i, i = 1, . . . , p.

1. Определение сложности L^Ф(f) ФАЛ f(x₁...x_n) в классе формул и её тривиальная нижняя оценка для существенной ФАЛ.

L^Ф(f)=minL(Σ) - сложность ФАЛ f в классе U^Ф относ функционала L

Σ реал f,

U^Ф Э Σ

L^Ф(f)>=n-1

1. Определение функции Шеннона L^k(n) и её верхняя оценка, получаемая методом Шеннона.

L(n) = max L(f), f принадлежит P2(n)-Функция Шеннона для класса U^k относительно функционала сложности L.

1. Нижняя мощностная оценка функции Шеннона D(n) и то соотношение, из которого она выводится.

Аналогичным образом на основе неравенства и равенства c использованием леммы 4.1, где q = 22n,y = 2D(n), γ = 0, α = 1 и a = 64n, устанавливается справедливость при ε (n) = 12/log n.

1. Верхняя оценка функции Шеннона L^C(n), получаемая асимптотически наилучшим способом.

2. Формулировка утверждения, из которого следует минимальность контактного дерева в классе разделительных КС.

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

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