ОК_Часть_2_2015_(320-328)_v03-09 (1132806)
Текст из файла
Московский государственный университетимени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиС. А. ЛожкинЛекции по основамкибернетикиВариант 2015 г. (гр. 320–328), глава 2Москва 2015ОглавлениеВведение42 Основные классы управляющих систем. Оценкачисла схем, их структурные представления.Эквивалентные преобразования управляющихсистем7§1 Основные понятия из теории графов, сетей,схем. Свойства матриц достижимости сетей,оценка числа сетей .
. . . . . . . . . . . . . . . 7§2 Формулы, их структура, эквивалентность и способызадания. Оптимизация подобных формул поглубине . . . . . . . . . . . . . . . . . . . . . . . 16§3 Задача эквивалентных преобразований схем напримере формул. Полнота системы основныхтождеств для эквивалентных преобразованийформул базиса {&, ∨, ¬} .
. . . . . . . . . . . . 25§4 Схемы из функциональных элементов. Оценкачисла формул и схем в базисе {&, ∨, ¬} . . . . 32§5 Эквивалентные преобразования схем из функциональныхэлементов и моделирование с их помощью формульныхпреобразований. Моделирование эквивалентныхпреобразований формул и схем в различныхбазисах, теорема перехода . . . . . . . . . . .
. 40§6 Контактные схемы и π-схемы, оценка их числа.Особенности функционирования многополюсныхсхем . . . . . . . . . . . . . . . . . . . . . . . . . 492Оглавление§7§83Эквивалентные преобразования контактныхсхем. Основные тождества, выводвспомогательных и обобщенных тождеств . . . 61Полнота системы основных тождестви отсутствие конечной полной системытождеств в классе контактных схем . . . .
. . . 71Литература78ВведениеКурс «Основы кибернетики» (ранее «Элементы кибернетики»), создателем и основным лектором которого былчл.-корр. РАН С. В. Яблонский, читается на факультетеВМК МГУ с первых лет его существования. В настоящеевремя он читается в 6–8 семестрах и является обязательнымдля всех бакалавров (интегрированных магистров) направления 01400 — «Прикладная математика и информатика».При этом объем и, в некоторой степени, программа курса«Основы кибернетики» варьируются в зависимости от профиля.Курс «Основы кибернетики» посвящен изложению теории дискретных управляющих систем, которая представляет собой часть дискретной математики и математическойкибернетики.
В ней разрабатываются и изучаются дискретные математические модели, описывающие функционирование и структуру сложных систем преобразования информации (интегральных схем, программ и т. п.). В основе этихмоделей лежат различные способы задания функционирования управляющих систем с помощью дискретных функцийи их структурная реализация в тех или иных классах графов (классах схем). При исследовании управляющих системставятся и решаются две основные задачи: задача анализаи задача синтеза.Задача анализа состоит в нахождении функционирования данной схемы, а задача синтеза — в построении схемы,имеющей (реализующей) заданное функционирование. Каждая из этих задач может рассматриваться либо как индивидуальная задача, и тогда ее решением является конкрет4Введение5ное функционирование (схема), либо как массовая задача,и тогда ее решением должен быть алгоритм нахожденияфункционирования (схемы).
Задача синтеза имеет, как правило, множество решений, из которых выбирают решение,оптимальное по какому-либо критерию. Чаще всего в качестве такого критерия выступает сложность схемы, понимаемая как сумма сложностей составляющих ее элементовили задержка схемы, понимаемая как максимальная сумма задержек для последовательно соединенных элементовсхемы.С содержательной точки зрения различные критерии оптимальности отражают различные параметры моделируемых электронных схем или программ.
Так, например, сложность может характеризовать стоимость, размеры или потребляемую мощность СБИС, а также время выполненияпрограммы на одном процессоре. При этом задержка схемыхарактеризует время срабатывания СБИС или время выполнения программы на параллельных процессорах и т. п.Если задача синтеза решена в одной модели, можно пытаться перенести это решение в другие модели с помощьюструктурного моделирования.
Кроме того, полученное решение можно «улучшить» с помощью эквивалентных преобразований. С другой стороны, если задача синтеза решенадля одних функций, можно пытаться «разбить» (декомпозировать) новую функцию на уже рассмотренные и построитьиз синтезированных для них схем схему для новой функциис помощью операции суперпозиции.Указанные выше задачи рассматриваются в лекциях длявсех основных классов схем (дизъюнктивные нормальныеформы, формулы и схемы из функциональных элементов,контактные схемы), а также для некоторых модификацийэтих классов.Первая глава посвящена различным вопросам представления функций алгебры логики с помощью таблиц и дизъюн-6Введениективных нормальных форм (минимизация дизъюнктивныхнормальных форм).Вторая глава содержит описание структуры и функционирования схем из основных классов управляющих систем,а также из некоторых классов, представляющих собой ихобобщения или модификации.
В ней устанавливаются верхние оценки числа схем различных типов, рассматриваютсянекоторые вопросы их структурного моделирования.Во второй главе изучаются также эквивалентные преобразования схем на основе тождеств во всех основных классах управляющих систем. Для каждого из них приводитсясистема «основных» тождеств, доказывается полнота этойсистемы и изучаются вопросы ее избыточности.В третьей главе подробно рассматривается задача синтеза управляющих систем, а также изучаются особенностиприменения операции суперпозиции в различных классахсхем. В ней приводится целый спектр методов синтеза схем(от простейших до асимптотически оптимальных), устанавливаются нижние мощностные оценки функций Шеннона иоценки сложности ряда конкретных функций, доказываетсяминимальность некоторых схем.В четвертой главе представлены некоторые вопросы надежности и контроля схем (построение теств для таблиц,синтез самокорректирующихся контактных схем).Глава 2Основные классы управляющих систем.Оценка числа схем, их структурныепредставления.
Эквивалентныепреобразования управляющих систем§1Основные понятия из теории графов, сетей,схем. Свойства матриц достижимости сетей,оценка числа сетейПонятие графа, которое обобщает понятие бинарного отношения (см. §1 главы 1), часто используется для описанияструктурных моделей, связанных с вычислениями, представлениями или реализациями дискретных функций.
Напомним основные понятия и обозначения из теории графов, сетей и схем, а также сформулируем некоторые известные результаты (см., например, [3, 27, 8]).Пару (V, E), где E — сочетание (с возможными повторениями) над множеством упорядоченных и неупорядоченныхпар из V , будем, как обычно, называть графом с множеством вершин V = V (G) и множеством ребер E = E (G).При этом длина сочетания E считается числом ребер графаG и обозначается через |E|. Упорядоченные (неупорядоченные) пары вершин называются ориентированными ребрами или, иначе, дугами (соответственно неориентированными ребрами), одинаковые пары — параллельными ребрами(дугами), дуги, отличающиеся порядком вершин, — проти78Глава 2.
Основные классы управляющих системвоположными дугами, а пары из совпадающих вершин —петлями. Граф из ориентированных (неориентированных)ребер считается ориентированным (соответственно неориентированным). Заметим, что бинарное отношение представляет собой ориентированный граф без параллельныхдуг. При этом симметричное антирефлексивное отношениеможно рассматривать как неориентированный граф без параллельных ребер и петель.Будем говорить, что ориентированное (неориентированное) ребро инцидентно составляющим его вершинам, а дуга(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(соответственно d+(v)=r)длялюбойотличнойотистокаGвершины v, v ∈ V (G).Граф G0 = (V 0 , E 0 ) называется подграфом графа G == (V, E), если V 0 ⊆ V и E 0 ⊆ E. При этом G0 считается подграфом графа G, натянутым на множество вершинV 0 , если E 0 включает в себя все входящие в E пары вершин из V 0 . Подграф, содержащий все вершины исходного§1.
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
