Тесты с почти всеми ответами2 (1133185), страница 2
Текст из файла (страница 2)
Дать определение функции Шеннона λ(n) для длины сокращенной ДНФ и привести её оценки.Число ЭК (ЭД) в ДНФ (соответственно КНФ) A называется ее длиной и обозначается через λ (A).Для любого n, n ∈ N, и для почти всех ФАЛ f, f ∈ P2 (n), имеют место соотношения:4. Сформулировать утверждение об особенностях ДНФ для монотонных ФАЛ.Сокращенная ДНФ A монотонной ФАЛ f ∈ P2 (n), является единственной тупиковой ДНФ этой ФАЛ и имеет вид:Сопоставим каждому набору β из Bn, монотонную ЭКK+β от БП X (n), состоящую из тех и только тех букв xj ,j ∈ [1, n], для которыхβ j = 1,1.
Дать определение покрытия матрицы и ФАЛ покрытия.Пусть N = {α1, . . . , αs} — конечное множество, а N == (N1, . . . ,Np) — система его подмножеств, образующих покрытиемножества N. Сопоставим паре (N,N) матрицу M, M ∈ Bp,s, для которой M i, j = 1 тогда и только тогда, когда αj ∈Ni . i-я строкаматрицы M покрывает ее j-й столбец, если M_i, j = 1, то есть αj ∈Ni и что система строк с номерами из I, I ⊆ [1, p], образуетпокрытие матрицы M, если каждый ее столбец покрывается хотя бы одной строкой с номером из I, то есть система подмножеств{Ni}i∈I задает покрытие множества N.Рассмотрим ФАЛ F (y), для которой F (β) = 1 тогда и только тогда, когда система строк матрицы M с номерами из I (β) образует еепокрытие, и будемназывать эту ФАЛ функцией покрытия матрицы M.2. Выписать сокращённую ДНФ монотонной ФАЛ с множеством нижних единиц {(0011), (1001), (0110)}.'x1'x2x3x4Vx1'x2'x3x4V'x1x2x3'x43.
Дать определение функции Шеннона λ(n) для длины ДНФ и указать её значение.Число ЭК (ЭД) в ДНФ (соответственно КНФ) A называется ее длиной и обозначается через λ (A).Для любого n, n ∈ N, и для почти всех ФАЛ f, f ∈ P2 (n), имеют место соотношения:4. Сформулировать утверждение о длине диагностического теста для почти всех таблиц.Мощность теста называется также его длиной. Длина любого тупикового диагностическоготеста для отделимой по столбцам матрицы из множества Bp,s заключена в пределах отдо (s − 1).a.
Дать определение теста для таблицы и заданной цели контроля.Пусть M, M ∈ Bp,s, — отделимая по столбцам матрица, а N — связанная с ней цель контроля.Сопоставим i-й строке, i ∈ [1, p], матрицы M БП yi, а каждому набору β, β ∈ Bp, значений этих переменных y = (y1, . . . , yp) —множество строк матрицы M с номерами из множества I = I (β) ⊆ [1, p], где i ∈ I (β) тогда и только тогда, когда β _i_ = 1.Рассмотрим ФАЛ F (y), для которой F (β) = 1 тогда и только тогда, когда система строк матрицы M с номерами из I (β) образует тестдля (M,N), и будем называть эту ФАЛ функцией теста для (M, N).b.Выписать максимальную антицепь частично-упорядоченного множества целых чисел отрезка [1, 10] сотношениями делимости.c.Дать определение функции Шеннона R(n) ранга ДНФ и указать ее значение.число вхождений в формулу символов переменныхd.
Сформулировать утверждение о длине градиентного покрытия.Пусть для действительного γ, 0<γ<1,в каждом столбце матрицы M, M ∈ Bp,s, имеется не меньше, чем γ ·p, единиц. Тогда покрытиематрицы M, получаемое с помощью градиентного алгоритма, имеет длину не больше, чемТест № 41. Дать определение тождества для формул, и его подстановки.Формулы F’ и F’’, реализующие равные функции f’ и F’’, называются равными или, иначе, эквивалентными. При этом равенствовида t : F’ = F’’ считается тождеством.Для того, чтобы выделить набор x = (xi1, . .
. , xin), который состоит из всех различных БПалфавита X, встречающихся в формуле F и перечисленных в порядке возрастания их номеров, будем записывать ее в виде F = F(x). При этом формулу, которая получается из F в результате заменыкаждого вхождения БП xij, j = 1, . . . , n, формулой Fj будем считать результатом подстановки формулы Fj вместо БП xij, j = 1, .
. . ,n, в формулу F и будем обозначать ее через F (F1, . . . , Fn).если указанную подстановку применить к обеим частям тождества t : F’ = F’’, где F’ = F’ (x) и F’’ = F’’ (x), мы получим тождествокоторое называется подстановкой для тождества t.2. Дать определение подсхемы КС и указать правила применение к ней тождеств.С хема Σ’ называется подсхемой схемы Σ, если V(Σ’)⊆ V (Σ), E(Σ’)⊆ E (Σ) и любая вершина v, v ∈ V (Σ_), которая либо относится кмножеству входов (выходов) Σ, либо служит конечной (соответственно, начальной) вершиной некоторого ребра из E(Σ)\E(Σ_),является входом (соответственно, выходом) Σ’.
Из определений следует, что для СФЭ и КС с неразделенными полюсами, как и дляформул, имеет место принцип эквивалентной замены. При этом все введенные выше для случая эквивалентных преобразованийформул понятия (однократная и кратная выводимость, полнота системы тождеств и др.), а также связанные с ними обозначенияпереносятся на случай ЭП указанных классов схем без изменений.3.Привести основные тождества, связанные с:a) законом де Моргана для конъюнкции – в классах формул и СФЭ;b)ветвлением выхода ФЭ отрицания – в классе СФЭ;c)введением фиктивной БП в контакт – в классе КС.4.
Сформулировать утверждение о переходе от КПСТ для ЭП формул к КПСТ для ЭП СФЭ.Пусть τ — КПСТ для ЭП формул из UΦБ, а Π’ и Π — системы тождеств для перехода от базиса Б к базису Б’ и от базиса Б’ к базису Бсоответственно. Тогда система тождеств {Π’ (τ ) ,Π’ (Π)} является КПСТ для ЭП формул из UΦБ1. Дать определение тождества для СФЭ, и его подстановки.эквивалентностьсхем Σ’ и Σ’’ из U имеет место тогда и только тогда, когда Σ’и Σ’’ реализуют равные системы (матрицы) ФАЛпредполагается, что соответствующие друг другу полюса (выходы, входы) в Σ’ и Σ’’ имеют одинаковые пометки, а эквивалентностьΣ’ и Σ’’ записывается в виде тождества t : Σ’ ∼ Σ’’. Для схем из U, как и для формул, определяется ряд «простейших»преобразований, сохраняющих эквивалентность схем, которые называются подстановками.
Тождествокотороеполучается в результате применения одной и той же подстановки к обеим частям тождества t : Σ’ ∼ Σ’’, называется подстановкойтождества t.2. Дать определение подформулы данной формулы и указать правила применения к ней тождеств.формулы, полученные в процессе индуктивного построения формулы F, называются ее подформулами. для формул имеет место такназываемый принцип эквивалентной замены. Это означает, что если подформулу F’ (подформулу F’’)формулы F заменить, учитываятождество t эквивалентной ей формулой F’’ (соответственно F’), то полученная в результате такой замены формула ˇF будетэквивалентна формуле F, то есть будет справедливо тождество ˇt : F = ˇF .Аналогичный переход от F к F’ в результате применения одного из тождеств системы τ (нескольких последовательных примененийтождеств из τ ) будем записывать в виде однократной (соответственно кратной) выводимости вида F →τ F’ (соответственно F ⇒|τF’). При этом считается, что тождество t : F = F’ выводится из системы тождеств τ3.Привести основные тождества, связанные с:a) подстановкой константы 0 в конъюнкцию – в классах формул и СФЭ;b)снятием “висячего” входа – в классе СФЭ;c)формульным тождеством видаx⋅ x = 0– в классе КС.4.
Дать определение разделяющей КС и сформулировать лемму Шеннона.Схема называется разделительной по входам(выходам), если ФАЛ проводимости между любыми ее различными входами(соответственно выходами) равна 0. Пусть КС Σ является результатом стыковки вида Σ = Σ’’ (Σ’), а F, F’ и F’’ — матрицы,реализуемые КС Σ, Σ’ и Σ’’ соответственно. ТогдаΣ’разделительна по выходам.если КС Σ’’ разделительна по входам или КС1.
Дать определение тождества для КС, и его подстановки.эквивалентность КС Σ’ = Σ’ (x1, . . . , xn; a1, . . . , am) и Σ’’ = Σ’’ (x1, . . . , xn; a1, . . . , am) означает, что для любых i и j изотрезка [1,m] ФАЛ проводимости от ai к aj в КС Σ’ равна ФАЛ проводимости от ai к aj в КС Σ’’. Определим подстановку для КС какпереименование (с возможным отождествлением и инвертированием) БП, а также переименование (с возможным отождествлениеми снятием) полюсов.2.
Дать определение подсхемы СФЭ и указать правила применения к ней тождеств.С хема Σ_ называется подсхемой схемы Σ, если V(Σ’)⊆ V (Σ), E(Σ’)⊆ E (Σ) и любая вершина v, v ∈ V (Σ’), которая либо относится кмножеству входов (выходов) Σ, либо служит конечной (соответственно, начальной) вершиной некоторого ребра из E(Σ)\E(Σ’),является входом (соответственно, выходом) Σ’.Тождества: отождествление переменных, соединение/разделение полюсов3.4.Привести основные тождества, связанные с:a) дистрибутивностью конъюнкции относительно дизъюнкций – в классах формул и СФЭ;b)снятием “висячего” ФЭ отрицания – в классе СФЭ;c)перебрасыванием контакта в трюхполюсной схеме - в классе КС.Дать определение суммарного цикломатического числа КС и сформулировать утверждение о его измененияхпри применении основных тождеств.|E (G)| − |V (G)| + |c (G)| называется цикломатическим числом графа G.
множество вершин V = V (G) и множество ребер E = E(G) множество всех связных компонент обозначается через c (G)Для КС Σ от БП x1, . . . , xn и набора α, α ∈ Bn, определим величину Θ(Σ, α) = |E (Σ|α)| − |V (Σ|α)| + |c (Σ|α)| ,которая задаетцикломатическое число графа Σ|α. Положим, далее,Θ(Σ) = α∈Bn Θ(Σ, α) .Если Σ_ (x1, . . . , xn) ⇒{t1−t5}Σ’’ (x1, . . . , xn), то Θ(Σ’) = Θ(Σ’’), а если Σ’ ⇒τkΣ’’, где k < n, то Θ(Σ’)−Θ(Σ’’) делится на 2n−k.Тест № 51. Определение глубины D(f) ФАЛ f(x1…xn) и её тривиальная нижняя оценка для существенной ФАЛ f.D (f)=minD(Σ) - глубина ФАЛ f относительно функционала LΣ реал f,2.Определение функции Шеннона LC(n) и её верхняя оценка, получаемая методом Шеннона.L(n) = max L(f), f принадлежит P2(n)-Функция Шеннона для класса UC относительно функционала сложности L.3.Нижняя мощностная оценка функции Шеннона LФ(n) и то соотношение, из которого она выводится.γ = 0, a= 32n, y = LΦ(n) + 1, если U = UΦ;4.Верхняя оценка функции Шеннона Lk(n), получаемая асимптотически наилучшим способом.5.Утверждение о нижней оценке сложности КС, реализующей заданную систему ФАЛ, и асимптотика сложностиконтактного дешифратора.Для любой ФАЛ f, f ∈ P2 (n), существует реализующая ее КС Σf такая, что1.
Определение сложности LC(f) ФАЛ f в классе СФЭ и её тривиальная нижняя оценка для существенной ФАЛ f.LC (f)=minL(Σ) - сложность ФАЛ f в классе U C относ функционала LΣ реал f,UC Э ΣLC (f)>=n-12.Определение функции Шеннона LФ(n) и её верхняя нижняя оценка, получаемая с помощью моделирования совершеннойДНФ на основе контактного дерева.L(n) = max L(f), f принадлежит P2(n)-Функция Шеннона для класса UФ относительно функционала сложности L.3.Нижняя мощностная оценка функции Шеннона Lk(n) и то соотношение, из которого она выводится.γ = 1, a= 8n, y = LK(n), если U = UK;4.Верхняя оценка функции Шеннона D(n), получаемая асимптотически наилучшим способом5.Определение регулярного множества наборов единичного куба и формулировка утверждения о разбиениикуба на такие подмножества.Множество δ, δ ⊆ Bq, называется m-регулярным множеством наборов куба Bq, если m < q, |δ| = 2m, и все префиксы длины mнаборов из δ различны.
Для любого m-регулярного множества наборов δ, δ ⊆ Bq, система множеств ∆ = (δ1, . . . , δ2q−m), где δi =δ⊕α и ν (α) = i−1 при всех i, i = 1, . . . , 2q−m, образует разбиение куба Bq на m-регулярные подмножества.1.Определение сложности Lk(f) ФАЛ f(x1…xn) в классе КС и её тривиальная нижняя оценка для существеннойФАЛ f.Lk (f)>=n2. Определение функции Шеннона D(n) и её верхняя оценка, получаемая с помощью моделирования совершенной ДНФ.D(n) = max D(f), f принадлежит P2(n)-Функция Шеннона для класса U относительно функционала глубины D.3.Нижняя мощностная оценка функции Шеннона LC(n) и то соотношение, из которого она выводится.γ = 1, a= 32, y= LC(n) + n, если U = UC;4. Верхняя оценка функции Шеннона LФ(n), получаемая асимптотически наилучшим способом.LФ(n)<2n/logn5.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
