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

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

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

Для любого n, n ∈ N, и для почти всех ФАЛ f, f ∈ P2 (n), имеют место соотношения:

1. Сформулировать утверждение о длине диагностического теста для почти всех таблиц.

Мощность теста называется также его длиной. Длина любого тупикового диагностического

теста для отделимой по столбцам матрицы из множества Bp,s заключена в пределах от до (s − 1).

1. Дать определение теста для таблицы и заданной цели контроля.

Пусть 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).

1. Выписать максимальную антицепь частично-упорядоченного множества целых чисел отрезка [1, 10] с отношениями делимости.

1. Дать определение функции Шеннона R(n) ранга ДНФ и указать ее значение.

число вхождений в формулу символов переменных

1. Сформулировать утверждение о длине градиентного покрытия.

Пусть для действительного γ, 0<γ<1,в каждом столбце матрицы M, M ∈ Bp,s, имеется не меньше, чем γ ·p, единиц. Тогда покрытие матрицы M, получаемое с помощью градиентного алгоритма, имеет длину не больше, чем

Тест № 4

1. Дать определение тождества для формул, и его подстановки.

Формулы 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.

1. Дать определение подсхемы КС и указать правила применение к ней тождеств.

С хема Σ’ называется подсхемой схемы Σ, если V(Σ’)⊆ V (Σ), E(Σ’)⊆ E (Σ) и любая вершина v, v ∈ V (Σ_), которая либо относится к множеству входов (выходов) Σ, либо служит конечной (соответственно, начальной) вершиной некоторого ребра из E(Σ)\E(Σ_), является входом (соответственно, выходом) Σ’. Из определений следует, что для СФЭ и КС с неразделенными полюсами, как и для формул, имеет место принцип эквивалентной замены. При этом все введенные выше для случая эквивалентных преобразований формул понятия (однократная и кратная выводимость, полнота системы тождеств и др.), а также связанные с ними обозначения переносятся на случай ЭП указанных классов схем без изменений.

1. Привести основные тождества, связанные с:

   1. законом де Моргана для конъюнкции – в классах формул и СФЭ;

1. ветвлением выхода ФЭ отрицания – в классе СФЭ;

1. введением фиктивной БП в контакт – в классе КС.

1. Сформулировать утверждение о переходе от КПСТ для ЭП формул к КПСТ для ЭП СФЭ.

Пусть τ — КПСТ для ЭП формул из UΦБ, а Π’ и Π — системы тождеств для перехода от базиса Б к базису Б’ и от базиса Б’ к базису Б соответственно. Тогда система тождеств {Π’ (τ ) ,Π’ (Π)} является КПСТ для ЭП формул из UΦБ

1. Дать определение тождества для СФЭ, и его подстановки.

эквивалентностьсхем Σ’ и Σ’’ из U имеет место тогда и только тогда, когда Σ’и Σ’’ реализуют равные системы (матрицы) ФАЛ предполагается, что соответствующие друг другу полюса (выходы, входы) в Σ’ и Σ’’ имеют одинаковые пометки, а эквивалентность Σ’ и Σ’’ записывается в виде тождества t : Σ’ ∼ Σ’’. Для схем из U, как и для формул, определяется ряд «простейших» преобразований, сохраняющих эквивалентность схем, которые называются подстановками. Тождество которое получается в результате применения одной и той же подстановки к обеим частям тождества t : Σ’ ∼ Σ’’, называется подстановкой тождества t.

1. Дать определение подформулы данной формулы и указать правила применения к ней тождеств.

формулы, полученные в процессе индуктивного построения формулы F, называются ее подформулами. для формул имеет место так называемый принцип эквивалентной замены. Это означает, что если подформулу F’ (подформулу F’’)формулы F заменить, учитывая тождество t эквивалентной ей формулой F’’ (соответственно F’), то полученная в результате такой замены формула ˇF будет эквивалентна формуле F, то есть будет справедливо тождество ˇt : F = ˇF .

Аналогичный переход от F к F’ в результате применения одного из тождеств системы τ (нескольких последовательных применений тождеств из τ ) будем записывать в виде однократной (соответственно кратной) выводимости вида F →τ F’ (соответственно F ⇒|τ F’). При этом считается, что тождество t : F = F’ выводится из системы тождеств τ

1. Привести основные тождества, связанные с:

   1. подстановкой константы 0 в конъюнкцию – в классах формул и СФЭ;

1. снятием “висячего” входа – в классе СФЭ;

1. формульным тождеством вида – в классе КС.

1. Дать определение разделяющей КС и сформулировать лемму Шеннона.

Схема называется разделительной по входам(выходам), если ФАЛ проводимости между любыми ее различными входами (соответственно выходами) равна 0. Пусть КС Σ является результатом стыковки вида Σ = Σ’’ (Σ’), а F, F’ и F’’ — матрицы, реализуемые КС Σ, Σ’ и Σ’’ соответственно. Тогда если КС Σ’’ разделительна по входам или КС Σ’разделительна по выходам.

1. Дать определение тождества для КС, и его подстановки.

эквивалентность КС Σ’ = Σ’ (x1, . . . , xn; a1, . . . , am) и Σ’’ = Σ’’ (x1, . . . , xn; a1, . . . , am) означает, что для любых i и j из отрезка [1,m] ФАЛ проводимости от ai к aj в КС Σ’ равна ФАЛ проводимости от ai к aj в КС Σ’’. Определим подстановку для КС как переименование (с возможным отождествлением и инвертированием) БП, а также переименование (с возможным отождествлением и снятием) полюсов.

1. Дать определение подсхемы СФЭ и указать правила применения к ней тождеств.

С хема Σ_ называется подсхемой схемы Σ, если V(Σ’)⊆ V (Σ), E(Σ’)⊆ E (Σ) и любая вершина v, v ∈ V (Σ’), которая либо относится к множеству входов (выходов) Σ, либо служит конечной (соответственно, начальной) вершиной некоторого ребра из E(Σ)\E(Σ’), является входом (соответственно, выходом) Σ’.

Тождества: отождествление переменных, соединение/разделение полюсов

1. Привести основные тождества, связанные с:

   1. дистрибутивностью конъюнкции относительно дизъюнкций – в классах формул и СФЭ;

1. снятием “висячего” ФЭ отрицания – в классе СФЭ;

1. перебрасыванием контакта в трюхполюсной схеме - в классе КС.

1. Дать определение суммарного цикломатического числа КС и сформулировать утверждение о его изменениях при применении основных тождеств.

|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.

Тест № 5

1. Определение глубины D(f) ФАЛ f(x₁…x_n) и её тривиальная нижняя оценка для существенной ФАЛ f.

D (f)=minD(Σ) - глубина ФАЛ f относительно функционала L

Σ реал f,

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

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

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

γ = 0, a= 32n, y = LΦ(n) + 1, если U = UΦ;

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

1. Утверждение о нижней оценке сложности КС, реализующей заданную систему ФАЛ, и асимптотика сложности контактного дешифратора.

Для любой ФАЛ f, f ∈ P2 (n), существует реализующая ее КС Σf такая, что

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

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

Σ реал f,

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

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