Дискретно-непрерывная математика (стр. 101 )

(3.68)

Положим в (3.68) п равными последовательно 1, 2,...,n —1и просум­мируем все полученные равенства:

После приведения подобных в левой и суммирования в правой частях найдем с учетом очевидного начального условия N(1) =0 (ЛО с одним

элементом не надо вычислять)

(3.69)

Итак, сложность вычисления семейства ЛО-столбцов по разложению (3.61) растет как квадрат числа элементов ЛО, что во многих случаях приемлемо.

3.8. Вычисление логических определителей методом упорядочения

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

(3.70)

Для упорядочения множества Аn используем итеративный метод вставок. Он основан на том, что если множество Ап уже упорядочено, то для упо­рядочения нового множества полученного добавле­нием в Ап нового элемента ап+1, достаточно вставить этот новый элемент в нужное место между элементами упорядоченного множества Аn. Это место находится так. Сначала an + 1 сравнивается с центральным элементом множества Ап. Этим устанавливается, в какой из двух половин Ап должен находиться ап + 1: если то во второй половине, еслито в первой. Далее ап+1 сравнивается с центральным элементом "подозрительной" половины и т. д. Сложность процедуры упо­рядочения составляет

(3.71)

двухместных операций сравнения, что заметно меньше сложности всех других изложенных ранее процедур вычисления ЛО.

3.9. Вычисление асимптотики выражения (3.1)

Выведем оценки (3.3), (3.4). По формуле Стерлинга при больших п и фиксированных r получим

Но

так что

(3.72)

Подставив выражение (3.72) в (3.1), придем к оценке (3.3). Далее при больших n, r и n-r.

Обозначив s = п/r, получим

п = rs, так что

Таким образом,

(3.73)

Подставив выражение (3.73) в (3.1), получим оценку (3.4).

Проблема сложности вычисления больших ЛО была сформулирована в связи с задачей поиска информации в больших массивах. Были приведены простейшие оценки сложности. Подробные оценки слож­ности вычисления ЛО по готовым формулам раскрытия и по формулам разложения были даны позднее при изучении динамики сложных цифровых автоматов. Эти оценки выявили случаи как приемлемости, так и неприемлемости по сложности точных методов вычисления ЛО, что сделало целесообразной разработку приближенных методов, а также специальных методов вычисления семейств ЛО.

4. ЛОГИЧЕСКИЕ ОПРЕДЕЛИТЕЛИ С ОГРАНИЧЕНИЯМИ НА СУММЫ ЭЛЕМЕНТОВ

4.1. Вводные замечания

Порядковые логические определители (ЛО), введенные в гл. 2, не являются единственным классом блочных конструкций, предназначенных для упрощения анализа высокоразмерных нелинейных систем. Опыт изу­чения таких систем показывает, что рассмотрение каждого нового класса систем приводит обычно к необходимости введения нового класса ЛО, предназначенного для решения проблемы размерности именно в рассмат­риваемом случае.

В этой главе рассмотрен большой класс ЛО, которые вводятся как та или иная экстремальная характеристика прямоугольной матрицы, точнее, как максимальная (минимальная) из сумм элементов матрицы, удовлет­воряющих некоторому ограничению. ЛО с ограничениями, в отличие от порядковых ЛО, выражаются через свои элементы при помощи двух типов операций. 1) дизъюнкции и конъюнкции БЛ;

2) алгебраического сложе­ния. Рассматриваемые ЛО с ограничениями позволяют решать проблему размерности при изучении тех систем, все возможные варианты действия которых задаются прямоугольной матрицей, причем выбор какого-то од­ного варианта сводится к выбору одной из сумм элементов матрицы, удовлетворяющих заданному ограничению, а выбор наилучшего вариан­та - к отысканию максимальной (минимальной) из сумм.

4.2. Логические определители первого рода и их свойства

Рассмотрим произвольную прямоугольную матрицу

(4.1)

с числовыми элементами Будем оперировать суммами элементов

удовлетворяющими ограничению каждая включает ровно по одному элементу из каждого столбца А. При этом из одной строки в сумму может включаться любое число элементов: 0, 1,..., Р. Общее число раз­личных сумм равно Мр. Обозначим q-ю сумму через

Определение 4.1. Будем называть ЛО с ограничениями первого рода для матрицы А выражения вида

(4.2)

(4.3)

т. е. дизъюнкцию (конъюнкцию) БЛ всех сумм элементов А, содержащих каждая ровно один элемент из каждого столбца А.

Любая матрица А всегда имеет непустое множество сумм

а отсюда — и ЛО

Ниже изучается в основном дизъюнктивный ЛО (4.2). Однако, так как операции дизъюнкции и конъюнкции БЛ подчиняются одним и тем же законам (1.9) — (1.12), (1.14), все получаемые результаты верны и для конъюнктивного ЛО (4.3), если заменить в них операции

Свойства введенных ЛО определяются следующими предложениями.

Лемма 4.1. Перестановка местами двух строк не меняет величины ЛО:

(4.4)

Доказательство следует из того, что при указанной перестановке мно­жество суммфигурирующее в определении ЛО (4.2), остается неизменным.

Лемма 4.2. Перестановка местами двух столбцов не меняет величи­ны ЛО:

(4.5)

Доказательство аналогично доказательству леммы 4.1.

Лемма 4.3. Общий для всех (положительных) элементов положитель­ный множитель можно вынести за знак ЛО:

(4.6)

Доказательство. При учитывая распределительный закон (1.45), имеем

Лемма 4.4. Общий для всех положительных элементов отрицателъный множитель можно вынести за знак ЛО, изменив тип ЛО ж противополож­ный

(4.7)

Доказательство. Приучитывая распределительный закон (1.48 ), получаем

Лемма 4.5. Знак минус, присутствующий во всех элементах ЛО, можно вынести за знак ЛО, изменив тип ЛО на противоположный:

(4.8)

Доказательство следует из (4.7) при λ = —1.

Лемма 4.6. Общее для всех элементов слагаемое можно вынести за знак ЛО, предварительно умножив на число Р столбцов в нем:

(4.9)

Доказательство. Имеем с учетом распределительного закона (1.37) и того, что в каждой суммеприсутствует ровно один элемент

от каждого из Р столбцов ЛО:

Лемма 4.7. Общее для всех элементов уменьшаемое можно вынести за знак ЛО, предварительно умножив на число столбцов Р в нем; при этом тип ЛО меняется на противоположный: