Логическая энтропия
Рассмотрение логической энтропии как меры неопределенности и сложности информационных моделей, описываемых булевскими функциями. Приводятся содержательные интерпретации логической энтропии. Отличие логической энтропии от энтропии Теории информации.
| Рубрика | Программирование, компьютеры и кибернетика |
| Вид | статья |
| Язык | русский |
| Дата добавления | 28.10.2018 |
| Размер файла | 196,5 K |
Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
При таком определении абсолютной доли, выполняется теорема, аналогичная Теореме 1.
Теорема 5. Имеет место равенство i pz(i) = 1.
Если мы рассматриваем логические функции, представляющие всюду определенные вычислимые функции, то верно следующее утверждение.
Лемма 6. Пусть py(i) есть доля i-го класса y-эквивалентности, qz(j) - доля j-го класса z-эквивалентности. Тогда доля yz-наборов, которые характеризуются принадлежностью y-наборов i-му классу y-эквивалентности и z-наборов j-му классу z-эквивалентности среди всех yz-наборов равна произведению рy(i)qz(j), i = 1, 2,…, k, j = 1, 2, …, h.
Доказательство. Все логические функции fij, i=1, 2, …, k, j=1, 2, …. h не являются тождественно нулевыми. Следовательно, для каждого y-набора ri i и для каждого z-набора qj j все конъюнкты вида yrizqj входят в разложение исходной функции.
Лемма доказана.
С другой стороны, если рассматривать логические функции, представляющие не всюду определенные функции, то утверждение места не имеет. Действительно, в этом случае некоторые функции матрицы Mf могут быть тождественно нулевыми и, следовательно, для y-набора ri i для некоторых z-наборов qj j конъюнкты вида yrizqj могут не входить в разложение исходной функции. Следовательно, не все yz-наборы, у которых y-наборы из класса i, характеризуются принадлежностью z-наборов какому-либо классу z-эквивалентности.
Сложность зависимости функции f(y) от переменных y характеризуется фактор-множеством у-эквивалентности. Действительно, чем больше фактор-множество, тем больше различных подформул встречается в разложении логической функции по этим переменным. В терминах бинарной программы мощности фактор-множества у-эквивалентности соответствует число узлов у-сечения.
Если py(i) есть доля путей, проходящих из истока в i-ый узел y-сечения, то обратная величина ty(i) = 1/ py(i) пропорциональна числу путей, ведущих из истока в этот узел, i = 1,2, …, k. i=1,k py(i) log ty(i) есть математическое ожидание случайной величины log ty(i), i = 1,2, …, k, с распределением py(i).
Введем следующее определение.
Эффективной пропускной способностью одного узла у-сечения бинарной программы назовем величину , такую, что log = i=1,k py(i) log ty(i). Таким образом, эффективную пропускную способность можно представлять как математическое ожидание величины, пропорциональной числу путей, проходящих через один узел y-сечения. Поэтому эффективная пропускная способность отличается от «реальной» некоторой аддитивной константой. Если доли py(i) одинаковы, то log = logt . В этом случае эффективная пропускная способность совпадает с числом путей из истока, которые проходят через один узел y-сечения.
Введем величину t = i=1,k ty(i) которая пропорциональна общему числу путей, ведущих из истока в y-сечение. Величину Нy = log (t/) назовем эффективным у-сечением. Тем самым эффективное у-сечение есть мера сложности бинарной программы, расположенной выше у-сечения: при большем эффективном сечении Нy и при постоянном числе всех путей из истока в у-сечение, среднее число путей, проходящих через один узел сечения, мало, а число узлов в сечении - велико. Но чем шире у-сечение, тем сложнее зависимость логической функции от переменных у, так как число различных подформул, участвующих в разложении функции по переменным у больше. Поэтому зависимости исходной функции от переменных у выражается сложнее.
Нy = log (t/) = log t - log = log t - i=1,k py(i) log ty(i)
= -i=1,k (ty(i)/t) log (ty(i)/t) = -i=1,k py(i) log py(i).
Как видно, величина эффективного y-сечения и энтропии логической функции совпадают. Заметим, что энтропия получена из определения неопределенности выходных значений от входных, а эффективное сечение получено из анализа сложности зависимости функции от ее аргументов.
2. Некоторые интерпретации логической энтропии. Поясним с содержательной точки зрения понятие логической энтропии.
Пусть f(y, z) есть логическая функция и (у) есть функция, значение которой от аргументов у равно номеру того класса у-эквивалентности, которому принадлежит кортеж у. Обозначим долю таких y-наборов, при которых значение функции (у) равно i, i = 1, 2, …, k, среди всех наборов через pi. Будем говорить, что переменные у имеют распределение pу(1), pу(2), …, pу(k). Понятно, что i=1,k pу(i) = 1. Назовем функцию, которая получается из f(y, z) подстановкой y-наборов из i-го класса эквивалентности - соответствующей значению pi. Следовательно, показатель неожиданности -log2 pi функции (у) зависит от доли наборов, определяемых i-м классом у-эквивалентности. Чем больше наборов в i-м классе, тем меньше неожиданность того, что конкретное означивание ему принадлежит. В терминах бинарной программы это выглядит так: чем больше путей определяется одним классом у-эквивалентности, тем большая доля вычислений осуществляется промежуточным вычислителем, который соответствует данному классу и ассоциируется с соответствующим узлом у-сечения программы. Логическая энтропия, определяемая переменными у, есть усредненная неожиданность того, что конкретное вычисление будет реализовываться промежуточным вычислителем, соответствующим конкретному классу у-эквивалентности (в терминах бинарной программы - некоторому узлу y-сечения).
В теории информации энтропия служит мерой свободы системы: чем больше у системы степеней свободы, т.е. чем меньше на нее наложено ограничений, тем больше ее энтропия. Поэтому энтропия максимальна при одинаковой доле наблюдаемых событий, а всякое отклонение от него приводит к ее уменьшению. В пределе, когда доля одного события равна 1, энтропия равна нулю. Применительно к логической энтропии, под степенями свободы понимается число классов у-эквивалентности. Чем их меньше, тем больше определенность, какой промежуточный вычислитель используется для продолжения вычисление. И наоборот, чем больше классов эквивалентности и чем однороднее доли p1, p2, …, pk, тем больше возможностей для выбора того или иного промежуточного вычислителя и, следовательно, больше неопределенность.
В терминах сложности логической функции эти рассуждения выглядят так: если переменные y определяют небольшое фактор-множество, то они описывают лишь небольшое число различных свойств логической функции. Очевидно, что для описания небольшого числа свойств требуется меньше параметров (в нашем случае - аргументов) и наоборот, чем разнообразнее проявления системы, тем больше параметров необходимо для ее описания. При прочих равных условиях, более сложная система наблюдателю кажется менее определенной и наоборот, чем больше определенности у наблюдателя, тем проще зависимость демонстрируемого поведения системы от входных параметров. В данном контексте под сложностью зависимости системы от аргументов y понимается число классов у-эквивалентности. Это согласуется с определением неопределенности функции от переменных у, как сложности зависимости от этих аргументов. Чем меньше классов у-эквивалентности, тем, с одной стороны, меньше средний показатель неожиданности, а с другой, - тем проще выражается зависимость функции от этих аргументов. Если же классов эквивалентности много, то больше средний показатель неожиданности и функция сложнее зависит от аргументов у. Тем самым, чем больше энтропия Нy, тем сложнее выражается зависимость функции от аргументов у и наоборот.
Приведем теперь интерпретацию логической энтропии с позиций статистической модели равновероятных последовательностей. Для этого представим логическую функцию f(y, z) таблицей истинности, в которой приведены лишь ее единичные означивания. Разложение по y выглядит следующим образом:
f(y, z) = i=1,k [yi] f(i1, z).
Полагаем, что все переменные y случайны и независимы, и py(i), i = 1, 2, …, k, есть доля наборов, включающих y-поднаборы из i-го класса y-эквивалентности в достаточно большом случайно порожденном множестве единичных означиваний, мощность которого равна N. Тогда число наборов, обладающих y-поднаборами из i-го класса y-эквивалентности, равно Ni = N py(i).
По закону больших чисел во всяком достаточно большом подмножестве единичных означиваний доля означиваний, порожденных i-м классом y-эквивалентности совпадает с py(i), i = 1, 2, …, k и доли наборов, порожденных каждым из k классов y-эквивалентности, не зависят от вида множества единичных означиваний. Поэтому из N наборов Ni = N py(i) порождены i-м классом и вероятность выбора такого множества единичных означиваний, которая характеризуется распределением py(i), i = 1, 2, …, k, по классам y-эквивалентности, равна q = py(1)N1py(2)N2 … py(k)Nk = (py(1)py(1)py(2)py(2) … py(k) py(k))N. Неопределенность H* всего множества единичных означиваний равна - log q. Поэтому H* = -N i=1,k py(i) log py(i). Но тогда -i=1,k py(i) log py(i) = H*/N представляет собой среднюю неопределенность, которая приходится на единственное единичное означивание.
Тем самым, получили еще одну интерпретацию логической энтропии: формула -i=1,k py(i) log py(i) определяет среднюю неопределенность, которая приходится на одно единичное означивание функции f(y, z), если их классификация осуществляется с помощью y-эквивалентности при достаточно большом числе независимо порожденных единичных означиваний.
Наконец, еще одна трактовка логической энтропии основывается на следующих рассуждениях.
Пусть y-эквивалентность порождает k классов. Присвоим каждому из N единичных означиваний функции f(y, z) номер того класса из {1, 2, …, k}, порождением которого он является. Число различных перестановок N единичных означиваний из которых Ni = N pi обладают номером i, равно
.
Тогда энтропия этого случайного множества
H* = log M = log N! - i=1,k log Ni!.
По формуле Стирлинга
.
Полагая, что N достаточно велико, имеем
H* = N log N - i=1,k Ni log Ni = i=1,k Ni log N - i=1,k Ni log Ni = - N i=1,k py(i) log py(i).
В этом случае энтропия
- i=1,k py(i) log py(i) = (1/N) log M
есть средняя неопределенность, которая приходится на одно единичное означивание при их случайном порождении.
Последние интерпретации логической энтропии проясняют ее поведенческую природу. Под N понимается число проводящих путей бинарной программы из истока в сток. Тогда Ni есть число таких путей, проходящих через i-ый узел y-сечения, pi - доля этих путей. M есть число способов распределения вычислений по k промежуточным вычислителям, соответствующих узлам y-сечения, при условии, что на i-ый вычислитель приходится pi-ая доля всех вычислений. Но тогда log M / N есть средняя неопределенность того, на каком вычислителе будет обрабатываться отдельная последовательность аргументов.
Если k = 1, то неопределенность равна 0. Если k возрастает, то возрастает и величина max(-i=1,k py(i) log py(i)). То есть неопределенность отнесения того или иного единичного означивания к соответствующему классу растет.
Из последнего определения следует, что логическая энтропия представляет собой информацию, которую мы получаем об одном единичном означивании, при известном разложении функции по переменным y. Единичные означивания, порожденные одним классом y-эквивалентности на промежуточном этапе разложения по y не различимы с точностью до y- эквивалентности. Они характеризуются одним номером класса. Следовательно, информация, которая приходится на одно означивание при известном разложении по переменным y касается именно принадлежности к классу эквивалентности.
Достаточно очевидна аналогия такого представления с представлением энтропии в Теории информации как меры информации, которая передается одним символом сообщения,. В нашем случае каждое единичное означивание является носителем сигнала, который указывает на принадлежность соответствующего y-набора конкретному классу эквивалентности.
Пример 3. Опишем два класса логических функций. Первый называется локальным и характеризуется энтропией, не зависящей от переменных y, определяющих сечение бинарной программы. Второй обладает энтропией, линейно зависящей от мощности множества y переменных не зависимо от порядка их означивания.
Первый класс функций описан в [2]. Для них доказана ограниченность сечения бинарных программ при некотором порядке означивания переменных. Содержательно это значит, что между переменными функций из этого класса имеется большое число зависимостей или, что эквивалентно, такие функции обладают небольшим числом подфункций.
С другой стороны в [2] описан класс не локальных функций, для бинарных программ которых любое y-сечение (когда число переменных y не превосходит половины от числа всех аргументов) содержит не менее узлов, где c - положительная константа. При этом доли путей, ведущих в разные узлы y-сечения, совпадают. Отсюда следует, что логическая энтропия, определяемая такими множествами аргументов, пропорциональна | y |. Содержательно это обозначает, что для таких функций, их аргументы по большей части попарно независимы или, что эквивалентно, они обладают большим числом подфункций.
Если говорить о том, какова логическая энтропия большинства логических функций, то отметим, что для почти всех логических функций сложность реализации контактными схемами ограничена снизу экспонентой от числа переменных. Следовательно, почти все логические функции при любом построении бинарных программ обладают максимальной энтропией, сравнимой с общим числом их переменных.
Литература
1. Брошкова Н.Л., Попов С.В., О проектировании информационных систем. Препринт ИПМ РАН им. М.В.Келдыша, 2005.
2. Брошкова Н.Л., Попов С.В., О локальности информационных систем. Препринт ИПМ РАН им. М.В. Келдыша, 2005.
3. Шеннон К. Работы по теории информации и кибернетике, М.: ИЛ. 1963, - 830 с.
4. Колмогоров А.Н. Теория информации и теория алгоритмов, М.: Наука, 1987, - 303 с.
5. Файнстейн А. Основы теории информации. М.: ИЛ, 1960. - 140 с.
Размещено на Allbest.ru
...Подобные документы
Способы передачи и хранения информации наиболее надежными и экономными методами. Связь между вероятностью и информацией. Понятие меры количества информации. Энтропия и ее свойства. Формула для вычисления энтропии. Среднее количество информации.
реферат [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
