test all (1133098)

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

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

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

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

Простейшей π-схемой считается любая (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) Определение ДНФ сумма тупиковых.

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

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

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

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

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

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