Тесты с почти всеми ответами2 (1133185), страница 3

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

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

Определение ДУМ и описание стандартного ДУМ.Множество ФАЛ 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(x1...xn) в классе формул и её тривиальная нижняя оценка длясущественной ФАЛ.LФ(f)=minL(Σ)- сложность ФАЛ f в классе UФ относ функционала LΣ реал f,UФ Э ΣФL (f)>=n-12.Определение функции Шеннона Lk(n) и её верхняя оценка, получаемая методом Шеннона.L(n) = max L(f), f принадлежит P2(n)-Функция Шеннона для класса Uk относительно функционала сложности L.3.Нижняя мощностная оценка функции Шеннона D(n) и то соотношение, из которого она выводится.Аналогичным образом на основе неравенства и равенства c использованиемлеммы 4.1, где q = 22n,y = 2D(n), γ = 0, α = 1 и a = 64n, устанавливается справедливость при ε (n) = 12/log n.4.5.Верхняя оценка функции Шеннона LC(n), получаемая асимптотически наилучшим способом.Формулировка утверждения, из которого следует минимальность контактного дерева в классе разделительных КС..

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

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