Схемы заданной функции

Основы схем из функциональных элементов. Проблема минимизации

К главе 4.

К главе 2.

Разное.

К главе 1.

Ответы

Упражнения.

1. Найти число ожерелий из пяти бусин трех цветов. Два ожерелья оди­наковы, если одно на другого можно получить циклической переста­новкой в плоскости.

2. Найти число раскрасок граней тетраэдра в четыре цвета. Два тетра­эдра одинаковы, если один иа них можно получить из другого враще­нием в пространстве.

3. Найти число раскрасок ребер тетраэдра в четыре цвета. Два тетра­эдра одинаковы, если один из другого можно получить вращениями в пространстве.

4. Найти число существенно различных булевых функций от трех пере­менных. Две функции одинаковы, если одну из другой можно получить переименованием переменных.

1) 2) 3) 4) . 5) . 6) 7) 8)8!=40320. 9) 5!=120. 10) 3 11)

12) 13) 14) =252.

15) 16) 17) .

18) . 19) . 20) .

21) 22) 23) 24) 25) 26) 27) . 28) Порядок существенен: 5! ; порядок не существенен: . 29) 30)

31) . 32) . 33) 34) 35)66660:3 (1111+2222+3333+4444). 36)33330. 37)11110. 38) 16665. 39) 12. 40) 864. 41) 2220. 42) 43) 44) 45)

46) 47) а)

1.

2.

3.

4. (6).

5.

6.

7.

8.

9.

10.

11. Ответ нужно поделить на 2.

1.

2.

3.

4.

5.

1.

2.

3.

4.

Пример. Рассмотрим базовые элементы: . Задача состоит в построении схемы из данных элементов, которая вычисляет функцию суммы двух элементов по модулю ().

Рассмотрим представление функции в виде СДНФ. Рассмотрим следующий функциональный граф, вершинам которого поставлены в соответствие логические элементы.

ar w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>">

Этот граф естественным образом вычисляет требуемую сумму . Каждая вершина совершает соответствующую ей логическую операцию. Таким образом, подавая на входы данной схемы определенные r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> значения , на выходе получим требуемую сумму по r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> .

Определение. Схемой из функциональных элементов называется последовательность элементов, где каждый элемент совершает определенную логическую операцию над результатами, ранее вычисленными операционными элементами.

Удобно графовое представление схемы из функциональных элементов. Рассмотрим ациклический ориентированный граф (ацикличность – отсутствие циклов).

В таком графе обязательно найдется хотябы одна вершина, в которой нет входящих ребер. Такую вершину назовем источником. Аналогично, в таком графе найдется хотябы одна вершина, в которой нет исходящих ребер. Такую вершину назовем стоком.

Причем, рассматривая ациклический граф, число входящих ребер в каждой вершине . Глубиной вершины в таком графе назовем длину максимального пути из источника к данной вершине. Если ребро в графе

, то глубина вершины меньше глубины вершины ().

Каждой вершине поставим в соответствие функциональный элемент . Если у вершины входящих ребра, то это r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> или r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> , как элементы с входами. Если у вершины входящее ребро, то поставим в соответствие . Источникам поставим в соответствие переменные . В результате получим схему из функциональных элементов. Каждой вершине схемы соответствует определенная логическая функция от входных переменных , которая определяется индукцией по глубине вершин в схеме. Для источников это соответствующие тождественные функции. Пусть мы определили функции всех вершин, глубина которых , тогда рассмотрим вершины, глубина которых ar w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> . Если вершине соответствует элемент r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> , а соответствуют входам элемента, то выходу этого элемента соответствует .

Если вершине соответствует элемент r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> , то получаем соответственно выход . если вершине соответствует элемент , то на выходе получаем отрицание входа.

Таким образом, каждая схема из функциональных элементов вычисляет набор функций от входных элементов , которые определены в стоках программы.

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

Определение. Сложностью логической функции будем называть следующую величину , где минимум берется по всем схемам, которые реализуют функцию , то есть минимальное число элементов “r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> ” “r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> ” “ ”, необходимое для реализации функции с помощью какой-либо схемы.

Определение. С ложностью класса функций K назовем величину

В дальнейшем нас будет интересовать сложность класса всех двоичных функций неболее чем от n:

Оценим сложность класса двоичных функций не более чем от переменных при больших n. Будем использовать следующие обозначения:

1) , если ;

2) если ;

3) , если (“≲” – ассимптотически не превосходит).

Оценим сложность сумматора двух двоичных чисел.

Входами сумматора являются разрядов входных двоичных чисел, а выходами ar w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> цифр , которые являются разрядами суммы. На рисунке показано подсхем блока, каждый блок соответствует вычислению определенного разряда суммы.

Входом i-ого блока являются входы -ых разрядов суммируемых чисел ( – вход -ого разряда -ого числа, – вход -ого разряда -ого числа), а также значение переносимого числа из предыдущего разряда. Выходом i-ого блока является значение двоичной суммы разрядов на входе , а также значение переносимого числа в очередной r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> разряд.

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

Отдельный блок зависит не более чем от -х входов и имеет выхода, тогда сложность реализации отдельного блока не более, чем const. Например, используя представление двоичной функции в виде СДНФ, выход определяется формулой:

Потребуется r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> операции конъюнкции (“r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> ”), т.к. в СДНФ слагаемых, в каждом слагаемом операция “r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> ” выполняется раза. Операций дизъюнкций (“r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> ”) потребуется и операций отрицания (“ ”). Общее число элементов для реализации -ого выхода: , .

Оценим сложность реализации . Для этого будем использовать представление в виде СДНФ. имеет единицы, поэтому в СДНФ будет слагаемых, тогда число используемых элементов “r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> ” равно , “r w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> ” – , “ ” – . Общее число элементов

, следовательно, суммарная сложность сумматора, построенного по СДНФ ar w:top="1134" w:right="850" w:bottom="1134" w:left="1701" w:header="720" w:footer="720" w:gutter="0"/><w:cols w:space="720"/></w:sectPr></w:body></w:wordDocument>"> .

Оценим сложность двоичной функции не более чем от переменных.

При построении схемы, реализуем двоичную функцию не более чем от переменнх. Будем использовать следующие схемы:

Дата добавления: 2017-01-13