3 (С.А. Ложкин - Лекции по основам кибернетики (2017))

Московский государственный университетимени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиС. А. ЛожкинЛекции по основамкибернетикиВариант 2017 г. (гр. 320–328), глава 3Москва 2017ОглавлениеВведение43 Синтез и сложность управляющих систем7§1Задача синтеза. Простейшие методы синтезасхем на основе ДНФ и связанные с ними верхниеоценки сложности функций.

. . . . . . . . . . .7§2Нижние оценки сложности ФАЛ, реализациянекоторых ФАЛ и минимальность некоторыхсхем. . . . . . . . . . . . . . . . . . . . . . . . . . 13§3Разложение ФАЛ и операция суперпозиции схем.Корректность суперпозиции для некоторых типовсхем, разделительные контактные схемы и леммаШеннона. . . . . . . . . .

. . . . . . . . . . . . . 21§4Каскадные контактные схемы и схемы из функциональныхэлементов. Метод каскадов и примеры его применения.Метод Шеннона . . . . . . . . . . . . . . . . . . 30§5Нижние мощностные оценки функции Шеннона,их обобщение на случай синтеза схем для функцийиз специальных классов . . . . . .

. . . . . . . 41§6Дизъюнктивно-универсальные множествафункций. Асимптотически наилучшийметод О. Б. Лупанова для синтезасхем из функциональных элементовв базисе {&, ∨, ¬} . . . . . . . . . . . . . . . . . 472Оглавление§7§8§93Регулярные разбиения единичного куба и моделированиефункций переменными. Асимптотически наилучшийметод синтеза формул в базисе {&, ∨, ¬}. . . . 52Асимптотически наилучший метод синтеза контактныхсхем. Синтез схем для ФАЛ из некоторых классов 57Синтез схем для некоторых дешифраторов имультиплексоров.

Поведение функции Шеннонадля глубины ФАЛ. . . . . . . . . . . . . . . . . 64Литература70ВведениеКурс «Основы кибернетики» (ранее «Элементы кибернетики»), создателем и основным лектором которого былчл.-корр. РАН С. В. Яблонский, читается на факультетеВМК МГУ с первых лет его существования. В настоящеевремя он читается в 6–8 семестрах и является обязательнымдля всех бакалавров (интегрированных магистров) направления 01400 — «Прикладная математика и информатика».При этом объем и, в некоторой степени, программа курса«Основы кибернетики» варьируются в зависимости от профиля.Курс «Основы кибернетики» посвящен изложению теории дискретных управляющих систем, которая представляет собой часть дискретной математики и математическойкибернетики.

В ней разрабатываются и изучаются дискретные математические модели, описывающие функционирование и структуру сложных систем преобразования информации (интегральных схем, программ и т. п.). В основе этихмоделей лежат различные способы задания функционирования управляющих систем с помощью дискретных функцийи их структурная реализация в тех или иных классах графов (классах схем). При исследовании управляющих системставятся и решаются две основные задачи: задача анализаи задача синтеза.Задача анализа состоит в нахождении функционирования данной схемы, а задача синтеза — в построении схемы,имеющей (реализующей) заданное функционирование. Каждая из этих задач может рассматриваться либо как индивидуальная задача, и тогда ее решением является конкрет4Введение5ное функционирование (схема), либо как массовая задача,и тогда ее решением должен быть алгоритм нахожденияфункционирования (схемы). Задача синтеза имеет, как правило, множество решений, из которых выбирают решение,оптимальное по какому-либо критерию.

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

При этом задержка схемыхарактеризует время срабатывания СБИС или время выполнения программы на параллельных процессорах и т. п.Если задача синтеза решена в одной модели, можно пытаться перенести это решение в другие модели с помощьюструктурного моделирования. Кроме того, полученное решение можно «улучшить» с помощью эквивалентных преобразований. С другой стороны, если задача синтеза решенадля одних функций, можно пытаться «разбить» (декомпозировать) новую функцию на уже рассмотренные и построитьиз синтезированных для них схем схему для новой функциис помощью операции суперпозиции.Указанные выше задачи рассматриваются в лекциях длявсех основных классов схем (дизъюнктивные нормальныеформы, формулы и схемы из функциональных элементов,контактные схемы), а также для некоторых модификацийэтих классов.Первая глава посвящена различным вопросам представления функций алгебры логики с помощью таблиц и дизъюн-6Введениективных нормальных форм (минимизация дизъюнктивныхнормальных форм).Вторая глава содержит описание структуры и функционирования схем из основных классов управляющих систем,а также из некоторых классов, представляющих собой ихобобщения или модификации.

В ней устанавливаются верхние оценки числа схем различных типов, рассматриваютсянекоторые вопросы их структурного моделирования.Во второй главе изучаются также эквивалентные преобразования схем на основе тождеств во всех основных классах управляющих систем. Для каждого из них приводитсясистема «основных» тождеств, доказывается полнота этойсистемы и изучаются вопросы ее избыточности.В третьей главе подробно рассматривается задача синтеза управляющих систем, а также изучаются особенностиприменения операции суперпозиции в различных классахсхем. В ней приводится целый спектр методов синтеза схем(от простейших до асимптотически оптимальных), устанавливаются нижние мощностные оценки функций Шеннона иоценки сложности ряда конкретных функций, доказываетсяминимальность некоторых схем.В четвертой главе представлены некоторые вопросы надежности и контроля схем (построение теств для таблиц,синтез самокорректирующихся контактных схем).Глава 3Синтез и сложность управляющихсистем§1Задача синтеза.

