Тесты — Ответы (почти все) (1133111)

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

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

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

Схемы, моделирующие ДНФ или КНФ, являются частным случаем т. н. параллельно-последовательных КС или, иначе, π-схем.

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

При любых натуральных L и n выполняется неравенство ||Uπ (L, n)|| <= (64n)^L .

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

Вершина СФЭ называется висячей, если она является стоком, но не является выходом схемы. Схема называется приведенной, если в ней нет висячих вершин.

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

Обозначим через U^ф [D, n] {D – это глубина} множество формул F = F (x1, . . . , xn), для которых D(F) <= D.

||U^ф [D, n]|| <= _(32n)2^D

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

R(F) <= L(F) + 1 <= 2^D(F).

D(F) >= [log (L(F) + 1)] {это округление вверх}

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

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

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

2. каждая отличная от истока вершина v схемы E помечена ФС [FI]i, где ki = d⁺_E(v).

D(E) — глубина E, то есть максимальная глубина ее вершин. {глубина одной вершины – ноль, для всех остальных – максимальная глубина из поддеревьев + 1}

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

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

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

Обозначим через U^Ф(L, n) множество приведенных СФЭ E = E(x1, . . . , xn; z1), для которых

L(E) <= L (L(E) — сложность E, то есть число всех ее ФЭ)

||U^Ф (L, n)|| <= (32n)^L+1

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

Для каждой формулы F, F [принадлежит] U^Ф, индукцией по глубине определим величину Alt (F) так, что:

1. Alt (F) = 0, если F — ЭК или ЭД;

2. Alt(!F)= Alt(F) + 1, если F не является переменной;

3. Alt (F1 * · · · * Ft) = max {Alt (F1) , . . . , Alt (Ft)} + 1,где t >= 2 и * = {&, [дизъюнкция]}, если ни одна из формул F1, . . . , Ft не является формулой вида F’ * F’’ и хотя бы одна из них не является буквой.

Величину Alt (F) будем называть альтернированием формулы F.

Легко видеть, что альтернирование формулы F с поднятыми отрицаниями равно максимальному числу изменений типов ФЭ & и . в цепях дерева, соответствующего формуле F.

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

D(F’) <= log (L(F) + 1)+Alt (F)

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

Две СФЭ считаются изоморфными, если они изоморфны как помеченные графы, и эквивалентными, если они реализуют равные системы ФАЛ.

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

Схема E,E [принадлежит] U^C, с монотонной нумерацией вершин, называется вычисляющей программой (ВП) над базисом Б.

Предполагается, что команды ВП E выполняются последовательно в соответствии с их номерами в моменты времени 1, 2, . . . , p + m и что значение БП ui, вычисленное

момент времени i, i . (n, p], занимает отдельную битовую ячейку памяти на отрезке времени [i, ai), где ai - максимальный номер команды, в которой встречается ui.

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

Индукцией по длине можно показать что любая ДНФ или КНФ после ее оптимизации по числу отрицаний и выполнения некоторых преобразований подобия (см. §2), а также при подходящей монотонной нумерации вершин переходит в ВП ширины 2.

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

Формулы F’ и F’’, реализующие равные функции f’ и f’’, называются равными или, иначе, эквивалентными. При этом равенство вида t : F’ = F’’ считается тождеством.

формула F (F1, . . . , Fn) реализует ФАЛ f (f1, . . . , fn), где ФАЛ f (ФАЛ fj) — ФАЛ, реализуемая формулой F (соответственно Fj, j = 1, . . . , n). Отсюда следует, что если указанную подстановку применить к обеим частям тождества t : F’ = F’’, где F’ = F’ (x) и F’’ = F’’(x), мы получим тождество t~: F~’ = F~’’, где F~’ = F’ (F1, . . . , Fn) и F~’’ = F’’ (F1, . . . , Fn), которое называется подстановкой для тождества t.

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

Схема E’ называется подсхемой схемы E, если V(E’) [принадлежит] V(E), E(E’) [принадлежит] E(E) и любая вершина u, v [принадлежит] V (E’), которая либо относится к

множеству входов (выходов) E, либо служит конечной (соответственно, начальной) вершиной некоторого ребра из E(E)\E(E’), является входом (соответственно, выходом) E’.

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

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

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

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

a)

b)

c)

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

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

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

Тождество T` : E`’ ~ E`’’, которое получается в результате применения одной и той же подстановки к обеим частям тождества t : E’ ~ E’’, называется подстановкой тождества t.

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

Формулы, полученные в процессе индуктивного построения формулы F, называются

ее подформулами.

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

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

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

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

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

1. {обозначается tau в верхнем индексе ПК, в нижнем 0, &}x1&(x2&(!x2)) = x2&(!x2) {в СФЭ это нарисовать несложно… на бумаге}

b) Вершина СФЭ называется висячей, если она является стоком, но не является выходом схемы. {исходя из этого и нарисовать СФЭ с отдельным входом и без него}

c)

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

Схема называется разделительной по входам(выходам), если ФАЛ проводимости между любыми ее различными входами (соответственно выходами) равна 0.

Пусть КС E является результатом стыковки вида E = E’’ (E’), а F, F’ и F’’ — матрицы, реализуемые КС E, E’ и E’’ соответственно. Тогда F >= F’ · F’’ и F = F’ · F’’, если КС E’’ разделительна по входам или КС E’ разделительна по выходам.

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

Схемы E’ и E’’ считаются изоморфными, если изоморфны соответствующие им графы, и эквивалентными, если они реализуют равные системы ФАЛ. Изоморфные КС, очевидно, эквивалентны.

Определим подстановку для КС как переименование (с возможным отождествлением и инвертированием) БП, а также переименование (с возможным отождествлением и

снятием) полюсов.

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

Схема E’ называется подсхемой схемы E, если V(E’) [принадлежит] V(E), E(E’) [принадлежит] E(E) и любая вершина u, v [принадлежит] V (E’), которая либо относится к

множеству входов (выходов) E, либо служит конечной (соответственно, начальной) вершиной некоторого ребра из E(E)\E(E’), является входом (соответственно, выходом) E’.

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

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

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

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

1. (a|b)&c = a&c | b&c

2. {нарисовать схемку с висячим ФЭ отрицания и без него}

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

|E (G)| - |V (G)| + |c (G)| - цикломатическое число графа {E – ребра, V – вершины, C – компоненты связности}

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

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

переменных X (n).

2) ДНФ А назывется нерасширяемой, если расширение ДНФ А содержит ЭК, не являющуюся импликантой ни одной ЭК из A.

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

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

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

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

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

соответствуют ядровым граням этой ФАЛ.

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

Элементарная конъюнкция,которая имплицирует ФАЛ f, называется импликантой этой ФАЛ. Импликанта K ФАЛ f называется простой импликантой этой ФАЛ, если она не поглощается никакой другой отличной от нее импликантой ФАЛ f.

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

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

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

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

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

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

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