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

3. ВЫЧИСЛЕНИЕ ПОРЯДКОВЫХ

ЛОГИЧЕСКИХ ОПРЕДЕЛИТЕЛЕЙ И ЕГО СЛОЖНОСТЬ

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

При практическом применении порядковой логики для исследования сложных систем возникает необходимость вычисления достаточно больших, т. е. содержащих много элементов, порядковых ЛО. Здесь и ниже под вычислением ЛО понимается отыскание численного значения ЛО по за­данным численным значениям его элементов. Будем оценивать сложность вычисления ЛО количеством элементарных двухместных операций БЛ, необходимых для получения численного значения ЛО. Для вычисления ЛО методически проще всего использовать готовые формулы раскры­тия ЛО (§ 2.5 - 2.7). При этом вычисление ЛО сводится к вычислению значения соответствующей функции БЛ, полученной в результате раскры­тия данного ЛО. Вместо указанных формул для раскрытия ЛО можно использовать процедуры их последовательного разложения на меньшие ЛО (§ 2.8 — 2.12). Однако в связи с этим возникают такие вопросы: 1) какова сложность указанных процедур вычисления ЛО; 2) в каких случаях эти процедуры можно рекомендовать как приемлемые по слож­ности;

3) что делать, если эти процедуры неприемлемы по сложности. Ответам на эти вопросы посвящена настоящая глава.

3.2. Сложность вычисления логических определителей по формулам раскрытия

Начнем с процедур вычисления ЛО-столбца по готовым формулам раскрытия (2.26), (2.27). Каждая конъюнкция в (2.26) для своего вы­числения требует п - r элементарных операций сравнения двух чисел, а общее количество конъюнкций равногде - числo

сочетаний из а элементов по b. Далее, для вычисления дизъюнкции в (2.26) требуется элементарных операций. Суммируя, найдем, что сложностьвычисления ЛО-столбца ранга r с п элементами по формуле (2.26) равна

(3.1)

Каждая дизъюнкция (2.27) для вычисления требует r - 1 элементарных oпераций сравнения двух чисел, а число всех дизъюнкций Для вычисле­ния конъюнкции требуется элементарных операций. Отсюда слож­ность вычисления ЛО-столбца с п элементами ранга r по формуле (2.27)

(3.2)

Легко убедиться (например, выразив через факториалы), что выраже­ния (3.1), (3.2) тождественно равны. С помощью формулы Стерлинга можно получить асимптотику выражения (3.1) при (см. § 3.9)

фиксировано;(3.3)

фиксировано. (3.4)

Из (3.2), (3.4) следует, что при фиксированном n/r сложность вычисле­ния ЛО-столбца по формулам (2.26), (2.27) растет экспоненциально по п, что делает нереальными вычисления при больших п: при фиксирован­ном r эта сложность растет как степенная функция пr, что дает возмож­ность вычисления даже больших ЛО невысокого ранга r.

Оценим сложность вычислений общего бесконечного ЛО по форму­ле (2.29) и общего конечного ЛО по формуле (2.30). Сложность вы­числения одной конъюнкции в (2.29) равна q — 1 элементарных опера­ций сравнения. Подсчитаем общее число L (q, r) таких конъюнкций. В об­разовании этих конъюнкций в силу леммы 2.14 участвуют лишь r первых элементов каждой строки ЛО. Зафиксируем некоторый элемент q-й стро­ки Соответствующих ему конъюнкций в (2.29) столько, сколько есть конъюнкций удовлетворяющих условию т. е.

Отсюда, суммируя по k от 1 до r, получаем общее число конъюнкций в (2.29)

(3.5)

Теперь для отыскания функции L(q, r) надо решить уравнение (3.5). Используем с этой целью рекуррентную по q процедуру. Во-первых,

L (1, r) = 1, так как при q = 1 формула (2.29) имеет вид Далее,

с помощью (3.5) последовательно находим

Полученные формулы подсказывают общее выражение

(3.6)

Докажем (3.6) индукцией по q. Справедливость (3.6) при q = 1, 2, 3, 4 уже доказана. Допустим, что (3.6) верно при некотором q = р. Докажем, что тогда оно верно и при q = р + 1. Имеем, согласно (3.5) и нашему пред­положению,

Таким образом, выражение (3.6) осталось справедливо и при q = р + 1, следовательно, оно справедливо при любом q.

Сложность вычисления общего бесконечного ЛО. r-го ранга

q-гo порядка по формуле (2.29) равна произведению сложности q — 1 вычисле­ния одной конъюнкции в (2.29) на число L(q, r) конъюнкций плюс слож­ность L(q, r) - 1 вычисления дизъюнкции (2.29). Отсюда с учетом (3.6) находим

(3.7)

Выражение (3.7) определяет также оценку сверху сложности вычисления общего конечного ЛО r-го ранга q-гo порядка по формуле (2.30). Дейст­вительно, вычисление общего конечного ЛО по формуле (2.30) отличается от вычисления общего бесконечного ЛО по формуле (2.29) отсутствием части операций.

Асимптотика выражения (3.7) при

фиксировано, (3.8)

отсюда

s фиксировано. (3.9)

Соотношение (3.8) находим, заменив в формуле (3.72) n на q + r - 2 и получив в результате оценку для которую подставляем в (3.7).

Соотношение (3.9) находим, заменив в формуле (3.73) п на q + r — 2 и подставив получившуюся оценкув (3.7). Из (3.8), (3.9) видно,

что при фиксированном q/r сложность вычисления общего ЛО по формулам (2.29), (2.30) растет экспоненциально по q; однако при фиксированном r эта сложность растет как степенная функция qr, и потому процедура прием­лема для вычисления больших ЛО низкого ранга r .

3.3. Сложность вычисления логических определителей методом последовательного разложения

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

(3.10)

Формула (3.10) позволяет находить для последовательно возрастаю­щих r. Положив в (3.10) r = 1, получимоткуда при очевид­ном начальном условииследует

(3.11)

Далее, положив в (3.10) r = 2, получим или с учетом (3.11) Решая уравнение в соответствии с очевидным начальным условием получим

(3.12)

При r = 3 из (3.10) получаем откуда после подстановки значений и из (3.11) и (3.12) и необходимых действий следует уравнение Решая его (начальное условие найдем