Методы синтеза схем на основе ДНФ и связанные с ними верхние оценки сложности функций.В общем виде задача синтеза состоит в построении по заданной системе функций реализующей ее схемы, котораяпринадлежит заданному классу и на которой достигаетсяминимальное значение заданного функционала сложности.Частным случаем этой задачи является рассмотренная в §7главы 1 задача минимизации ДНФ. Дадим основные определения, связанные с задачей синтеза схем, и введем необходимые обозначения.Пусть U — один из введенных в главе 2 классов схем,который является полным в том смысле, что каждую систему ФАЛ F можно реализовать некоторой его схемой Σ,а Ψ — какой-либо функционал сложности схем класса U,то есть отображение U во множество неотрицательных действительных чисел. Будем считать, что функционал сложности Ψ обладает свойством монотонности, то есть Ψ (Σ) >Ψ (Σ0 ), если Σ, Σ0 ∈ U, и Σ0 получается из Σ в результатеудаления вершин или ребер (ср.с §7 гл.

1). Все введенные вглаве 2 функционалы сложности этим свойством обладают.Определим сложность Ψ (F ) системы ФАЛ F относительно78Введениефункционала Ψ в классе U как минимальное значение величины Ψ (Σ) на множестве тех схем Σ из U, которые реализуют F . При этом схема Σ, принадлежащая классу U, котораяреализует F и для которой Ψ (Σ) = Ψ (F ), называется минимальной схемой в классе U относительно функционала Ψ.В силу монотонности функционала Ψ, минимальная схемавсегда может быть найдена среди приведенных схем.Величину Ψ (F ), в том случае когда функционал Ψ совпадает с введенным в главе 2 функционалом L (D, R, и т. д.),будем называть сложностью (соответственно глубиной, рангом, и т.

д.) системы ФАЛ F . Введем функциюΨ (n) = max Ψ (f ) ,f ∈P2 (n)которая, обычно, называется функцией Шеннона для класса U относительно функционала сложности Ψ. В дальнейшем сложность системы ФАЛ F относительно функционаAла Ψ для любого из введенных классов вида UAБ (вида U )AAбудем обозначать через ΨБ (F ) (соответственно Ψ (F )), афункцию Шеннона для этого класса относительно Ψ — чеAрез ΨAБ (n) (соответственно Ψ (n)). В обозначениях классовΦUCБ , UБ , а также связанных с ними функционалов сложности и функций Шеннона, нижний индекс Б вида Б0 будем,как обычно, опускать.Отметим некоторые простейшие соотношения между введенными функциями. Очевидно, что для сложностей Ψ0 (F )и Ψ00 (F ) системы ФАЛ F относительно функционала Ψ вклассах схем U0 и U00 соответственно выполняется неравенствоΨ0 (F ) 6 Ψ00 (F ) ,если U0 ⊇ U00 .

В частности,ΦΨCБ (F ) 6 ΨБ (F ) ,ΨK (F ) 6 Ψπ (F )Введение9и т. д. Довольно часто выделение подклассов из основныхклассов схем происходит за счет наложения различных дополнительных свойств на рассматриваемые схемы. В частности, из класса КС выделяют π-схемы, КС, обладающиесвойствами разделительности, и. т. п.Заметим, что для сложности L (F ) системы ФАЛ F =(f1 , . . . , fm ) в любом из рассматриваемых классов схем выполняются неравенстваmax L (fi ) 6 L (F ) 616i6mmXL (f )i .i=1Задача синтеза допускает тривиальное решение, связанное с использованием переборного алгоритма, который, однако, имеет большую трудоемкость и практически не применим, если число БП больше 5.Для реализации произвольных ФАЛ и получения верхних оценок их сложности можно использовать другой простейший метод синтеза схем, основанный на моделированиисовершенной ДНФ.

На основе этого моделирования, в частности, доказывается следующее утверждение.Лемма 1.1. Для любой функции алгебры логики f (x1 , . . . , xn ),f 6= 0, существуют формула Ff , Ff ∈ UΦ , и π-схема Σf ,которые реализуют f и для которых справедливы неравенства:L (Ff ) 6 2n · |Nf | − 1,L (Σf ) 6 n |Nf | .(1.1)Следствие 1. В силу (1.1), с учетом того, что ФАЛ 0можно реализовать π-схемой сложности 2, а также формулой из UΦ , имеющей сложность 2, выполняются неравенстваLC (n) 6 LΦ (n) 6 n · 2n+1 − 1,LK (n) 6 Lπ (n) 6 n · 2n .10ВведениеСледствие 2. В силу следствия 1 и с учётом следствия 2из теоремы 2.1 главы 2 справедливо неравенствоD(n) 6 n + dlog ne + 2.Следующее утверждение доказывается моделированиемсовершенной ДНФ с использованием контактного дерева.Лемма 1.2.

Для любой ФАЛ f, f ∈ P2 (n) и f 6= 0, существуют π-схема Σf и формула Ff , Ff ∈ UΦ , которыереализуют f и для которых, наряду с (1.1), справедливытакже неравенства:L (Σf ) 6 2n + |Nf | − 2,L (Ff ) 6 2n+1 + |Nf | − 4.Доказательство. В качестве Σf можно взять π-схему, которая получается из (1, 2n )-КД порядка n от БП x1 , . .