Логическая энтропия
Рассмотрение логической энтропии как меры неопределенности и сложности информационных моделей, описываемых булевскими функциями. Приводятся содержательные интерпретации логической энтропии. Отличие логической энтропии от энтропии Теории информации.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 28.10.2018 |
| Размер файла | 196,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
РОССИЙСКАЯ АКАДЕМИЯ НАУК
ОРДЕНА ЛЕНИНА ИНСТИТУТ ПРИКЛАДНОЙ МАТЕМАТИКИ
ИМЕНИ М.В. КЕЛДЫША
С.В. Попов
ЛОГИЧЕСКАЯ ЭНТРОПИЯ
Москва, 2005г.
Вводится понятие логической энтропии как меры неопределенности и сложности информационных моделей, описываемых булевскими функциями. Приводятся содержательные интерпретации логической энтропии. Демонстрируется отличие логической энтропии от энтропии Теории информации. Выделяется класс физических систем, энтропия которых совпадает с энтропией их информационных моделей.
логическая энтропия информационная модель
It is entered notion of logical entropy as measures to uncertainties and difficulties of the information models, described logical functions. Profound interpretation to logical entropy is given. It is demonstrated difference between the logical entropy and entropy of Theory of information. Stands out the class of the physical systems, entropy which comply with entropy their information models.
De non apparetibus et non existentibus eadem est ratio.
О том, чего не видно и о том, чего не существует, судят одинаково. (лат.)
Введение. Содержательное обоснование логической энтропии, как меры неопределенности информационных моделей дано в [1], где физические системы представляются логическими функциями, аргументы которых используются для кодирования объектов. В результате объекты в информационных моделях кодируются единичными означиваниями логических функций. И если различные означивания приводят к логически эквивалентным функциям, то они определяют одну характеристическую функцию некоторой совокупности объектов.
Более формально это выглядит так.
Пусть булевская функция f(x1, x2, …, xn) служит информационной моделью физической системы. Ее объекты кодируются наборами вида (1, 2, …, n) признаков, i {0, 1}, i = 1, 2, …, n, при котором функция f истинна. Тем самым, число различных объектов не превосходит мощности множества
{(1, 2, …, n)| f(1, 2, …, n) = 1}
единичных означиваний функции f.
В [1] введено понятие неопределенности физической системы (x1, x2, …, xn), определяемой переменными x1, x2, …, xi, i n. Аналогично определяется неопределенность ее информационной модели f(x1, x2, …, xn), определяемой переменными x1, x2, …, xi, i n. Как будет показано неопределенность функции f(x1, x2, …, xn), определяемая переменными x1, x2, …, xi, обладает следующими свойствами.
1. Ее значение зависит от числа k подфункций, которые получаются в результате разложения функции по переменным x1, x2, …, xi. При увеличении k (при прочих равных условиях) неопределенность возрастает.
2. Неопределенность определяется относительными долями мощностей соответствующих множеств 1, 2, .., k означиваний переменных x1, x2, …, xi, приводящих к эквивалентным функциям. Если все множества 1, 2, .., k одинаковы и доля каждого равна 1/k, то неопределенность монотонно возрастает с ростом k.
3. При переходе от означивания переменных x1, x2, …, xi, к означиванию переменных x1, x2, …, xi, xi+1 их неопределенность зависит от неопределенности, определяемой переменными x1, x2, …, xi.
Последнее свойство легко объяснимо с содержательной точки зрения, если заметить, что между аргументами функции f могут существовать зависимости, когда значения одних переменных в той или иной степени определяют значения других. Например, в случае функциональной зависимости одному значению некоторых переменных соответствует в точности одно значение других. И тогда порядок означивания существенно определяет последовательность разбиений объектов на классы. В результате, свойство аддитивности неопределенности нарушается.
1. Неопределенность булевских функций. Определим понятие энтропии логической функции и установим ее связь со структурой функций. Формальное определение логической энтропии мы введем, основываясь на следующем.
Пусть f(У, w) есть булевская функция, множество У ее аргументов назовем входными переменными и w - выходными. При определенных значениях Y ее входных переменных и w - выходных f(Y, w) = 1. Тем самым, функция f определяет отображение, ставящее в соответствие входным значениям - выходные. В общем случае, один входной кортеж определяет несколько выходных.
Напомним, что логическая функция f(Y, w) представляет вычислимую двоичную функцию (Y) если: f(Y, w) = 1 (Y) = w.
Назовем кортеж y означиваний (не обязательно всех) входных переменных y y-набором. Тем самым, для логической функции f(Y, w), представляющей вычислимую функцию, верно, что всякий ее y-набор определяет некоторое множество w-наборов.
Нам потребуется следующее определение.
Бинарной программой f для логической функции f(x1, x2, …, xn) называется ор-дерево с единственным корнем (истоком), которому приписана функция f(x1, x2, …, xn), и двумя висячими узлами, одному из которых приписано значение 1 (1-сток), другому 0 (0-сток), а дуги помечены литерами xi илиxi, i = 1, 2, …, n. Если два узла сети соединяются путем, дуги которого не содержат ортогональных меток, то назовем его проводящим. Каждый узел дерева достижим из истока. Проводящий путь, дуги которого помечены метками, образующими множество {xj11, xj22, …, xjmm} литер, где 1, 2, …, m {0, 1}, назовем определяющим это множество.
Внутренние узлы и дуги программы помечены следующим образом.
Каждой дуге приписана в точности одна литера xi илиxi, i = 1,2, …, n.
Из каждого внутреннего узла ведут в точности две дуги, которым приписаны литеры xi иxi, i = 1,2, …, n.
Если в узел N ведет проводящий путь, дуги которого помечены метками xj11, xj22, …, xjmm , то этому узлу приписана функция, которая получается из исходной в результате присваивания переменным xj1, xj2, …, xjm значений соответственно 1, 2, …, m. Узлы, соответствующие эквивалентным функциям, склеиваются. При этом узлу приписан в точности один представитель класса эквивалентности.
Для каждого из 2n двоичных наборов х переменных имеется путь проводящий из истока либо в 1-сток либо в 0-сток, множество меток дуг которого покрывается компонентами х.
Так как логическая функция однозначно характеризуется перечислением своих 1-проводящих путей, то будем мыслить бинарные программы, состоящими лишь из 1-проводящих путей. Тогда бинарная программа представляет собой двухполюсник с истоком, которому приписана логическая функция f, и стоком, который помечен 1.
Пусть функция f(Y, w) представляет вычислимую двоичную функцию . В бинарной программе f каждое вычисление (Y) = w представлено единственным путем из истока в сток. Ограничимся рассмотрением программ, для которых все пути из истока на начальных отрезках содержат дуги, помеченные литерами, образованными только из входных переменных y, и после этих отрезков дуг с такими метками не встречается. Такие бинарные программы назовем однородными.
Введем еще одно определение.
y-сечением однородной бинарной программы назовем множество всех ее узлов, которыми завершаются все пути, начинающиеся в истоке и дуги которых помечены литерами, образованными лишь из переменных некоторого подмножества y входных переменных.
Применительно к вычислениям, реализуемым бинарными программами, можно говорить о неопределенности выходных значений от входных. Действительно, если задан y-набор y, то он задает единственный путь программы f из истока в некоторый узел N. Нам удобно мыслить узел N как некоторый промежуточный вычислитель. Он может соединяться со стоком несколькими путями, каждый из которых характеризуется собственными выходными значениями. И только по входным значениям нельзя определить, какой именно выходной вектор появится на выходе такого вычислителя. В связи с этим можно говорить лишь о различении множеств выходных векторов, которые определяются различными узлами y-сечения.
Мы рассмотрим несколько различных подходов к вычислению неопределенности и дадим их содержательные интерпретации. Это прояснит связь настоящего подхода с традиционным в Теории информации.
В последующем, главным образом мы будем рассматривать логические функции, представляющие всюду определенные вычислимые функции. Во избежание путаницы, мы всегда будем указывать, какие логические функции рассматриваем, если это не вытекает из контекста. Очевидно, что если логическая функция f(Y, w) представляет всюду определенную вычислимую функцию (Y), то при любом y-наборе y функция f(y, w) не является тождественным нулем. В этом случае (y) = {w: f(y, w) = 1 при любых подстановках на места не означенных переменныъ}.
Если полагать, что входные переменные независимы и их значения 0 и 1 одинаково возможны, то можно говорить о неопределенности зависимости выходных значений от входных, как о характеристике y-сечения. Действительно, чем меньше y-сечение, тем больше определенность, какой промежуточный вычислитель вычислеят выходные значения. В предельном случае, когда сечение содержит в точности один узел, при любом входном векторе все вычисления осуществляются одним вычислителем. Если сечение имеет 2|y| узлов, то неопределенность максимальна, так как имеется возможность выбора из наибольшего числа доступных вычислителей.
Выберем в качестве показателя неопределенности выходных значений в зависимости от входных y, двоичный логарифм от числа узлов y-сечения программы f. Полагаем, что все входные переменные y независимы, y-сечение состоит из k узлов, каждый его узел соединен с истоком одним и тем же числомt путей и число всех путей программы из истока в y-сечение равно t.
Справедливо равенство log k = log (t /t ). Доля путей, ведущих в один узел y-сечения среди всех путей программы f из истока в y-сечение равна py =t /t. Тогда log k = - log py. Если предположить, что доли py(i) путей, ведущих в i-ый узел y-сечения программы f различны, наложив требование, чтобы выполнялось равенство i=1,k py(i) = 1, то получим более общую формулу - i=1,k py(i) log py(i), которая выражает неопределенность означенных переменных. Еще раз подчернем, что рассматриваемое сечение определяется в результате означивания подмножества входных переменных y. Из этого следует, что
log k - i=1,k py(i) log py(i).
Доля py(i) в общем случае зависит от способа построения бинарной программы выше y-сечения. Чтобы в этом убедиться, рассмотрим два примера.
Пример 1. Пусть функция f(x1, x2, y1, y2, z) = (x1x2 x1x2)(y1y2y1y2)f1(z)(x1x2)(y1y2y1y2)f1(z)x1x2(y1y2y1y2)f2(z).
Здесь z - это не пустой набор переменных отличных от x1,x2,y1,y2. Начальный фрагмент бинарной программы для этой функции приведен на рис.1. Здесь для каждого узла вначале указан его номер, затем (в скобках) - доли путей, ведущих из истока в этот узел, от числа всех приведенных путей. Так в узел 1 ведут два пути, которые получаются в результате означиваний переменных {x1 = 1, x2 = 0} и {x1 = x2 = 0}. На рис. 1 этим путям соответствует одна дуга, помеченная {x1x2}{x1x2}. Соответствие между меткой дуги и соответствующими означиваниями очевидно. Всего же путей из истока, которые получаются в результате означиваний переменных x1 и x2, четыре. Следовательно, доля всех путей из истока в узел 1 среди всех путей равна Ѕ. Аналогично вычисляются доли путей, ведущие в остальные узлы.
Построим для этой функции бинарную программу с другим порядком означиваний переменных, как на рис.2. Видно, что доли путей ведущих в узлы, которым приписаны одинаковые функции для первой программы и для второй (узлы 4 и 5 первой программы соответствуют узлам 3 и 4 второй) отличаются.
Рис. 1
Рис. 2
Пример 2. Пусть логическая функция f(x1, x2, y1, y2, z) =
(x1x2x1x2)(y1y2y1y2y1y2)f1(z)(x1x2)(y1y2y1y2)f1(z)x1x2y1y2f2(z).
Здесь z - это не пустой набор переменных отличных от x1, x2, y1, y2. Начальный фрагмент бинарной программы для этой функции приведен на рис.3.
Рис. 3
Рис. 4
Таким образом, если мы хотим ввести меру неопределенности как функцию бинарной программы, расположенной выше y-сечения, то необходимо учитывать последовательности означиваний переменных в бинарной программе.
Введем ряд определений.
Пусть i-ый узел y-сечения соединен Nyz|y(j1|i), Nyz|y(j2|i), …, Nyz|y(jk|i) путями в точности с узлами соответственно j1, j2, …, jk yz-сечения и Nyz = Nyz|y(j1|i) + Nyz|y(j2|i) + …+ Nyz|y(jk|i) - это число всех путей, ведущих из i-го узла в yz-сечение. Тогда величина pyz|y(js| i) = Nyz|y (js| i)/Nyz - есть доля путей, ведущих из i-го узла y-сечения в js-ый узел yz-сечения, s = 1, 2, …, k среди всех путей из i-го узла y-сечения в yz-сечение. Понятно, что s=1,k pyz|y(js| i) = 1, так как j1, j2, …, jk - это все узлы yz-сечения, в которые имеются пути из i-го узла y-сечения.
Пусть в бинарной программе i-ый узел y-сечения соединен путями в точности с узлами j1, j2, …, jk yz-сечения; h1, h2, …, hm - суть все узлы yzu-сечения, в которые мы попадаем из узлов j1, j2, …, jk yz-сечения (см.рис.5). Тем самым из i-го узла y-сечения в узлы h1, h2, …, hm yzu-сечения мы можем попасть только через какой-либо узел из j1, j2, …, jk yz-сечения.
Рис.5
Из определения следует равенство:
t=1,k pyzu|yz(hs | jt) pyz|y(jt | i) = pyzu|y(hs | i).
Действительно, i-ый узел y-сечения соединен путями с узлами j1, j2, …, jk yz-сечения и доля таких путей, ведущих в jt-ый узел равна pyz|y(jt | i). В свою очередь jt-ый узел соединен с некоторыми узлами из совокупности h1, h2, …, hm yzu-сечения, причем доля таких путей, ведущих из jt-го узла в hs-ый узел равна pyzu|yz(hs | jt). Но тогда доля путей из i-го узла y-сечения в hs-ый узел yzu-сечения равна указанной сумме.
Справедливы следующие равенства:
s=1,m pyzu|y(hs | i) = 1; t=1,k pyz|y(jt | i) = 1; s=1,m pyzu|yz(hs | jt) = 1, t = 1, 2, …, k.
Последнее равенство выполняется для тех пар узлов, которые соединены путями.
Теорема 1. Для всяких, не пересекающихся множеств y, z, u аргументов имеет место равенство t=1,k, s=1,m pyzu|yz(hs|jt) pyz|y(jt|i) = 1.
Доказательство. По определению t=1,k pyz|y(jt | i) = 1.
Для каждого из узлов j1, j2, …, jk yz-сечения имеем равенство s=1,m pyzu|yz(hs | jt) = 1, t = 1, 2, …, k.
Умножая каждый член первой суммы на s=1,m pyzu|yz(hs | jt), получаем равенство s=1,m t=1,k pyzu|yz(hs | jt) pyz|y(jt | i) = 1.
Теорема доказана.
Определим рекурсивно величину pz(i) как долю путей, проходящих из истока в i-ый узел z-сечения бинарной программы.
Пусть z = z1z2…zm - последовательность аргументов и однородная бинарная программа имеет z1-сечение, z1z2-сечение, …, z1z2…zm-сечение, причем множества путей заданы следующими значениями: Nz1z2…zm| z1z2…zm-1(i| jm-1), Nz1z2…zm-1| z1z2…zm-2(jm-1| jm-2), …, Nz1z2| z1 (j2| j1), Nz1(j1) при соответствующем именовании узлов сечений. Нетрудно увидеть, что число Nz1z2…zm(i) всех путей из истока программы в i-ый узел z-сечения равно сумме
j1,j2,…,jm-1Nz1z2…zm|z1z2…zm-1(i|jm-1) Nz1z2…zm-1|z1z2…zm-2(jm-1|jm-2)…
… Nz1z2| z1(j2| j1) Nz1(j1),
где суммирование ведется по всем узлам указанных сечений. Используя частичные суммы, получим, что эта сумма равна
jm-1 Nz1z2…zm| z1z2…zm-1(i| jm-1) Nz1z2…zm-1 (jm-1).
Здесь Nz1z2…zm-1 (jm-1) - это число путей, ведущих из истока в jm-1-ый узел z1z2…zm-1-сечения.
Обозначим Nz общее число различных путей из истока в z-сечение и разделим каждый член последней суммы на величину Nz. Тогда отношение
Nz1z2…zm| z1z2…zm-1(i| jm-1) Nz1z2…zm-1(jm-1)/Nz
представляет собой долю всех путей из истока в i-ый узел z-сечения, проходящих через jm-1-ый узел z1z2…zm-1-сечения среди общего множества путей из истока в z-сечение.
Доля pz1z2…zm-1(jm-1) путей из истока в z1z2…zm-сечение, проходящих через узел jm-1 z1z2…zm-1-сечения также определяется общим числом таких путей среди остальных, ведущих в z1z2…zm-сечение. Причем только часть pz1z2…zm| z1z2…zm-1(i| jm-1) из них ведет далее в i-ый узел z1z2…zm-сечение. Эти рассуждения позволяют ввести такое индуктивное определение.
Базис конструкции. Если множество аргументов пусто, то p(1) = 1. В этом случае узел -сечения - это исток бинарной программы.
Индуктивное построение. Пусть для некоторой последовательности z аргументов pz(j) есть доля путей из истока в j-ый узел z-сечения, y - это новая переменная и pzy|z(i | j) - доля путей, ведущих из в j-го узла z-сечения в i-ый узел zy-сечения. Тогда pzy(i) = j pzy|z(i | j) pz(j).
Это определение распространяется на произвольные множества аргументов y и z следующим образом.
pyz(i) = j pyz|y(i | j) py(j).
Пусть z = z u и мы уже получили, что pyz(h) = j pyz |y(h | j) py(j). По определению
pyzu(i) = h=1,q pyzu |yz(i | h) pyz(h) = h=1,q pyzu |yz(i | h) j=1,k pyz |y(h | j) py(j) =
h=1,q,j=1,k pyzu |yz(i | h) pyz |y(h | j) py(j).
Известно, что h=1,q pyzu |yz(i | h) pyz |y(h | j) = pyzu |y (i | j). Следовательно,
pyzu(i) = j=1,k pyzu |y (i | j) py(j).
Справедливо утверждение.
Теорема 2. Справедливо равенство i=1,h pz(i) = 1, где суммирование ведется по всем узлам z-сечения.
Доказательство. Пусть pu(j) есть известная доля путей из истока в узел j u-сечения, y - это переменная, z = uy и j=1,k pu ( j) = 1. По определению, puy(i) = j=1,k puy|u(i | j) pu(j), где puy|u(i | j) - относительная доля путей, ведущих из j-го узла u-сечения в i-ый узел uy-сечения. Следовательно, произведение puy|u(i | j) pu(j) есть доля путей из истока в в i-ый узел uy-сечения, проходящих через j-ый узел u-сечения.
i=1,h puy(i) = i=1,h j=1,k puy|u(i | j) pu(j) = j=1,k(i=1,h puy|u(i | j)) pu(j) = j=1,k pu(j) = 1.
При доказательстве мы использовали равенства i=1,h puy|u(i | j) = 1 и j=1,k pu(j) = 1.
Теорема доказана.
Назовем логической энтропией функции f, определяемой переменными y, величину
Hfy = -i=1,k py(i) log py(i),
где суммирование ведется по всем узлам y-сечения.
Из определения логической энтропии следует, что в общем случае ее значение зависит от порядка означивания переменных y в бинарной программе. Это поясняют примеры 1 и 2. Опишем класс логических функций, для которых логическая энтропия Hfy определяется лишь видом множества y переменных и не зависит от порядка их означивания.
Справедливо следующее утверждение.
Лемма 3. Пусть f(x, w) представляет всюду вычислимую функцию w = (x) и y x. Тогда разложение этой функции по переменным y приводит к одному выражению с точностью до перестановки конъюнктивных и дизъюнктивных членов.
Доказательство следует из того, что при любом означивающем y-наборе y в разложении присутствует конъюнкция, первым членом которой является конъюнкт yy и вторым функция, которая получается из f(x, w) в результате этого означивания.
Теорема 4. Значение Hfy не зависит от порядка означиваний переменных y, а определяется только множеством y.
Из этого следует, что логическая энтропия Hfy функции f(Y, w), представляющей физическую систему w = (Y), где - всюду определенная функция совпадает с ее энтропией, определяемой переменными y, как она введена в [1].
Если же функция f(Y, w) представляет не всюду определенную вычислимую функцию, то логическая энтропия зависит от порядка означивания переменных.
Если ясно, о какой функции идет речь, то в обозначении Hfy будем опускать верхний индекс.
Понятие логической энтропии введено, исходя из представления бинарной программы как некоторого вычислителя. Тем самым она выступает мерой неопределенности процесса вычисления. Ту же формулу можно получить в результате несколько иных рассуждений. Как следствие получим, что логическая энтропия служит и мерой сложности функции.
Определим по функции f(y, z) отношение y-эквивалентности y-наборов:
1y 2y f(1y, z) = f(2y, z).
При этом говорим, что функция f(1y) определяется тем классом эквивалентности, которому принадлежит y-набор 1y.
Пусть число всех классов y-эквивалентности равно k: 1, 2, …, k; 11 1, 21 2, …, k1 k суть представители этих классов и есть множество всех единичных означиваний функции f(iy, z), i = 1, 2, …, k. Назовем множество i означиваний - порождаемым i-ым классом y-эквивалентности. Пусть есть множество всех единичных означиваний функции f(y, z). Тогда y-эквивалентность определяет разбиение множества на k не пересекающихся подмножеств: = i=1,k i , i = 1, 2, …, k - по числу классов эквивалентности.
Функции f(iy, z), i = 1, 2, …, k, связаны с исходной функцией f(y, z) очевидным образом:
f(y, z) = i=1,k (y1i y2i … ymi) f(i1, z).
Здесь 1i, 2i, …, mi - означивания переменных у, составляющие i-ый класс эквивалентности, i = 1, 2, …, k, они определяют одну функцию f(i1, z), (обозначим её fi).
Представим функцию f(y, z) следующим образом:
f(y, z) = i=1,k [yi] fi,
где [yi] обозначает дизъюнкцию конъюнктов, определяемых всеми у-наборами одного класса эквивалентности i = {1i, 2i, …, mi}, i = 1, 2, …, k.
Разлагая каждую функцию f(i1, z) по переменным z, получим равенство
f(y, z) = i=1,k j=1,h [yi] [zj] f(1i, 1j) = i=1,k j=1,h [yi] [zj] fij.
Сокращенно это разложение обозначим так: f(y, z) = i=1,k j=1,h [yizj] fij. Множества 1, 2, …, k попарно не пересекаются, но множества 1, 2, …, h могут пересекаться.
Мы рассматриваем логические функции, представляющие лишь всюду определенные вычислимые функции. Поэтому каждая функция fij не равна тождественному нулю, i = 1, 2, …, k, j = 1,2, …, h. Несколько различных пар (i, j) индексов могут определять эквивалентные логические функции fij. Перечислим все классы yz-эквивалентности. Пусть t-ый класс yz-эквивалентности характеризуется множеством {(i, j1), (i, j2), …, (i, jq)} пар индексов в разложении функции f(y, z). Тогда мы говорим, что t-ый класс yz-эквивалентности порожден i-ым классом y-эквивалентности.
Разложение функции f(y, z) по переменным y и z, можно представить ее в виде матрицы Mf, как на рис.5.
zу |
1 |
2 |
3 |
… |
|
|
1 |
f11 |
f12 |
f13 |
… |
|
|
2 |
f21 |
f22 |
f23 |
… |
|
|
3 |
f31 |
f32 |
f33 |
… |
|
|
… |
… |
… |
… |
… |
Рис. 5
Здесь fij обозначает функцию f(1i, 1j), i-ая строка соответствует i-му классу y-эквивалентности, i=1, 2, …, k, j-ый столбец - j-му классу z-эквивалентности, j=1, 2, …, h. В общем случае нескольким парам (i, j), где i - номер столбца и j - номер строки, может соответствовать один класс эквивалентности yz-наборов. Но число классов yz-эквивалентности не больше числа таких различных пар. Все порожденные одним i-м y-классом yz-классы характеризуются эквивалентными функциями из одной i-ой строки.
Введем теперь показатель, аналогичный тому, который использовался при исследовании бинарных программ.
Определим pyz|y(j|i) как условную долю j-го yz-класса, порожденного i-м y-классом среди всех yz-классов, порожденных i-м y-классом. Из разложения функции f по переменным и определения бинарной программы понятно, что все введенные ранее равенства относительно условных и абсолютных долей сохраняются при новой интерпретации. В частности, определение абсолютной доли py(i) i-го y-класса среди остальных y-классов выглядит так.
Базис конструкции. При пустом множестве аргументов имеется единственный класс эквивалентности, который определяется самой функцией f и поэтому доля его p(1) = 1.
Индуктивное построение. Пусть для некоторой последовательности z аргументов pz(j) есть доля j-го класса z-эквивалентности среди остальных z-классов, y - это новая переменная и pzy|z(i | j) - доля i-го zy-класса среди всех zy-классов, порожденных j-м z-классом. Тогда pzy(i) = j pzy|z(i | j) pz(j).
Рассмотрим однородную бинарную программу f для функции f(y). Пусть N1, N2, …, Nk - суть все узлы y-сечения и Т1, Т2, …, Тk - совокупности путей, проходящих из истока программы в узлы соответственно N1, N2, …, Nk, причем мощности множеств Т1, Т2, …, Тk равны соответственно t1, t2, …, tk и t = i=1,k ti. Каждый узел Ni соответствует, с одной стороны, в точности одному классу у-эквивалентности, а с другой, - единственной логической функции, определяемой всяким у-набором из этого класса у-эквивалентности. По определению, доля py(i) всех наборов, определяемых одним классом у-эквивалентности, соответствующего узлу Ni, совпадает с долей py(i) путей из истока в i-ый узел y-сечения. i = 1, 2, …, k.
...Подобные документы
Способы передачи и хранения информации наиболее надежными и экономными методами. Связь между вероятностью и информацией. Понятие меры количества информации. Энтропия и ее свойства. Формула для вычисления энтропии. Среднее количество информации.
реферат [99,7 K], добавлен 19.08.2015Механизм передачи информации, ее количество и критерии измерения. Единицы информации в зависимости от основания логарифма. Основные свойства и характеристики количества информации, ее энтропия. Определение энтропии, избыточности информационных сообщений.
реферат [33,9 K], добавлен 10.08.2009Объединение как совокупность нескольких ансамблей дискретных, случайных событий. Безусловная энтропия - среднее количество информации, приходящееся на один символ. Описание информационных свойств непрерывного источника. Понятие дифференциальной энтропии.
контрольная работа [106,8 K], добавлен 28.07.2009Выделение подсистем на основе некоторой меры. Выбор типов шкал. Метод логического ранжирования. Построение моделей систем. Динамическая модель системы в виде сети Петри. Элементарные контуры графа системы. Расчет энтропии системы и матрицы приоритетов.
курсовая работа [1,2 M], добавлен 06.08.2013Количество информации и ее мера. Определение количества информации, содержащегося в сообщении из ансамбля сообщений источника. Свойства количества информации и энтропии сообщений. Избыточность, информационная характеристика источника дискретных сообщений.
реферат [41,4 K], добавлен 08.08.2009Определение энтропии как меры стойкости паролей, способ противодействия их взлому. Вычисление веса и информационной емкости пароля с помощью SeaMonkey, Password Strength Tester. Алгоритм работы дежурного и вспомогательного анализаторов от Microsoft.
курсовая работа [632,8 K], добавлен 18.06.2011Предмет и задачи теории информации, ее функции при создании АСУ. Определение пропускной способности дискретных (цифровых) каналов при отсутствии шумов. Расчет скорости передачи информации. Вычисление значения энтропии - среднего количества информации.
контрольная работа [112,0 K], добавлен 18.01.2015ERwin как средство разработки структуры базы данных. Внешний вид диалогового окна Entity Edition. Общий вид модели после создания сущностей. Вид логической модели после создания связей. Диалоговое окно New Key Group, окончательный вид логической модели.
лабораторная работа [559,0 K], добавлен 16.07.2013Система передачи информации. Использование энтропии в теории информации. Способы преобразования сообщения в сигнал. Динамический диапазон канала. Определение коэффициента модуляции. Преобразование цифровых сигналов в аналоговые. Использование USB–модемов.
курсовая работа [986,3 K], добавлен 18.07.2012Реализация интегрирования функции методами прямоугольников, трапеций, Симпсона. Построение графика сравнения точности решения методов интегрирования в зависимости от количества разбиений. Алгоритм расчета энтропии файлов с заданным расширением.
контрольная работа [1011,0 K], добавлен 04.05.2015Исследование спецификации логической игры "Сапёр". Системное и функциональное проектирование приложения. Разработка программных модулей. Обзор классов, необходимых для создания интерфейса данного приложения. Инструменты для реализации логической игры.
курсовая работа [1,2 M], добавлен 13.01.2016Построение логической модели определенного вида по выборке данных указанного объема, которая содержит информацию о трех входах системы и одном выходе, и представлена в виде матрицы размерностью 30х4. Поверка адекватности этой модели по заданному критерию.
дипломная работа [20,0 K], добавлен 13.08.2010Базы данных - важнейшая составная часть информационных систем. Проектирование базы данных на примере предметной области "Оргтехника". Сбор информации о предметной области. Построение информационно-логической модели данных. Разработка логической структуры.
курсовая работа [318,6 K], добавлен 24.12.2014Вычисление количества информации, приходящейся на один символ по формуле Шеннона. Изменения информационной энтропии в текстах экономического, естественнонаучного и литературного содержания. Максимальное количество информации на знак по формуле Хартли.
лабораторная работа [28,2 K], добавлен 06.12.2013Разработка программы "Сапер", удовлетворяющей необходимым требованиям эффективности в интегрированной среде программирования Microsoft Visual C++. Специфика создания Windows-приложений. Применение логической игры для развития интереса к обучению у детей.
курсовая работа [511,1 K], добавлен 01.06.2013Логика высказываний и предикатов. Построение таблицы истинности для логической формулы. Обоснование выбора структур данных. Описание алгоритма решения задачи. Описание пользовательского интерфейса. Окно командной строки, для ввода логической формулы.
курсовая работа [437,7 K], добавлен 10.04.2017Практическая разработка информационно-логической модели автоматизируемой предметной области "Отрасль печати". Построение логической структуры информационной базы организаций отрасли печати. Проектирование и описание целостного приложения базы информации.
курсовая работа [1,8 M], добавлен 18.12.2012Процесс вскрытия системы связи при проведении противником несанкционированного мониторинга. Правила преобразований для формирования защищенной функционально-логической структуры системы связи. Способ защиты вычислительной сети с выделенным сервером.
дипломная работа [5,4 M], добавлен 21.12.2012Разработка приложения на WinAPI с реализацией логической структуры в игре "Сапер". Реализация графической части приложения. Проверка на корректность поведения интерфейса программы, работы логической части игры, корректности записи и чтения файла.
курсовая работа [1,1 M], добавлен 17.10.2012Понятие автоматизированных информационных систем, их достоинства и недостатки. Анализ бизнес-процессов детского центра. Построение моделей в нотациях IDEF0, DFD, IDEF3 (в программе PBwin). Разработка логической структуры базы данных в СУБД MS Access.
курсовая работа [2,5 M], добавлен 25.06.2013
