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

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

. . . . . . . . . . . . . . . 6§2 Формулы, их структура, эквивалентность и способызадания. Оптимизация подобных формул поглубине . . . . . . . . . . . . . . . . . . . . . . . 15§3 Схемы из функциональных элементов. Оценкачисла формул и схем в базисе {&, ∨, ¬} . . . . 24§4 Контактные схемы и π-схемы, оценка их числа.Особенности функционирования многополюсныхсхем . . . . .

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

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

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

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

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

Некоторые модели иклассы схем, связанные спрограммно-аппаратной реализациейалгоритмов§1Основные понятия из теории графов, сетей,схем. Свойства матриц достижимости сетей,оценка числа сетейПонятие графа, которое обобщает понятие бинарного отношения (см. §1 главы 1), часто используется для описанияструктурных моделей, связанных с вычислениями, представлениями или реализациями дискретных функций. Напомним основные понятия и обозначения из теории графов, сетей и схем, а также сформулируем некоторые известные результаты (см., например, [3, 27, 8]).Пару (V, E), где E — сочетание (с возможными повторениями) над множеством упорядоченных и неупорядоченныхпар из V , будем, как обычно, называть графом с множеством вершин V = V (G) и множеством ребер E = E (G).При этом длина сочетания E считается числом ребер графаG и обозначается через |E|.

Упорядоченные (неупорядоченные) пары вершин называются ориентированными ребра6§1. Основные понятия из теории графов, сетей, схем.7ми или, иначе, дугами (соответственно неориентированными ребрами), одинаковые пары — параллельными ребрами(дугами), дуги, отличающиеся порядком вершин, — противоположными дугами, а пары из совпадающих вершин —петлями. Граф из ориентированных (неориентированных)ребер считается ориентированным (соответственно неориентированным). Заметим, что бинарное отношение представляет собой ориентированный граф без параллельныхдуг.

При этом симметричное антирефлексивное отношениеможно рассматривать как неориентированный граф без параллельных ребер и петель.Будем говорить, что ориентированное (неориентированное) ребро инцидентно составляющим его вершинам, а дуга(u, v) исходит или, иначе, выходит из вершины u и заходитили, иначе, входит в вершину v. Число ребер, инцидентныхвершине v (входящих в v, выходящих из v) в графе G, называется степенью (соответственно полустепенью захода,полустепенью исхода) вершины v в графе G и обозначается−через dG (v) (соответственно d+G (v), dG (v)).

Заметим, чтоXdG (v) = 2 |E (G)| ,(1.1)v∈V (G)−−+и что dG (v) = d+G (v)+dG (v) (dG (v) = dG (v) = dG (v)) в случае ориентированного (соответственно неориентированного)графа G.Вершина v называется изолированной вершиной (стоком, истоком) графа G, если dG (v) = 0 (соответственно+d−G (v) = 0, dG (v) = 0). Ориентированный граф G называется r-ичным (строго r-ичным) графом, если d+G (v) 6 r+(соответственно dG (v) = r) для любой отличной от истокавершины v, v ∈ V (G).Граф G0 = (V 0 , E 0 ) называется подграфом графа G == (V, E), если V 0 ⊆ V и E 0 ⊆ E. При этом G0 считается подграфом графа G, натянутым на множество вершин8Глава 2.

Основные классы управляющих системV 0 , если E 0 включает в себя все входящие в E пары вершин из V 0 . Подграф, содержащий все вершины исходногографа, называется его остовным подграфом. Легко видеть,что подграф всегда можно получить из исходного графа врезультате (многократного) применения операций удаленияребра или удаления вершины. При этом удаление вершины,как обычно, подразумевает удаление всех инцидентных ейребер.При определении понятий, связанных с «движениями»по графу, ограничимся случаем ориентированных графов,считая, как обычно, что неориентированное ребро эквивалентно двум противоположным дугам, связанным с той жепарой вершин. Последовательность C, состоящая из реберe1 , e2 , .

. . , en , где ei = (vi , vi+1 ) ∈ E (G) при всех i, i ∈ [1, n],называется (v1 − vn+1 )-путем графа G. При этом вершина v1 (vn+1 ) считается начальной (соответственно конечной)вершиной этого пути, вершины v2 , . . . , vn — его внутренними вершинами, а число n — его длиной. Если все ребра пути различны (как элементы соответствующего сочетания),то он называется цепью, а если, кроме того, различны всеего вершины, то — простой цепью. Если начальная и конечная вершины пути (цепи) C совпадают, то C считаетсязамкнутым путем (соответственно циклом).