АЛГОРИТМ ЛОКАЛЬНЫЙ

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

В некоторых задачах для вводят счетную систему окрестностей Пусть, напр., семейство мн-в , составленных элементарных конъюнкций, входящих в сокращенную дизъюнктивную нормальную форму (ДНФ) ф-ции Окрестностью назовем совокупность всех конъюнкций из , таких, что соответствующие им интервалы имеют непустое пересечение с интервалом соответствующим конъюнкции .

Пусть определена окрестность порядка конъюнкции в Окрестностью порядка в. ; назовем совокупность всех из , для которых выполнено одно из двух условий:

1) непусто, и ,

2) интервал, соответствующий содержится в сумме интервалов, каждому из которых соответствует конъюнкция из , удовлетворяющая условию 1). Нетрудно ввести и окрестности для вершин и ребер графа. Будем считать, что на парах определена система двухместных предикатов , которая разбита на два непересекающихся подмножества Элементы первого подмножества назовем основными предикатами, второго — вспомогательными предикатами.

Вектор информационным, если Вектора наз. допустимым для в , если для всех

выполнено равенство . Мн-во всех информационных векторов, допустимых для в , наз. информационным мн-вом в .

Пусть назовем допустимыми для ЗЛ.

Класс всех допустимых для ЗЛ мн-в ЗЛ назовем информационным классом мн-ва ЗЛ по системе предикатов

Очевидно, окрестность определяет окрестность ЭЛ. Введем систему ф-ций

Ф-ции определены на всех парах

ЗЛ) таких, что и удовлетворяют следующим условиям:

1) , если 2) мн-во , которое получается из ЗЛ заменой элемента на , допустимо для Для краткости пары будем обозначать .

Введем частичную упорядоченность в некоторых мн-вах (см. Частично упорядоченное множество):

1)

2) - мн-во информационных векторов длины если

3) Мн-во элементов с отметками: если

4) Мн-во если, во-первых, принадлежат одному информационному классу , и, во-вторых, если то

5) Мн-во окрестностей если а из условий следует, что

Пусть А и В — элементы одного из

Если и то элементы А и В назовем равными по информации и обозначим . Ф-цию назовем монотонной, если из соотношения следует, что

Для определения А. необходимо также ввести алгоритм упорядочивания АП и А — оператор по системе предикатов. Пусть М — произвольное мн-во, составленное из элементов с информационными векторами

Рассмотрим мн-во всех пар таких, что Алгоритм упорядочивает мн-во — оператор по системе над ЗЛ заменяет в информационных векторах всех элементов из ЗЛ значения всех координат, кроме координат с номерами на А. Обозначают его А.

Алгоритм А полностью определяется системой предикатов Рразбиением этой системы на основные и вспомогательные ; предикаты, системой монотонных ф-ций и алгоритмом

Пусть .

Опишем первый шаг алгоритма. К мн-ву применим алгоритм

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

Пусть выполнено шагов алгоритма А. Описание шага в точности повторяет описание первого шага, если вместо мн-ва. ЗЛ рассматривать мн-во ЗЛП, в которое перешло ЗЛ после первых шагов алгоритма А. В силу монотонности алгоритм закончится после конечного числа шагов.

Исходными теоремами теории А. являются теорема единственности и теорема существования наилучшего алгоритма. Первая теорема утверждает, что результат вычислений осн. предикатов А. не зависит от алгоритма прохода элементов мн-ва . Вторая теорема утверждает существование в весьма общих предположениях наилучшего А. т. е. алгоритма, который по заданной фиксированной системе окрестностей вычисляет заданные осн. предикаты при фиксированных, вспомогательных предикатах всегда, когда это делает любой другой алгоритм. Эта теорема носит характер теоремы существования, т. е. прямое построение наилучшего алгоритма с использованием доказательства затруднено. Естественно поэтому попытаться

получить наилучший алгоритм в явной форме. Эта задача решена лишь для отдельных случаев. Примером может быть задача построения миним. покрытий мн-ва М системой Если в качестве основных предикатов рассмотреть не входит ни в одно миним. покрытие М мн-вами из числа входит во все миним. покрытия М мн-вами из числа , то при пустом мн-ве вспомогательных предикатов удается построить А. л. вычисления Решена задача вычисления свойства ребра графа входить или не входить в какой-либо тупиковый путь между двумя полюсами: построен наилучший А. л. Построены также А. л. для задач упрощения ДНФ. Эти алгоритмы вычисляют свойство элементарной конъюнкции входить или не входить в дизъюнктивную нормальную форму минимальную по окрестностям первого, второго или третьего порядка. Доказана невычислимость в классе А. л. свойства элементарной конъюнкции входить в минимальную ДНФ булевой функции? Точнее, если число предикатов, участвующих в определении А. л., равно I, а порядок (индекс) окрестности равен к, то при к существует булева ф-ция для которой о всякой элементарной конъюнкции, входящей в сокращенную ДНФ, алгоритм с параметрами к, I «не узнает», входит она в минимальную ДНФ или нет. При этом накладываются довольно нежесткие ограничения на вид предикатов Исследована вычислимость всех предикатов, связанных с задачей минимизации булевых ф-ций.

Лит.: Журавлев Ю. И. Теоретико-множественные методы в алгебре логики. «Проблемы кибернетики», 1962, в. 8; Журавлев Ю. И. Оценки сложности алгоритмов построения минимальных дизъюнктивных нормальных форм для функций алгебры логики. «Дискретный анализ», 1964, в. 3; Журавлев Ю. И. Локальные алгоритмы вычисления информации. «Кибернетика», 1965, 1; 1966, 2; Андон Ф. И. Алгоритм упрощения д. н. ф. булевых функций. «Кибернетика», 1966, ; Евдокимов А. А. О максимальной длине цепи в единичном -мерном кубе. «Математические заметки», 1969, т. 6, в. 3; Хуторянская И. В. Некоторые вопросы теории локальных алгоритмов на графах. «Кибернетика», 1971, Кн 1. ГО. И. Журавлев.