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

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

Текст из файла

Тест №1

1. Определение элементарной конъюнкции и ДНФ.

Функции xi и xi будем называть буквами БП xi и, как обычно, будем считать, что x0i = xi, x1i = не xi. Конъюнкция (дизъюнкция) r, 1<r<n букв различных БП из множества X (n) называется элементарной конъюнкцией (соответственно элементарной дизъюнкцией) ранга r от булевых переменных X (n).

Дизъюнкция различных элементарных конъюнкций называется дизъюнктивной нормальной формой (ДНФ)

1. Определение нерасширяемой ДНФ.

Любая ДНФ A’, которую можно получить из ДНФ A путем формирования в ней с помощью тождеств ассоциативности и коммутативности подформул вида xiK’ ∨ не(xi)K’’, применения к этим подформулам тождества обобщенного склеивания xiK’ ∨ xiK’’ = xiK’ ∨ не(xi)K’’ ∨ K’K’’ и последующего приведения подобных, называется расширением ДНФ A.

1. Определение ДНФ сумма тупиковых.

ДНФ пересечение тупиковых (сумма тупиковых) ФАЛ f, есть дизъюнкция всех тех различных простых импликант этой ФАЛ, которые входят в любую (соответственно хотя бы в одну) тупиковую ДНФ ФАЛ f.

1. Критерий вхождения простых импликант в ДНФ пересечение тупиковых.

Дизъюнктивная нормальная форма ∩T ФАЛ f состоит из тех простых импликант ФАЛ f, которые соответствуют ядровым граням этой ФАЛ.

1. Определение импликанты и простой импликанты.

Будем говорить, что ФАЛ f’ имплицирует ФАЛ f’’, если Nf’ ⊆ Nf’’ , то есть импликация (f’ → f’’) тождественно равна 1. Элементарная конъюнкция, которая имплицирует ФАЛ f, называется импликантой этой ФАЛ. Импликанта K ФАЛ f называется простой импликантой этой ФАЛ, если она не поглощается никакой другой отличной от нее импликантой ФАЛ f.

1. Определение минимальной ДНФ и кратчайшей ДНФ.

минимальная (кратчайшая) ДНФ ФАЛ f, есть ДНФ, которая имеет минимальный ранг (соответ-

ственно длину) среди всех ДНФ, реализующих f.

1. Определение ядровой точки, ядровой грани и ДНФ Квайна.

Набор α, α ∈ Bn, называется ядровой точкой ФАЛ f (x1, . . . , xn), если α ∈ Nf и α входит только в одну максимальную грань ФАЛ f. При этом грань NK, являющаяся максимальной гранью ФАЛ f и содержащая точку α, считается ядровой гранью ФАЛ f

Дизъюнктивная нормальная форма, получающаяся из сокращенной ДНФ ФАЛ f удалением тех ЭК K, для которых грань NK покрывается ядром ФАЛ f, но не входит в него, называется ДНФ Квайна этой ФАЛ.

1. Формулировка утверждения, связанного с построением сокращенной ДНФ из какой-либо КНФ.

Если неприводимая ДНФ A получается из КНФ B ФАЛ f в результате раскрытия скобок и приведения подобных, то A — сокращенная ДНФ ФАЛ f.

1. Определение сокращённой ДНФ.

Дизъюнкция всех простых импликант ФАЛ f называется ее сокращенной ДНФ.

1. Определение тупиковой ДНФ.

Будем говорить, что ДНФ A, реализующая ФАЛ f, является тупиковой ДНФ, если f не= A’ для

любой ДНФ A’, полученной из A в результате удаления некоторых букв или целых ЭК.

1. Определение пучка, регулярной точки и регулярной грани.

Для ФАЛ f (x1, . . . , xn) и набора α, α ∈ Nf , обозначим через Πα (f) множество всех проходящих через α максимальных граней ФАЛ f, которое мы будем называть пучком

ФАЛ f через точку α. Точку α, α ∈ Nf , будем называть регулярной точкой ФАЛ f, если найдется точка β, β ∈ Nf ,для которой имеет место строгое включение Πβ (f) ⊂ Πα (f).

