OK_metodichka_part_2 (1132797)
Текст из файла
Московский государственный университетимени М. В. ЛомоносоваФакультет вычислительной математики и кибернетикиС. А. ЛожкинЛекции по основамкибернетики(вариант 2009 г., глава 2)Москва 2009ОглавлениеВведение42 Основные классы управляющих систем.
Оценкачисла схем, их структурные представления.Эквивалентные преобразования управляющихсистем7§1 Основные понятия из теории графов, сетей,схем. Свойства матриц достижимости сетей,оценка числа сетей . . . . . . . . . . . . . . . . 7§2 Представление формул с помощью деревьев,схемы из функциональных элементов. Оценкачисла формул и схем в базисе {&, ∨, ¬} . .
. . 15§3 Задача эквивалентных преобразований схем напримере формул. Оптимизация подобных формулпо глубине . . . . . . . . . . . . . . . . . . . . . 26§4 Полнота системы основных тождеств для эквивалентныхпреобразований формул базиса {&, ∨, ¬} . . . . 32§5 Эквивалентные преобразования схем из функциональныхэлементов и моделирование с их помощью формульныхпреобразований. Моделирование эквивалентныхпреобразований формул и схем в различныхбазисах, теорема перехода . . .
. . . . . . . . . 38§6 Контактные схемы и π-схемы, оценка их числа.Особенности функционирования многополюсныхсхем . . . . . . . . . . . . . . . . . . . . . . . . . 472Оглавление§7§8§93Эквивалентные преобразования контактныхсхем. Основные тождества, выводвспомогательных и обобщенных тождеств .
. . 59Полнота системы основных тождестви отсутствие конечной полной системытождеств в классе контактных схем . . . . . . . 69Операция суперпозиции и ее корректностьдля некоторых типов схем. Разделительныеконтактные схемы и лемма Шеннона . . . . . . 75Литература85ВведениеКурс «Основы кибернетики» (ранее «Элементы кибернетики»), создателем и основным лектором которого былчл.-корр. РАН С. В. Яблонский, читается на факультетеВМиК МГУ с первых лет его существования. В настоящеевремя он читается в 6–8 семестрах и является обязательнымдля всех студентов, обучающихся по специальности 01.02 —прикладная математика и информатика, а также бакалавров одноименного направления 510200 и направления 010400 —информационные технологии.
При этом объем и, в некоторой степени, программа курса «Основы кибернетики» варьируются в зависимости от специализации и направления.Курс «Основы кибернетики» посвящен изложению теории дискретных управляющих систем, которая представляет собой часть дискретной математики и математическойкибернетики. В ней разрабатываются и изучаются дискретные математические модели, описывающие функционирование и структуру сложных систем преобразования информации (интегральных схем, программ и т. п.). В основе этихмоделей лежат различные способы задания функционирования управляющих систем с помощью дискретных функцийи их структурная реализация в тех или иных классах графов (классах схем).
При исследовании управляющих системставятся и решаются две основные задачи: задача анализаи задача синтеза.Задача анализа состоит в нахождении функционирования данной схемы, а задача синтеза — в построении схемы,имеющей (реализующей) заданное функционирование. Каждая из этих задач может рассматриваться либо как инди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)).
Характеристики
Тип файла PDF
PDF-формат наиболее широко используется для просмотра любого типа файлов на любом устройстве. В него можно сохранить документ, таблицы, презентацию, текст, чертежи, вычисления, графики и всё остальное, что можно показать на экране любого устройства. Именно его лучше всего использовать для печати.
Например, если Вам нужно распечатать чертёж из автокада, Вы сохраните чертёж на флешку, но будет ли автокад в пункте печати? А если будет, то нужная версия с нужными библиотеками? Именно для этого и нужен формат PDF - в нём точно будет показано верно вне зависимости от того, в какой программе создали PDF-файл и есть ли нужная программа для его просмотра.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
