test3 - answers (1133102)

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

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

Тест 3. Ответы.

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

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

Простейшей π-схемой считается любая (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 схемы У помечена ФС [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)

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

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

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

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

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

Схема 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.

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

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

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

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

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

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