Диссертация (1149691), страница 15
Текст из файла (страница 15)
Функция bitscount выдает число ненулевых бит в двоичном представлении своего целочисленного аргумента.В случае вектора-редистрибъютора будет удобнее не рассуждать о совместности свидетельств, а напрямую обратиться к полученной выше формепредставления через тензорное произведение ⎛[94].Рассмотрим все места, где⎞⎜0⎟+⎟в тензорном произведении встречается r+ = ⎜⎝ ⎠. Заметим, что позиции r1определяются положительным свидетельством, а именно — единичнымибитами в индексе положительного свидетельства. Если в позиции, где содержит единичный бит, будет содержать нуль, то в определении значения⟨ ; ⟩ будет участвовать верхний (нулевой) элемент-го элемента вектора rвектора r+ , что заведомо обращает указанный элемент в нуль. Таким образом, мы получаем первую строку указанного выше равенства.⎛ ⎞⎜1⎟⎟Теперь рассмотрим позиции, где встречается r∘ = ⎜⎝ ⎠.
Рассуждения0будут аналогичны предыдущему случаю [94]. Вектор r∘ встречается там,где одновременно индексы положительного и отрицательного свидетельства имеют нулевой бит, т.е. позиции, где выражение ∨˙ имеет единицу вдвоичной записи. Заметим, что если в такой позиции у в двоичной записибудет единица, то при вычислениях будет использоваться нижний (равныйнулю) элемент вектора r∘ . Иначе говоря, если у ∨˙ и будет единицав одной и той же позиции двоичной записи, то -й элемент вектора r⟨ ; ⟩заведомо будет нулем.
Эта ситуация в точности соответствует второй строке приведенного выше равенства. Следует заметить, что первое и второе 87условие не являются взаимоисключающими и могут выполняться одновременно, но так как в обоих случаях соответствующий элемент вектора r⟨ ; ⟩равен нулю, то мы можем написать их и по отдельности.Выше мы разобрали все ситуации, когда r⟨ ; ⟩ [] равно нулю. Рассмотрим оставшиеся значения. Так как r+ и r∘ либо обращают значениев нуль, либо не меняют его (умножают на единицу), а ситуации с нулем мыразобрали, то они не будут оказывать влиянияна оставшуюся ситуацию.⎞⎛1⎟⎜⎟Остается определиться со вкладом r− = ⎜⎠ в итоговое значение.
Если⎝−1в соответствующей позиции двоичной записи m стоит нуль, то в вычислении используется верхний (равный единице) элемент вектора r− , которыйне оказывает влияния на результат. Остается ситуация, когда в соответствующей позиции двоичной записи m стоит единица, при этом происходитумножение на минус один. Но таких мест, где единица встречается в двоичной записи m и двоичной записи одновременно, ровно столько, сколько˙ .
Это в точности приводит нас к последнейненулевых бит в числе &строке указанного выше равенства [94].Проведем аналогичные изыскания по отношению к вектору d⟨ ; ⟩ , используемому в уравнениях апостериорного вывода для идеала дизъюнктов.Заметим, что элементы тензорного произведения, результатом которого является вектор d⟨ ; ⟩ схожи с элементами в тензорном произведениивектора-редистрибьютора с тем лишь различием, что r+ = d− и r− = d+ .Перейдем к формированию системы, определяющей значение элемента вектора d⟨ ; ⟩ . Отметим, что позиция d− определяется единичными битами виндексе отрицательного свидетельства . Тогда, если на позиции в битовомпредставлении, где в находится 1 в будет стоять 0, то -й элементвектора d⟨ ; ⟩ будет нулевым из-за наличия в произведении нулевого эле(︁)︁˙ ̸= .мента.
Данное условие можно записать следующим образом: &Рассуждения, касающиеся d∘ аналогичны рассуждениям о равному ему r∘и дают вторую часть первой строки системы, описывающей поэлементоевычисление вектора d⟨ ; ⟩ .Применим результат рассуждений об отрицательных элементах вектора-редистрибьютора к вектору d⟨ ; ⟩ с тем лишь отклонением, что вместоr− и соответствующего ему представления отрицательного свидетельста 88мы возьмем d+ и .
Тогда выражение, описывающее ненулевые элементы˙вектора d⟨ ; ⟩ : (−1)bitscount( & ) .Суммируя все вышесказанное, запишем итоговую систему [168]: ⎧⎪⎪⎨˙ ̸= или&⟨;⟩d [] = ⎪bitscount( &˙ ) , иначе.⎪⎩(−1) 0, если(︁)︁(︁∨˙˙ ̸= 0 ;&)︁(3.40).Заметим, что такая возможность по вычислению коэффициентов,отмеченная в [94], позволяет в расчетах воспользоваться концепцией отложенных вычислений. Нам не требуется строить сразу весь вектор s⟨ ; ⟩ ,d⟨ ; ⟩ или вектор r⟨ ; ⟩ .
Наоборот, в программной реализации мы сможемвычислить любую их компоненту по мере надобности, избегая хранениявспомогательных объектов значительной размерности.Наконец, рассмотрим несколько примеров, иллюстрирующих объекты, которые строятся в утверждение доказанных выше теорем. Таблица 3 — Примеры расчета векторов s⟨ ; ⟩ , r⟨ ; ⟩ , d⟨ ; ⟩ АлфавитСвидетельствоs⟨ ; ⟩ s⟨1 0⟩ = s+ ⊗ s∘⎛ ⎞{1 0} ,0 = ⟨1; 0⟩ =⟨01; 00⟩s⟨1 0⟩ =,⎜⎜⎜⎜⎜⎜⎜⎜⎝101⎟⎟⎟⎟⎟⎟⎟⎠,⎛ ⎞{1 0} ,¯0 = ⟨0; 1⟩ =⟨00; 01⟩,⎛ ⎞r⟨1 0⟩ =,s⟨0 1⟩ =,⎜⎜⎜⎜⎜⎜⎜⎝010⎟⎟⎟⎟⎟⎟⎟⎠⎜⎜⎜⎜⎜⎜⎜⎜⎝100⎟⎟⎟⎟⎟⎟⎟⎠r⟨0 1⟩ =,⎜⎜⎜⎜⎜⎜⎜⎜⎝,⎛d⟨1 0⟩ =,,⎛d⟨1 0⟩ = d+ ⊗ d∘0⎟r⟨0 1⟩ = r− ⊗ r∘⎜1 ⎟d⟨ ; ⟩ r⟨1 0⟩ = r+ ⊗ r∘0⎟s⟨0 1⟩ = s− ⊗ s∘ r⟨ ; ⟩ , ⎞−1001⎟⎟⎟⎟⎟⎟⎟⎟⎠−100d⟨0 1⟩ = d− ⊗ d∘,⎛ ⎞1⎟⎟⎟⎟⎟⎟⎟⎟⎠⎜⎜⎜⎜⎜⎜⎜⎜⎝⎞d⟨0 1⟩ =,⎜⎜⎜⎜⎜⎜⎜⎜⎝0⎟⎟1⎟⎟00⎟⎟⎟⎟⎠89Продолжение таблицы 3АлфавитСвидетельствоs⟨ ; ⟩r⟨ ; ⟩ s⟨1 0⟩ = s+ ⊗ s∘,[2]⎛ ⎞{2 1 0} , ,0 = ⟨1; 0⟩ =⟨001; 000⟩s⟨1 0⟩ =,⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝1010101⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠[2],⊗ s∘⎛ ⎞{2 1 0} , ,0 1 = ⟨3; 0⟩ =⟨011; 000⟩s⟨3 0⟩ =,⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝0010001s⟨1 2⟩ =,⎛ ⎞r⟨1 0⟩ =,⎛ ⎞,2 1 0}0 ¯1 = ⟨1; 2⟩ = ⟨001; 010⟩s⟨1 2⟩ =,1000000⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠[2]⎛ ⎞r⟨3 0⟩ =,⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝1000100⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠00100001⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠−1000000[2],⎛d⟨3 0⟩ =,⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⊗ d∘⎞1⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠−1−110000d⟨1 2⟩ =,r+ ⊗ r− ⊗ r∘⎛,⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝d⟨3 0⟩ = d+0⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠⎞⎛,⊗ r∘[2],d⟨1 0⟩ =r⟨1 2⟩ =r⟨1 2⟩ =d⟨1 0⟩ = d+ ⊗ d∘0⎟r⟨3 0⟩ = r+⎜0 ⎟ , ,⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝,s+ ⊗ s− ⊗ s∘{[2],0⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠ r⟨1 0⟩ = r+ ⊗ r∘0⎟s⟨3 0⟩ = s+ d⟨ ; ⟩ ⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⎞d+ ⊗ d− ⊗ d∘⎛0⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠10−10000d⟨1 2⟩ =,⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎜⎝⎞0⎟⎟0⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎟⎠1−10000903.6Оценка сложности алгоритмов апостериорного выводаВ параграфах 3.3–3.4 мы рассмотрели матрично-векторные уравненияапостериорного вывода, являющиеся развитием подхода к апостериорномувыводу, предложенному А.В.
Сироткиным и А.Л. Тулупьевым [143; 158].Новые алгоритмы используют вектора r⟨ ; ⟩ ,s⟨ ; ⟩ и d⟨ ; ⟩ , позволяющие сократить количество вычислений.Оценка сложности алгоритмов является важной составляющей в проектировании программного обеспечения, планировании экспериментов и,наконец, сравнении предполагаемого времени работы и объема требуемойпамяти алгоритмов. В работах [124; 127] были предложены оценки сложности алгоритмов поддержания непротиворечивости, априорного вывода иапостериорного вывода. Однако стоит отметить, что в работах о сложностиалгоритмов апостериорного вывода не учитывались затраты на построениематриц T⟨ ; ⟩ , H⟨ ; ⟩ , M⟨ ; ⟩ , в то время как эта операция требует 4 умножений, где — мощность алфавита ФЗ.
Кроме того не была отдельнорассмотрена оценка сложности алгоритма решения первой задачи апостериорного вывода.В данном параграфе мы сформулируем и докажем новые оценкисложности алгоритмов апостериорного вывода с учетом использования полученных векторов и новых нормирующих множителей. Говоря в данномразделе о сложности алгоритмов, мы будем подразумевать, что для чиселзадано некоторое представление фиксированного размера, то есть сложность операций с данным представлением является константной и не влияетна общую сложность алгоритма.Итак, рассмотрим фрагмент знаний над набором пропозиций-квантов⟨,Pq⟩ со скалярными оценками вероятностей, построенный над алфавитом = {1 , 2 , .
. . , −1 , } и предположим, что в данный ФЗ поступилосвидетельство, построенное над алфавитом ev = {1 ,2 , . . . , −1 , }. Вформулировке и доказательствах последующих теорем данного параграфаположим, что свидетельство построено над атомами, а ФЗ, куда свидетельство поступает, над атомами.
Сформулируем оценки сложности 91операций вычисления вероятности свидетельства (первая задача апостериорного вывода) и апостериорных оценок вероятностей элементов ФЗ(вторая задача апостериорного вывода) для различных типов свидетельств.Теорема 3.6.1.Для решения первой задачи апостериорного выводатребуется сделать не более2 +1умножений и2сложений/вычитаний.Рассуждения будем строить на результатах, полученных в теореме 3.3.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
