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

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

. . . . . . 6§2 Метод каскадов для контактных схем исхем из функциональных элементов.Метод Шеннона . . . . . . . . . . . . . . . . . . 15§3 Регулярные разбиения единичного куба и моделированиефункций переменными. Асимптотика сложностиконтактного дешифратора . . . . . . . . . . . . 26§4 Операция суперпозиции и ее корректностьдля некоторых типов схем.

Разделительныеконтактные схемы, лемма Шеннона . . . . . . . 31§5 Нижние мощностные оценкифункций Шеннона . . . . . . . . . . . . . . . . . 40§6 Дизъюнктивно-универсальные множествафункций. Асимптотически наилучшийметод О. Б. Лупанова для синтезасхем из функциональных элементовв базисе {&, ∨, ¬} . . . . . . .

. . . . . . . . . . 45§7 Асимптотически наилучший метод синтезаконтактных схем . . . . . . . . . . . . . . . . . . 50Литература572ВведениеКурс «Основы кибернетики» (ранее «Элементы кибернетики»), создателем и основным лектором которого былчл.-корр. РАН С. В. Яблонский, читается на факультетеВМиК МГУ с первых лет его существования. В настоящеевремя он читается в 6–8 семестрах и является обязательнымдля всех студентов, обучающихся по специальности 01.02 —прикладная математика и информатика, а также бакалавров одноименного направления 510200 и направления 010400 —информационные технологии.

При этом объем и, в некоторой степени, программа курса «Основы кибернетики» варьируются в зависимости от специализации и направления.Курс «Основы кибернетики» посвящен изложению теории дискретных управляющих систем, которая представляет собой часть дискретной математики и математическойкибернетики. В ней разрабатываются и изучаются дискретные математические модели, описывающие функционирование и структуру сложных систем преобразования информации (интегральных схем, программ и т.

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

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

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

В ней устанавливаются верхние оценки числа схем различных типов, рассматриваютсяособенности применения операции суперпозиции в различных классах схем и некоторые вопросы их структурного моделирования.Во второй главе изучаются также эквивалентные преобразования схем на основе тождеств во всех основных классах управляющих систем. Для каждого из них приводитсясистема «основных» тождеств, доказывается полнота этойсистемы и изучаются вопросы ее избыточности.В третьей главе подробно рассматривается задача синтеза управляющих систем.

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

Простейшие методы синтезасхем и оценки сложности функцийВ общем виде задача синтеза состоит в построении по заданной системе функций реализующей ее схемы, котораяпринадлежит заданному классу и на которой достигаетсяминимальное значение заданного функционала сложности.Частным случаем этой задачи является рассмотренная в §7главы 1 задача минимизации ДНФ.

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

Определим сложность Ψ (F ) системы ФАЛ F относительно функционала Ψ в классе U как минимальное значение величины6§1. Задача синтеза7Ψ (Σ) на множестве тех схем Σ из 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 .