Научная литература
booksshare.net -> Добавить материал -> Математика -> Яблонский С.В. -> "Введение в дискретную математику " -> 91

Введение в дискретную математику - Яблонский С.В.

Яблонский С.В. Введение в дискретную математику — Наука , 1986. — 384 c.
Скачать (прямая ссылка): vvedenievdiskretnuyum1986.djvu
Предыдущая << 1 .. 85 86 87 88 89 90 < 91 > 92 93 94 95 96 97 .. 104 >> Следующая

II этап. Решающее правило определим так: возьмем произвольную минимальную д. н. ф. для / и данную конъюнкцию выбрасываем тогда и только тогда, когда она не входит в минимальную д. н. ф. Очевидно, данное решающее правило удовлетворяет требованию локальности и приводит нас к минимальпой д. н. ф.
Данное обстоятельство означает, что в локальных’ алгоритмах необходимо вводить ограничения на объем допустимой памяти V.
Б заключение этого параграфа покажем, что алгоритм Кваина и алгоритм построения д. н. ф. тина 2Т являются локальными и произведем оценку их параметров.
Б алгоритме Квайна сначала выявляются ядровые конъюнкции. Для этого необходимо знать окрестности первого порядка конъюнкция в сокращенной д. н. ф., и запоминать отметки: если конъюнкция не ядровая, то отметка 0, если — ядровая, то отметка 1. Для принятия решения о возможности удаления конъюнкции надо опять знать ее окрестность первого порядка и посмотреть, покрывается ли она отмеченными конъюнкциями из этой окрестности. Таким образом, мы имеем локальный алгоритм с параметрами и = 1, V 1.
В алгоритме построения д. н. ф. типа 2Т сначала определяют, является ли данная конъюнкция регулярной. Для этого нужно сравнивать пучки, проходящие через точки данной грани (конъюнкции) и пучки, проходящие через точки из окрестности 1-го порядка данной грани и не лежащие в ней, т. е. оперировать с окрестностями 2-го порядка. Регулярная грань помечается символом 1,
838
Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКИ
грапь, не являющаяся регулярной,— 0. Затем происходит принятие решения: удаляются грани с пометкой 1 (регулярные) . Итак, в этйм случае мы имеем локальный алгоритм с параметрами и = 2 и V ~ 1.
На основании обсуждений мы видим, что локальные алгоритмы охватывают многие известные классы алгоритмов. С другой стороны, локальные алгоритмы с параметрами и в V являются алгоритмами с ограниченной трудоемкостью.
Глава 2 СЙНТЕЗ СХЕМ
ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ
В современной технике управляющих и вычислительных устройств важное место занимают дискретные преобразователи, т. е. устройства (см. рис. 1), которые обладают некоторым числом входов и выходов. Наборы
сигналов, поступающие на входы
и возникающие на выходах, при-: надлежат известным конечным
*~Х/> множествам. Устройства осуще-
Рис. 1 ствляют преобразования входных
наборов сигналов в выходные. Интересным подклассом дискретных преобразователей является класс устройств, в которых время преобразования существенно малб по сравнению с длительностью сигналов (или устройства, временем преобразования в которых можно пренебречь). Математической моделью таких устройств являются так называемые схемы из функциональных элементов.
§ 1. Понятие схемы из функциональных элементов
Определение понятия схемы из функциональных элементов (Ф. Э.) можно разбить на два этапа. На первом этапе раскрывается структурная (схемная) част* этого понятия, на втором — функциональная.
I этап. Определение схемы из функциональных элементов с точки зрения ее структуры. Этот этап, в свою очередь, разбивается па ряд пунктов.
Iе. Имеется конечное множество Р объектов Л (I — 1, г), называемых злементами. Каждый эле-
ГЛ. 2. СИНТЕЗ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ 337
мент имеет п, входов и один выход. Элемент графически изображается так, кйК' указано на рис. 2.
2°. Исходя из элементов, по индукции определяем понятие логической сети (геометрическое определение). Логическая сеть 2 будет определяться как объект (см. рис. 3), в котором имеется некоторое чпсло п входов и некоторое число р выходов.
а) Базис индукции.
Одна изолированная вершина называется (тривиальной) логической сетью. По определению, она является одновременно входом п выходом (см. рис. 4). Здесь и далее
на рисунках входящая стрелка обозначает вход, исходящая стрелка — выход.
б) Индуктивный переход. Эта часть основана на использовании трех операций.
1°. Операция объединения
Рис. 2
Р
Рис. 3
^ Входы Выходы
Рис. 4
лцлхся сетей. Пусть 2' и 2' — две
о
непересекаю-
непересекающиеся
и
Рис. 5
Рис. 6
сети (без общих элементов, входов и выходов), имеющие соответственно п п тп входов И р И б/ выходов (см. рис. 5). Теоретико-множествеипое объединение двух непересекаю-щихся логических сетей 2' и 2” есть логическая сеть 21, входами которой являются все входы сетей 2Л и 2% выходами — все выходы сетей 2' и 2". Сеть 2! имеет п + т входов и р + $ выходов (см. рис. 6).
II0. Операция присоединения элемента Р1ш Пусть логическая сеть. Ж и элемент; ^ (рис. 7) таковы, что щ<р ив 2' выбрано щ попарно различных выходов
22 с. в. Яблонский
338 Ч. V. НЕКОТОРЫЕ ПРИ ЛОЖЕШІК К КП ПЕРНЕТ IIКЕ
с номерами 7 ц /2,../п..Тогда фигура 2а называется логической сетью, являющейся результатом подключения элемента Fi к логической сети 2'. Входами 22 являются все входы 2', выходами — все выходы сети 2', кроме выходов с номерами /ц ../П{, а также выход элемента /+ Логическая сеть 2а имеет гг входов и р — п{ + 1 выходов.
ПГ. Операция расщепления выход а. Пусть в логической сети 2' (рис. 8) выделен выход с
Предыдущая << 1 .. 85 86 87 88 89 90 < 91 > 92 93 94 95 96 97 .. 104 >> Следующая

Реклама

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed

Есть, чем поделиться? Отправьте
материал
нам
Авторские права © 2009 BooksShare.
Все права защищены.
Rambler's Top100

c1c0fc952cf0704ad12d6af2ad3bf47e03017fed