Грань NK ФАЛ f называется регулярной гранью этойФАЛ, если все точки NK регулярны.

1. Формулировка утверждения, связанного с построением сокращённой ДНФ из какой-либо ДНФ.

Из любой ДНФ A ФАЛ f можно получить сокращенную ДНФ этой ФАЛ в результате построения последовательных строгих расширений и приведения подобных до получения неприводимой ДНФ, не имеющей строгих расширений.

Тест №2

1. Определение -схемы и её сложности.

Схемы, моделирующие ДНФ или КНФ, являются частным случаем т. н. параллельно-последовательных КСили, иначе, π-схем. Простейшей π-схемой считается любая (1, 1)-КС, которая состоит из одного контакта, соединяющего полюса. Если π-схемы Σ1 и Σ2 уже определены, то (1, 1)-КС Σ’ (Σ’’), которая получается в результате их параллельного (соответственно последовательного) соединения тоже является π-схемой.

1. Определение приведенной СФЭ.

Будем называть (1,m)-КС приведенной, если все изолированные вершины Σ являются ее полюсами, а все контакты и остальные вершины Σ принадлежат простым проводящим цепям, соединяющим ее вход и выходы.

1. Определение величины и её верхняя оценка.

Обозначим через UCБ (L, n) (UΦБ(L, n) и UΦБ[D, n]) множество приведенных СФЭ Σ = Σ(x1, . . . , xn; z1) (соответственно формул F = F (x1, . . . , xn)) над базисом Б, для которых L(Σ)<=L (соответственно L(F)<=L и D(F)<=D), L(Σ) — сложность Σ, то есть число всех ее ФЭ; D(Σ) — глубина Σ, то есть максимальная глубина ее вершин.

1. Утверждение о соотношениях между рангом, сложностью и глубиной одной и той же формулы.

Для формулы F, F ∈ UΦ, выполняются неравенства

1. Определение СФЭ в базисе {&, , } и её глубины.

Схемой из функциональных элементов над базисом Б называется ориентированная ациклическая упорядоченная сеть Σ, входная выборка которой состоит из всех истоков Σ, а вершины помечены следующим образом:

1. каждому входу (выходу) Σ сопоставлена БП из X (соответственно Z), являющаяся пометкой связанной с ним вершины, причем различным входам (выходам)сопоставлены различные БП, а упорядоченность вершин во входной и выходной выборках Σ определяется упорядоченностью сопоставленных им БП;

2. каждая отличная от истока вершина v схемы Σ помечена ФС ϕi, где ki = d+Σ (v).

D(Σ) — глубина Σ, то есть максимальная глубина ее вершин.

1. Определение подобных формул.

Формулы, получающиеся друг из друга эквивалентными преобразованиями на основе тождеств коммутативности и ассоциативности, называются подобными.

1. Определение величины и её верхняя оценка.

Uк (L, n) - множество приведенных (1, 1)-схем Σ из UA от БП X (n), для которых L(Σ) <= L.

Кол-во попарно неэквивалентных КС от n БП сложности <= L

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

Кол-во смены & -> V и наоборот по целям ( от корня к листьям)

Для любой формулы F из UΦ существует подобная ей формула ˇF такая, что

1. Определение (1,1) – КС от БП x₁,...,x_n и её функционирования (той ФАЛ, которую она реализует).

Сеть Σ с входами a_1, . . . , a_p и выходами a__ 1, . . . , a__ q , в которой все ребра (дуги) помечены переменными x1, . . . , xn или их отрицаниями x1, . . . , xn, называется (p, q)-контактной схемой (КС) от БП x1, . . . , xn

g (x1, . . . , xn) = K (C1) ∨ . . . ∨ K (Ct) можно использовать для построения (1, 1)-КС Σ_, в которой ФАЛ проводимости от входа a1 к выходу a2 описывается заданной ДНФ вида A = K1 ∨ . . . ∨ Kt,

где K1, . . . , Kt — различные ЭК, и которая «моделирует» ДНФ A. Указанная контактная схема Σ_ получается в результате проведения из a1 в a2 цепей C1, . . . , Ct без общих контактов и внутренних вершин так, что K (Ci) = Ki,i = 1, . . . , t

