Введение в дискретную математику - Яблонский С.В.
Скачать (прямая ссылка):
5=1 ^„+1 О^ко) = • ? ? I
причем каждая окрестность порядка в (к > 0) содержит по крайней мере одну точку, не входящую в окрестность порядка и — 1, если в < в0 — 1. Отсюда щ, < 2”.
Зафиксируем теперь параметр и и будем изучать по-крытие множества Лт> на основе сведений об ее окрестностях порядка и. Это изучение аналогично попыткам составления плана местности на основе сведений об участках местности, которые человек видит из определенных ее точек.
Наши рассмотрения мы начнем с примера, который пояснит смысл локального изучения покрытий. Пусть
к\ V • •. V А2.
— сокращенная д. п. ф. функции /, а
— покрытие (максимальными гранями) множества №1Г
ГЛ. 1. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ формы ззз
Определение. Грани N ко и ^ко называются связными, если существует такое и, что N 0е5ц
I *1/
Легко видеть, что множество всех граней одно-
значным образом разбивается на связные компоненты, т. е. на такие подмножества, в которых каждая пара граней связна, а грани из разных подмножеств не связны.
Возникает вопрос, как для произвольной грани 0 найти компоненту связности, которой она принадлежит.
Отметим конъюнкцию Ки и начнем просмотр конъюнкций в порядке их следования в сокращенной д. н. ф.
Если Лгд() е то отмечаем конъюнкцию К\,
если Nко , то конъюнкцию не отмечаем. Затем
переходим к К\- Конъюнкцию отмечаем тогда и только тогда, когда ^ содержит грани для отмеченных
конъюнкций, и т. д. В результате этого мы просмотрим всю сокращенную д. н. ф. и отметим некоторые конъюнкции. Затем начинаем просмотр сокращенной д. н. ф. повторно. Если при этом множество отмеченных конъюнкций возрастает, то начинаем следующий просмотр сокращенной д. н. ф., и т. д. Мы придем к случаю, когда очередной просмотр (а их меньше т) не увеличит множества отмеченных конъюнкций, тогда выбрасываем все неотмеченные конъюнкции и процесс заканчивается. Оставшееся множество конъюнкций и дает искомую компоненту связности.
Мы видим, что сначала идет изучение покрытия при помощи окрестностей 1-го порядка, и на основе него делаются отметки конъюнкций. Последнее означает, что каждая конъюнкция снабжается одной ячейкой памяти с двумя состояниями (отметки «нет» и отметка «есть»). Кроме того, нужна еще одна ячейка для выяснения, увеличивает ли очередной просмотр число отметок или нет.
В качестве второго параметра возьмем число V — число допустимых ячеек двоичной памяти для каждой конъюнкции. Фиксируем параметр V.
Теперь перейдем к описанию локальных алгоритмов *)' [6] над покрытиями максимальными гранями с параметрами и и п. Работа алгоритма разбивается на два этана.
*) Здесь мы даем несколько другой вариант этого донятая.
334
Ч. V. НЕКОТОРЫЕ ПРИЛОЖЕНИЯ К КИБЕРНЕТИКЕ
I. Изучение покрытия. В определенном порядке просматривают сокращенную д. н. ф. и на основе того, что попадает в окрестность 8и(№кв) конъюнкции Кт. е. части сокращенной д. н. ф. и информации, накопленной для конъюнкций из этой окрестности, вычисляют новые значения у® м ячеек памяти для К°. При этом требуется, чтобы это вычпслсппе выполнялось одинаково для любых двух д. д. ф., имеющих конъюнкцию К° и таких, что у них окрестности конъюнкции К0 совпадают и имеют одинаковые значения ячеек памяти для конъюнкций из данной окрестности (локальность накопления информации). При выполнении определенных требований процесс накопления информации оказывается «сходящимся» и тем самым может быть окопчеп. В этих случаях мы получаем финальную информацию, аадаваемую значениями ячеек памяти для конъюнкций из сокращенной д. п. ф.
II. Принятие решения. По вычисленным значениям ячеек памяти конъюнкций пз *5'и(Лгк0) определяют возможность удаления конъюнкции Кй. Эта процедура также осуществляется локальпым образом, т. е. одинакова для любых двух д. п. ф., содержащих К0, у которых окрестности К° совпадают и имеют одинаковые значения ячеек памяти для конъюнкций из этой окрестности.
Легко видеть, что сформулированный выше алгоритм для нахождения в сокращенной д. н. ф. компоненты связности, содержащей данную конъюнкцию К°у является локальным алгоритмом с параметрами и — 1, V = 1.
В дальнейшем будем предполагать, что / такова, что покрытие множества Лг/ совокупностью всех ее максимальных граней образует связную компоненту. В противном случае задача минимизации с использованием локальных алгоритмов решается независимо для каждой связной компоненты в отдельности.
Пусть ](х1, #„) обладает указанным свойством.
Нетрудно видеть, что существует локальный алгоритм с параметрами и = 1, у~2п, который позволяет строить минимальную д. н. ф.
I этап. Сопоставим взаимно однозначным образом наборы (аь а„) с числами из множества {1, 2, 2П):
(оС{, »• йл) < * I (®1» • * •) К„) •
Каждой конъюнкции, К0 из сокращенной д. н. ф. для /
ГЛ. 1. ДИЗЪЮНКТИВНЫЕ НОРМАЛЬНЫЕ ФОРМЫ
335
сопоставляем двоичный кортеж
(у!* уУ*
где уца1,'..,ан) “ 1 тогда и только тогда, когда К°{аъ ...
«п)= 1- Очевидно, (??* ?•?'?!«) бУДет «кодом» грани К°. Затем идет изучение покрытия при помощи окрестностей 1-го порядка, и иовые значения ^ > • ? ч Для
/С" вычисляются как покомпонентные дизъюнкции кортежей для данной окрестности. Этот процесс приведет к тому, что для каждой конъюнкции сокращенной д. а. ф. мы вычислим двоичпый кортеж и он будет одним и тем же для всех конъюнкций — «кодом» функции (например, столбцом, определяющим ее в таблице).
