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

определяется первой строкой, а при — второй строкой (3.23). Очевидно, что С2 непусто лишь для r, которым в (3.26) соответствует дробное значение р. В С3 входят этапы с последующими но­мерами k, для которых количество элементов п (k) в ЛО превосходит r, т. е.откуда На каждом таком этапе ЛО вычисляется для значений ранга (т. е. и соответствующая сложность определяется первой строкой (3.23).

В соответствии с разбиением множества этапов вычисляем внутреннюю сумму в (3.22):

(3.27)

(3.28)

(3.29)

Подставляя выражения (3.27)- (3.29) в (3.22), после суммирования по k найдем оценку сложности вычисления ЛО в (3.20) при r> m

(3.30)

Совместно с уже найденной оценкой (3.25) для случая формула

(3.30) и есть требуемый результат. В (3.30) р - соответствующий r пока­затель, равный, согласно (3.26), а символы справа от каж­дой скобки показывают условия, при которых эта скобка присутствует в общем выражении. Полагая для простоты, что р в (3.30) целое, и учиты­вая (3.25), найдем упрощенную оценку (в которой n=qm)

(3.31)

Сложность вычисления ЛО-столбца методом последовательной блочной дихотомии получается из выражений (3.25), (330), (3.31) при условии т = 1, q = п. При этом общая оценка сложности (в предположении r > 1) имеет вид

(3.32)

где, в согласии с (3.26), а частная (в предположении, что

р — целое):

(3.33)

где

Как видно из формул (3.31), (3.33), сложность вычисления конечного ЛО (как общего вида, так и столбцевого) растет линейно при увеличении ранга r и числа элементов п. Таким образом, последовательная блочная дихотомия позволяет вычислять конечные ЛО высоких рангов с большим числом элементов.

3.4. Приближенное вычисление логических определителей. Случай определителя-столбца

Часто значения элементов ЛО известны неточно. В таких случаях точные методы вычисления ЛО, рассмотренные выше, не оправданы. Здесь целе­сообразен переход к приближенным методам — таким, которые обеспечи­вают необходимую точность вычисления, но обладают меньшей сложностью, что позволяет вычислять большие ЛО. Эти методы являются также доволь­но действенным средством вычисления больших ЛО с точно заданными значениями элементов в тех случаях, когда точные методы вычисления ЛО малоприемлемы из-за их большой сложности.

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

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

(3.34)

Величина такого ЛО для различных рангов r

(3.34а)

В частности, вырожденный ЛО-столбецсогласно (2.117), имеет равные элементы

(3.35)

В силу (3.35) для всех r верно Рассмотрим относительно простые задачи отыскания оценок ЛО-столбца. Оценки для общих ЛО будут даны в двух следующих параграфах. Начнем с получения оценки снизу. Используем выражение ЛО в ДНФ БЛ (2.26). Сохраним в этом выра­жении все конъюнкции вида Всего таких конъюнкций будет

(3.36)

гдеозначает целую часть х. Остаются неиспользованными элементов ai со старшими номерами i. Чтобы они фигурировали в оценке, сохраним в выражении (2.26) еще конъюнкцию В итоге получим оценку

(3.37)

Для получения оценки сверху используем точное выражение ЛО в КНФ БЛ (2.27). Сохраним в этом выражении все дизъюнкции вида

Всего таких дизъюнкций

(3.38)

так что неиспользованными останутся R ≤ r элементов со старшими номе­рами i. Поэтому сохраним в выражении (2.27) еще дизъюнкцию В результате получим оценку

(3.39)

Очевидно, что оценки (3.37) - (3.39) удовлетворяют условию согласован­ности, т. е. переходят в строгие равенства в случае (3.35). Они переходят в строгие равенства и в более общем случае, когда элементы ЛО упорядо­чены в виде

Собрав вместе оценки (3.37), (3.39). получим такой результат.

Теорема 3.1. Значение ЛО-столбца r-го ранга, содержащего п элементов, заключено в границах

(3.40)

Сложность вычисления нижней и верхней оценок (3.40), измеряемая числом двухместных операций дизъюнкции и конъюнкции БЛ, равна

(3.41)

Как видно из (3.41), суммарная сложность вычисления обеих оценок рас­тет как 3n (линейно) с увеличением числа элементов n в ЛО. Напомним, что сложность точного вычисления ЛО-столбца по готовым формулам (2.26), (2.27) растет как пr (см. (3.3)), а по методу дихотомического блочного разложения — как пr (см. (3.33)). Так что переход к приближен­ным оценкам позволяет существенно уменьшить сложность вычисления ЛО. Погрешность вычисления ЛО, обусловленную приближенным характером используемых оценок, легко контролировать — она равна разности между верхней и нижней оценками.

3.5. Приближенное вычисление общего бесконечного логического определителя

Для общего бесконечного ЛО найдем сначала оценку снизу, исполь­зуя точное выражение ЛО в ДНФ БЛ (2.29). Введем в рассмотрение сред­нее арифметическое значение d второго индекса элемента aij одной конъ­юнкции в (2.29). Так как в конъюнкции q элементов, а сумма их вторых индексов равна q + r — 1, то

(3.42)

Сохраним в выражении (2.29) одну конъюнкцию: где k - неизвестный второй индекс, определяемый из условия, налагаемого на сумму вторых индексов:

(3.43)

Тогда для оцениваемого ЛО Arq получается неравенство Но из (3.43) с учетом неравенства следует Отсюда, поскольку элементы в каждой строке ЛО упорядочены по величине, имеем . Теперь в выписанном неравенстве для можно заменить от этого неравенство лишь усилится.