2. Определение эквивалентности двух СФЭ.

эквивалентными, если они реализуют равные системы ФАЛ

Эквивалентность схем Σ’ и Σ’’ из U имеет место тогда и только тогда, когда Σ’и Σ’’ реализуют равные системы (матрицы) ФАЛ предполагается, что соответствующие друг другу полюса (выходы, входы) в Σ’ и Σ’’ имеют одинаковые пометки, а эквивалентность Σ’ и Σ’’ записывается в виде тождества t : Σ’ ∼ Σ’’

3. Определение величины и её верхняя оценка.

множество приведенных формул F = F (x1, . . . , xn) над базисом Б0, для которых L(F) <= L

4. Определение вычисляющей программы (ВП) и ее ширины, утверждение о ширине ВП, моделирующей ДНФ.

Схема Σ, Σ ∈ UCБ с монотонной нумерацией вершин называется вычисляющей программой (ВП) над базисом Б

для любой дуги номер вершины, из которой она исходит, больше номера вершины, в которую эта дуга входит.

Максимальное число отрезков вида [i, ai), где i ∈ (n, p], имеющих непустое пересечение, называется шириной ВП Σ, и определяет минимальное число ячеек памяти, необходимых для хранения ее внутренних БП un+1, . . . , u где ai —максимальный номер команды, в которой встречается ui.

число ФЭ ВП Σ характеризует время выполнения ее вычисляющих команд на одном процессоре,

Тест №3

1. Дать определение частично-упорядоченного множества (ЧУМ), его ширины и ранжированного ЧУМ.

Отношение, обладающее свойствами рефлексивности,транзитивности и антисимметричности, будем называть отношением частичного порядка. Если τ — отношение частичного порядка на множестве A, то пару (A, τ ) будем называть частично упорядоченным множеством.

Максимальная мощность цепей (антицепей) частично упорядоченного множества называется его длиной (соответственно шириной).

Частично упорядоченное множество (A, τ ) длины t называется ранжированным частично упорядоченным множеством, если все его неуплотняемые цепи имеют мощность t.

1. Выписать КНФ для ФАЛ теста для таблицы и цели контроля {(1,2), (1,3), (2,4), (4,5)}

(K1 V K2)(K1 V K2 V K3 V K4)(K1 V K2 V K4)(K1 V K2 V K4)

1. Дать определение функции Шеннона (n) для длины сокращенной ДНФ и привести её оценки.

Число ЭК (ЭД) в ДНФ (соответственно КНФ) A называется ее длиной и обозначается через λ (A).

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

1. Сформулировать утверждение об особенностях ДНФ для монотонных ФАЛ.

Сокращенная ДНФ 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.

1. Выписать сокращённую ДНФ монотонной ФАЛ с множеством нижних единиц {(0011), (1001), (0110)}.

'x1'x2x3x4Vx1'x2'x3x4V'x1x2x3'x4

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

Число ЭК (ЭД) в ДНФ (соответственно КНФ) A называется ее длиной и обозначается через λ (A).

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

Тип файла документ

Документы такого типа открываются такими программами, как Microsoft Office Word на компьютерах Windows, Apple Pages на компьютерах Mac, Open Office - бесплатная альтернатива на различных платформах, в том числе Linux. Наиболее простым и современным решением будут Google документы, так как открываются онлайн без скачивания прямо в браузере на любой платформе. Существуют российские качественные аналоги, например от Яндекса.

Будьте внимательны на мобильных устройствах, так как там используются упрощённый функционал даже в официальном приложении от Microsoft, поэтому для просмотра скачивайте PDF-версию. А если нужно редактировать файл, то используйте оригинальный файл.

Файлы такого типа обычно разбиты на страницы, а текст может быть форматированным (жирный, курсив, выбор шрифта, таблицы и т.п.), а также в него можно добавлять изображения. Формат идеально подходит для рефератов, докладов и РПЗ курсовых проектов, которые необходимо распечатать. Кстати перед печатью также сохраняйте файл в PDF, так как принтер может начудить со шрифтами.

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