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

(2.76)

Последующие этапы выполняются аналогично 2-му: группируются строки (2.76) из ЛО и т. д. Наконец, на последнем, v-м этапе строки из упорядоченных по рангам ЛО

(2.77)

полученные на (v — 1)-м этапе, не группируются, а рассматриваются как одно множество строк. Из множества (2.77) составляется единственный ЛО порядка т ранга r, который по формуле (2.72) выражается через найденные на (v - 1)-м этапе ЛО В результате получается искомое выражение ЛОчерез его элементы. Вычислив это выра­жение, тем самым мы вычислим ЛО

Определим число этапов и число строк в группе на каждом этапе так, чтобы минимизировать сложность выражения (вычисления) ЛО Пусть на каждом этапе строки объединились в группы по k строк. Найдем значение минимизирующее указанную сложность. На 1-м этапе имеем различных ЛО каждый из которых надо вычислить для значений ранга Поэтому сложность 1-го этапа

где — сложность вычисления по формуле (2.29) общего

бесконечногоЛО порядка k ранга i. На 2-м этапе имеем различных ЛОвычисляемых для рангов Отсюда сложность 2-го этапа Аналогично анализируется 3-й этап - его сложностьи т. д. На предпоследнем этапе имеем k различных ЛО (каждый рангов с общей сложностью вычислений На последнем этапе имеем ЛО k-го порядка, единственного ранга r. Сложность его вычисленияТаким образом, сложность вычисления ЛО по предложенной процедуре

(2.78)

С учетом выражения (3.7) для имеем

Подставляя это значение и значение в (2.78), после суммирования

прогрессии найдем

(2.79)

Выразив в (2.79) через факториалы, найдем, что при

(2.80)

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

(2.81)

Поскольку на каждом этапе общее число строк уменьшается вдвое, общее число этапов в оптимальной процедуре составляет

(2.82)

Согласно § 2.11 алгоритм вычисления общего конечного ЛО q-го по­рядка r-го ранга основанный на разложении (2.73), принципиально не отличается от рассмотренного алгоритма вычисления бесконечного ЛО на основе разложения (2.72) и сводится к выполнению двух опера­ций: 1) группировка строк имеющегося ЛО и образование из каждой группы строк своего ЛО; 2) вычисление полученных ЛО для последо­вательных значений ранга s = 1, 2, . . . , что дает новые строки. При этом на последнем этапе все имеющиеся строки образуют единый ЛО, кото­рый вычисляется для единственного значения ранга s = r. Некоторые от­личия алгоритма, обусловленные конечностью ЛО таковы: а) на каж­дом этапе, включающем две указанные выше операции, операция 2) вы­полняется не по формуле (2.72), а по формуле (2.73); б) на 1-м, 2-м. . . , k-м, . . . , предпоследнем этапах вычисление каждого ЛО ведет­ся для значений ранга если (где п (k) - число элементов в ЛО на k-м этапе), и для значений ранга еслиКак и для бесконечного ЛО, примем, что на каждом эта­пе строки ЛО объединяются в группы по две, полагая, что такая процеду­ра вычисления ЛО минимальна по сложности. Формула, по которой вы­числяются получающиеся на этапе ЛО 2-го порядка, аналогична (2.81)

(2.83)

Общее число этапов в процедуре дается прежней формулой (2.82). Определитель-столбец

(2.84)

— частный случай общего ЛО

при m = 1, q = п. Поэтому ЛО вида (2.84) можновы числить с помощью изложенного алгорит­ма. Именно, на 1-м этапе, сгруппировав элементы в по два, получим n/2 ЛО-столбцов с двумя элементами. Вычислив каждый для всех значений ранга s = 1,2, получим n/2 новых строк длины 2. Составим из них общий ЛО c

m = 2. На 2-м этапе, сгруппировав строки в по две, получим ЛО 2-го порядка с 22 элементами (в каждой строке по 2 элемента). Вычислив каждый для всех значений ранга s =1, 2, . . . , 22, получим n/22 новых строк длины 22, из которых составим новый ЛО и т. д. На k-м этапе вычисляется ЛО 2-го порядка с п(k) = 2 элементами (по 2k-1 элементов в каждой строке). вычисляется: а) на этапе - для всех

значений ранга б) на последнем этапе - для единственного значения ранга s - r. Покажем преимущества вычисления ЛО путем их блочного разложения.

Пример 2.5. Рассмотрим ЛО-столбец

Его раскрытие по формуле (2.26) приводит к выражению

сложность которого 11 элементарных операций БЛ. Раскроем тот же ЛО по иерархическому правилу разложения:

После раскрытияи по формуле (2.26) получим выражение

со сложностью всего семь элементарных операций БЛ.

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