Выборка с минимальным зацеплением
Утверждение 6.16. Любой класс неотличимости однозначно характеризуется тройкой A1. A2. A3. Тогда аналоги соотношений (6.8) и (6.9) для рассматриваемого нами случая будет иметь вид. Несложно убедиться, что мощность множества M (Ai) вычисляется следующим образом: Где суммирование проводится по всем векторам х = (х,…, хп), у которых х = г, хп = j. Будем использовать в данном разделе следующие… Читать ещё >
Выборка с минимальным зацеплением (реферат, курсовая, диплом, контрольная)
Рассмотрим теперь задачу классификации булевых функций (соответствующих рассматриваемой функциональной схеме) относительно вероятностей встречаемости m-грамм в выборке с шагом п — 1 из выходной последовательности.
Другими словами, мы будем рассматривать задачу классификации функций относительно распределения значений линейных функций (от знаков выхода) с минимальным зацеплением аргументов.
Будем использовать в данном разделе следующие упрощенные обозначения.
При заданной функции /: —> F2 через А — A (f) будем обозначать матрицу (а^) — (<4j (f)). h.'i — 0,1, у которой элементы (iij вычисляются по формуле.
где суммирование проводится по всем векторам х = (х,…, хп), у которых х = г, хп = j.
Тогда аналоги соотношений (6.8) и (6.9) для рассматриваемого нами случая будет иметь вид 
где суммирование по всем i, j = 0,1,.
Будем также для простоты величину Л (/[?]) обозначать через Л (или At (f), если необходимо подчеркнуть ее зависимость от функции /.
Утверждение 6.16. Любой класс неотличимости однозначно характеризуется тройкой A1. A2.A3.
Справедливость этого утверждения непосредственно вытекает из утверждения 6.15 при h = 1. Отметим, что данное утверждение имеет следующую равносильную формулировку.
Утверждение 6.17. Распределение выходных т-грамм в выборке с шагом п — 1 из выходной последовательности для любого натурального т полностью задается распределением трехграмм.
Мы будем использовать следующие обозначения. При заданном исходном множестве функций Q С {/: F!> —> F2} через Му будем обозначать класс неотличимости, содержащий функцию / е Q, а через М (Аь Аг, Аз) — класс неотличимости, соответствующий тройке Ai, А2, A3.
Будем использовать также следующие обозначения:
Так как последовательность А, = А (/[г]), i = 1,2,… является линейной рекуррентной последовательностью степени 2 (задаваемой характеристическим многочленом матрицы Л (/)), то, если Ai = А2 = 0, тогда А: = 0 при всех i. Поэтому имеет место, в частности, следующее свойство:
Несложно убедиться, что мощность множества M (Ai) вычисляется следующим образом:
