Двоичная логарифмическая мера

Существует несколько подходов к измерению информации.

Комбинаторная мера

Для лучшего понимания рассмотрим несколько простейших примеров.

Пример 1 . Проведем опыт. Возьмем игральный кубик. Он имеет шесть сторон, на каждой из которых изображены числа от одного до шести.

Подбросим его. При бросании кубика выпадает одно из имеющихся на сторонах кубика число. Получившееся таким образом число - есть исход нашего опыта.

Подбрасывая игральный кубик сколь угодно раз, мы можем получить только шесть возможных чисел. Обозначим это как N = 6.

Этот пример позволяет перейти к понятию комбинаторной меры информации и дать следующее определение:

Комбинаторная мера информации N - это способ измерения количества информации путем оценки количества возможных комбинаций информационных элементов.

Поскольку в примере с игральным кубиком возможно только шесть вариантов исхода опыта, иными словами, шесть комбинаций, то и количество информации в соответствии с комбинаторной мерой составляет N = 6 комбинаций.

Рассмотрим следующий пример.

Пример 2. Пусть задана одна из десятичных цифр, например, цифра 8 и одна из шестнадцатеричных – к примеру, цифра 6 (можно было взять любую другую шестнадцатеричную - 8, В, F и т. д.). Теперь, в соответствии с определением комбинаторной меры, определим количество информации, заключенное в каждой из этих цифр. Поскольку цифра 8 является десятичной, а значит, представляет один символ из десяти, то N 8 = 10 комбинаций. Аналогично, цифра 6 представляет один из шестнадцати символов, а поэтому N 6 = 16 комбинаций. Следовательно, что шестнадцатеричная цифра содержит больше информации, чем десятичная.

Из рассмотренного примера можно сделать вывод, что чем меньше цифр находится в основании системы счисления, тем меньше информации несет в себе один ее элемент.

Двоичная логарифмическая мера

Английский инженер Р. Хартли предложил измерять количество информации двоичной логарифмической мерой:

где N - количество различных комбинаций информационных элементов. Единицей измерения информации при таком измерении является бит.

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

Подсчет дает следующие результаты:

в примере с кубиком I = log 2 6 = 2,585 бит;

в примере с десятичной системой счисления I = log 2 10 = 3,322 бит;

в примере с шестнадцатеричной системой счисления I = log 2 16 = 4 бит;

в примере с двоичной системой счисления I = log 2 2 = 1 бит.

Последняя цифра говорит о том, что в каждой цифре двоичной системы счисления содержится один бит информации. Вообще, в технических системах двоичная система счисления применяется для кодировки двух возможных состояний, например 1 обозначает наличие электрического тока в сети, 0 - его отсутствие.

Во всех рассмотренных выше примерах исходы опытов были равновероятными и взаимно независимыми. Это означает, что при подбрасывании кубика каждая из шести граней имеет одинаковую вероятность результативного исхода. А также, что результат следующего подбрасывания никак не зависит от результата предшествующего.

Равновероятные и взаимно независимые события в реальной жизни встречаются довольно редко. Если обратить внимание на разговорные языки, например русский, то можно сделать интересные выводы. Для упрощения теоретических исследований в информатике принято считать, что русский алфавит состоит из 32 символов (е и ё, а также ь и ъ между собой не различаются, но добавляется знак пробела между словами). Если считать, что каждая буква русского языка в сообщении появляется одинаково часто и после каждой буквы может стоять любой другой символ, то можно определить количество информации в каждом символе русского языка как:

I = log 2 32 = 5.

Однако, фактически все бывает не так. Во всех разговорных языках одни буквы встречаются чаще, другие - гораздо реже. Исследования говорят, что на 1000 букв приходится следующее число повторений:

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

Эта мера определяет полезность информации (ценность) для достижения пользователем поставленной цели.

В основе всей теории информации лежит открытие, сделанное Р. Хартли в 1928 году, и состоящее в том, что информация допускает количественную оценку.

Подход Хартли основан на фундаментальных теоретико-множественных, по существу комбинаторных основаниях, а также нескольких интуитивно ясных и вполне очевидных предположениях.

Если существует множество элементов и осуществляется выбор одного из них, то этим самым сообщается или генерируется определенное количество информации. Эта информация состоит в том, что если до выбора не было известно, какой элемент будет выбран, то после выбора это становится известным. Необходимо найти вид функции, связывающей количество информации, получаемой при выборе некоторого элемента из множества, с количеством элементов в этом множестве, то есть с его мощностью. измерение алгоритмический прагматический байт

Если множество элементов, из которых осуществляется выбор, состоит из одного единственного элемента, то ясно, что его выбор предопределен, то есть, никакой неопределенности выбора нет - нулевое количество информации.

Если множество состоит из двух элементов, то неопределенность выбора минимальна. В этом случае минимально и количество информации.

Чем больше элементов в множестве, тем больше неопределенность выбора, тем больше информации.

Количество этих чисел (элементов) в множестве равно: N=2i

Из этих очевидных соображений следует первое требование: информация есть монотонная функция от мощности исходного множества.

Выбор одного числа дает нам следующее количество информации: i=Log 2 (N)

Таким образом, количество информации, содержащейся в двоичном числе, равно количеству двоичных разрядов в этом числе.

Это выражение и представляет собой формулу Хартли для количества информации.

При увеличении длины числа в два раза количество информации в нем так же должно возрасти в два раза, не смотря на то, что количество чисел в множестве возрастает при этом по показательному закону (в квадрате, если числа двоичные), то есть если N2=(N1)2, то I2=2*I1,

F(N1*N1)=F(N1)+F(N1).

Это невозможно, если количество информации выражается линейной функцией от количества элементов в множестве. Но известна функция, обладающая именно таким свойством: это Log:

Log 2 (N2)=Log 2 (N1)2=2*Log 2 (N1)

Это второе требование называется требованием аддитивности.

Таким образом, логарифмическая мера информации, предложенная Хартли, одновременно удовлетворяет условиям монотонности и аддитивности. Сам Хартли пришел к своей мере на основе эвристических соображений, подобных только что изложенным, но в настоящее время строго доказано, что логарифмическая мера для количества информации однозначно следует из этих двух постулированных им условий.

Пример. Имеются 192 монеты. Известно, что одна из них фальшивая, например, более легкая по весу. Определим, сколько взвешиваний нужно произвести, чтобы выявить её. Если положить на весы разное количество монет, то получим три независимые возможности: а) левая чашка ниже; б) правая чашка ниже; в) чашки уравновешены. Таким образом, каждое взвешивание дает количество информации I=log23, следовательно, для определения фальшивой монеты нужно сделать не менее k взвешиваний, где наименьшее k удовлетворяет условию log23k log2192. Отсюда, k 5или, k=4 (или k=5 - если считать за одно взвешивание и последнее, очевидное для определения монеты). Итак, необходимо сделать не менее пять взвешиваний (достаточно 5).

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Об обосновании логарифмической меры информации

Теория информации в настоящее время вышла за узкие рамки систем связи, где она первоначально применялась, и начала широко использоваться в таких нетрадиционных для нее областях, как физика, теория систем, теория управления, биология, математика. Особенно широкое применение она нашла в таких относительно новых областях науки, как информатика, теория автоматов, защита данных.

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

Важнейшим вопросом, на основе которого строится та или иная теория информации, является выбор меры информации.

Он во многом определяется теми объектами, на анализ которых направлена разрабатываемая теория.

В настоящее время в теории информации наибольшее распространение имеют меры Хартли и Шеннона, причем в ряде случаев меру Хартли представляют как частный случай меры Шеннона.

Однако уже по своему назначению мера Хартли имеет существенное отличие от меры Шеннона, так как первая направлена на исследование детерминированных (невероятностных) процессов конечной длины, а вторая - на анализ вероятностных процессов любой длительности, для анализа которых используются статистические методы .

Соответственно теория информации, использующая ту или иную из указанных мер, называется структурной или статистической теорией информации.

Конечность длин анализируемых массивов данных приводит соответственно к возможности подсчета их числа простым перебором или с помощью каких-либо математических методов, а также к применению для информационного анализа известных невероятностных методов, например, теории конечных предикатов или теории групп. В результате в структурной теории информации на сегодня получены методы кодирования, которые не могут быть разработаны на основе статистической теории информации.

В то же время статистическая теория позволяет получить предельные теоремы и вести информационный анализ сообщений на основе статистического набора данных, а не анализа каждого сообщения в отдельности, как это происходит в структурной теории информации.

Лежащая в основе структурной теории информации логарифмическая мера, где и - любые положительные числа конечной длины, не равные 0, а еще и не равное 1, предложенная Хартли в 1928 г., не была им логически обоснована, а вводилась на основе интуитивных соображений . Причем, что существенно, в таком виде она может принимать как положительные, при, так и отрицательные, при, значения.

В настоящее время она обосновывается свойством ее аддитивности, которое проявляется в том, что общая информация, генерируемая совместно двумя источниками информации и, равна сумме отдельных информаций и от каждого из них, как это показано, например, в .

Действительно, если каждый из двух источников и генерирует соответственно и сообщений, то их общее количество

Прологарифмировав выражение (1), получим равенство

которое доказывает свойство аддитивности меры информации Хартли.

Рассмотрим другое обоснование меры Хартли применительно к задачам поиска (непрерывного и дискретного).

Особенностью задач дискретного поиска является конечность исходного множества объектов, представляющих с равной вероятностью возможные решения задачи дискретного поиска, среди которых предположительно находится один искомый. Его поиск осуществляется в процессе решения дискретной задачи, как это происходит, например, в широко известной задаче коммивояжера.

В этой задаче искомым объектом является маршрут минимальной длины, выбираемый из некоторого исходного конечного числа возможных маршрутов.

Решение указанных задач так или иначе находится в процессе последовательных разбиений исходного множества из возможных объектов - решений на, классов эквивалентности и тестирование каждого из них на предмет наличия в нем искомого объекта. В процессе тестирование происходит устранение неопределенности о наличии искомого объекта, сопровождающееся выработкой соответствующего количества информации.

Особый случай разбиения будет тогда, когда исходные возможных объектов разбиваются на классов эквивалентности так, чтобы в них находились строго равные количества целых объектов.

Очевидно, что такие разбиения возможны только в том случае, когда

где - максимальное число разбиений до появления класса с одним объектом.

Если за меру информации в данном случае взять, то она в точности совпадает с логарифмической мерой Хартли, взятой по основанию:

Таким образом, число разбиений при равновероятном дискретном поиске объекта среди возможных представляет собой логарифмическую меру информации Хартли и, наоборот, мера Хартли представляет для рассматриваемого случая число равномерных разбиений множества из объектов на классов эквивалентности до появления одного искомого.

В общем случае при разбиении исходного множества, состоящего из объектов, на классов эквивалентности в каждом из них может содержаться объектов и соответственно вероятность нахождения искомого объекта в том или ином классе равна

При этом.

Формула Шеннона для энтропии, определяющая меру неопределенности нахождения искомого объекта в том или ином классе эквивалентности до тестирования, при первом разбиении

где утверждает, что величина энтропии достигает максимума для первого разбиения

при нахождении искомого объекта в классах эквивалентности с равными вероятностями

В данном случае.

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

Аналогично и на остальных разбиениях при равенстве вероятностей нахождения искомого объекта в новых классах эквивалентности будет получено максимальное количество информации, равное 1.

Из этого следует, что для достижения максимума генерируемой тестом информации нужно в процессе разбиений множества объектов разбивать их на классы эквивалентности с равным количеством объектов в каждом из них.

Так как мера Хартли применительно к рассматриваемой задаче использует именно такие разбиения, то это значит, что она определяет максимально возможное количество информации, получаемое в процессе поиска дискретного объекта, а раз это так, то число разбиений и соответственно время поиска должно быть при этом минимальным по сравнению с любыми другими возможными разбиениями. Именно в этом состоит принципиальная особенность меры информации Хартли.

На рис. 1 показано дерево с 3 равномерными разбиениями на 2 класса эквивалентности исходных объектов. В его вершинах проставляются содержащиеся в полученных классах эквивалентности количества объектов. В данном случае в каждой вершине генерируется максимальное количество информации

в сумме по всем разбиениям составляющее бита.

Рисунок 1 - Дерево равномерных разбиений с,

Очевидно, что число равномерных разбиений для данного случая с минимально.

Другое дерево разбиений на рис. 2 для неравномерных разбиений объектов на 2 класса эквивалентности имеет среднее число разбиений по всем возможным путям разбиений

что больше среднего числа разбиений, равного, полученного в предыдущем примере.

Это вызвано тем, что количество информации, вырабатываемое при каждом разбиении в соответствии с формулой Шеннона (6), меньше 1 бита, то есть время поиска искомого объекта не является минимальным.

При этом должно выполняться основное правило информационного поиска, которое сформулируем следующим образом.

Количество информации, необходимое для поиска одного целого искомого объекта не зависит от способа разбиения исходного множества объектов на классы эквивалентности и остается постоянным и равным.

Это значит, что какое бы не было дерево разбиений исходного множества из объектов необходимое количество информации для нахождения одного из них всегда будет одним и тем же - .

Рисунок 2 - Дерево неравномерных разбиений при, и

Разбиения на классы эквивалентности широко распространены на практике. Так, на них основывается позиционное кодирование слов и чисел, которое происходит в процессе последовательных разбиений их исходных множеств на классы эквивалентности с помощью букв и цифр, которые представляют признаки этих классов. В совокупности эти буквы и цифры образуют алфавиты, а число, на которое разбиваются исходные множества слов и цифр, представляет собой мощности этих алфавитов. Число разбиений определяет при этом длину слов и чисел.

Следовательно, каждая буква или цифра слова или числа указывает класс эквивалентности, к которому они принадлежат в том или ином разбиении.

Основное выражение для теории информации, предложенное Шенноном, имеет вид

Оно утверждает применительно к задаче поиска, что количество производимой в его процессе информации равно разности между начальной энтропией

искомого объекта и остаточной

где - остаточное число объектов, среди которых имеется искомый.

Очевидно, что в процессе разбиений и тестирования число уменьшается и в конечном итоге при

Последнее выражение представляет важное условие, которое сформулировано в как принцип унитарности.

Суть его сводится к тому, что полная информация об объекте будет получена тогда и только тогда, когда в процессе поиска будет найден один целый объект.

Если же, то это говорит о том, что информация об объекте передана приемнику частично.

Особым будет случай, для которого. Для него принимает отрицательное значение - и соответственно

Это значит, что в рассматриваемом случае, когда, при тестировании вырабатывается дополнительная информация о деталях объекта, принадлежащих теперь уже новым, ранее неисследованным классам эквивалентности. Такая процедура детализации объекта может длиться неопределенно долго. Например, в дереве разбиений на рис. 1 после вершины (класса эквивалентности), содержащий после 3-го разбиения один объект, могут идти вершины, содержащие 0,5 объекта (4-е разбиение), затем 0,25 и т.д. Каждый раз величина информации об объекте при этом увеличивается на 1 бит и может достичь любой величины.

Эта процедура подтверждает хорошо известный в науке факт, что любой объект может быть неограниченно познаваем, однако принцип унитарности при этом будет нарушен, так как и соответственно, т.е. анализируемый объект не может идентифицироваться как целостная система.

Все приведенные выше рассуждения относятся и к задачам поиска с числом объектов при условии, что в получаемых в процессе разбиений классах эквивалентности допускаются нецелые числа объектов.

Из неравенства следует, что

и соответственно

где - энтропия при;

Энтропия при.

Теорема 1. Если -е разбиение числа объектов, содержит классы эквивалентности с равным количеством объектов, то имеет место неравенство

Доказательство.

Из условия и соответственно следует, что.

Теорема доказана.

Следствие 1. Энтропия -го разбиения ограничена неравенством

Теорема 2. Если -е разбиение числа объектов при содержит классы эквивалентности с количеством объектов, то имеет место неравенство

Доказательство. Так как, то, где - количество объектов, размещенных по классам эквивалентности -го разбиения.

Из условия и соответственно непосредственно следует, что.

Теорема доказана.

Следствие 1 Остаточная энтропия ограничена неравенством

На рис. 3 в качестве примера к теоремам 1, 2 приведено дерево для трех разбиений с исходным количеством объектов. Из него видно, что классы второго разбиения содержат по 1,5 объекта, а классы третьего разбиения по 0,75 объекта, . По вертикальной оси координат на рисунке расположены номера исходных объектов, а по горизонтали величина получаемой после очередного разбиения 1, 2, 3 суммарной информации и значение остаточной информации. Величина вырабатываемой на каждом шаге информации остается при этом постоянной и максимальной:

Теорема 3.

Доказательство. Так как, то, где. Прологарифмировав последнее выражение, получим, что

Теорема доказана.

Рисунок 3 - Дерево разбиений при.

Теорема 4

Доказательство. Так как, то, где. Прологарифмировав последнее выражение, получим, что.

Теорема доказана.

Следствие 1

Так как при разбиениях числа в классах, получаемых при -м разбиении, содержится больше, а в классах -го разбиения меньше 1-го объекта, то это значит, что количество информации об объекте после -го разбиения

меньше требуемого количества, необходимого для идентификации искомого объекта, и значит он не может быть полностью определен, а после -го разбиения количество информации

поступает с избытком, и в результате определяется не только сам объект, а и некоторые его детали, что для решения задачи поиска является излишним.

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

Поэтому можно говорить о дискретной (целочисленной) мере информации, являющейся разновидностью логарифмической меры Хартли, которая представляет собой среднее число разбиений на классы эквивалентности, содержащие с равной вероятностью одинаковое количество объектов, до получения искомого. Эта мера эффективно может использоваться в задачах дискретной математики и комбинаторики, где решения представляют собой целочисленные объекты.

Однако разбиения могут производиться и на нецелое число классов эквивалентности. В этом случае можно достичь выполнения принципа унитарности для любого действительного значения, решив уравнение

относительно.

Например, при значение надо выбрать примерно равным. Тогда.

Это значит, что и соответственно количество получаемой за 3 разбиения информации будет равно

В теоретических работах часто выбирают равным, а на практике наиболее часто используют значение основания логарифма, на базе которого получена такая современная мера информации, как бит, - , то есть исходное множество объектов для этой меры состоит из, а искомый объект находится за одно разбиение на 2 класса эквивалентности, каждый из которых содержит по 1 объекту. Остаточная энтропия в этом случае равна 0 и соответственно для бита соблюден принцип унитарности.

Полученное выше значение для целого числа разбиений для исходного множества объектов, можно получить и исходя из следующих соображений.

Основание логарифма, при котором

где - целое число разбиений, которое можно найти из выражения

Соответственно

Из (25) следует, что

Например, для,

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

Определим отношение (25) как начальную плотность информации до первого разбиения:

Очевидно, что плотность информации изменяется при изменении от 1 до в пределах от 0 до 1.

Так для, начальная плотность информации

После каждого разбиения плотность информации будет определяться в соответствии с выражением

Так, для рассматриваемого выше примера после первого разбиения на два класса эквивалентности

а после второго

Из выражения (28) следует, что в случае после каждого разбиения плотность информации уменьшается и только при остается постоянной для всех разбиений и равной максимальной - 1.

Из (26) следует, что

и соответственно при

Следовательно, зная, можно определить необходимое число классов эквивалентности, на которое необходимо последовательно разбивать исходное число объектов, чтобы получить целое число разбиений. Так как при этом будет вырабатываться максимальное возможное количество информации, то это будет минимальное число разбиений при данных условиях.

Следствие 1 теоремы 4 показывает, что количество информации, вырабатываемой на -м последнем разбиении

При этом в соответствии с (16) не равно 0.

Для получения полной информации об объекте достаточно, чтобы. Тогда выражение (31) примет вид

Так как из (17) следует, что

то достичь равенства (32) можно, исходя из выражения

которое при заданном выполняется при соответствующем распределении вероятностей.

Так, например, для

и соответственно

Для достижения последнего равенства следует, чтобы вероятности и равнялись соответственно 0,15; 0,85 или 0,85; 0,15.

Это значит, что полученное во 2-м разбиении число в размере объекта разбивается во время 3-го разбиения на две пропорциональные вероятностям и части (0,225 и 1,275), которые затем анализируются тестом на предмет отношения одной из них к искомой. Вероятность их нахождения равна или, или в зависимости от их величины.

В результате будет получена полная информация об одном из объектов, однако при этом, кроме равномерных разбиений, использовалось и неравномерное.

В случае чисто логарифмической меры информации при числе исходных объектов для получения величина должна представлять собой информацию, получаемую при неполном -м разбиении объектов на две равные части так, что в каждой из них будут присутствовать элементы двух объектов. При этом энтропия будет равна 0 потому, что получаемая в процессе последнего целого -го разбиения информация будет частично идти на устранение помех при тестировании, создаваемыми элементами другого объекта.

Из рассмотренного выше следует, что информация измеряется числом разбиений множества из возможных объектов до получения одного целого искомого. Источником информации в данном случае выступает тест, который указывает класс эквивалентности, в котором находится искомый объект. При этом информация как самостоятельная сущность во время разбиений прямо себя никак не проявляет, оставаясь вне рамок измерительной процедуры (подсчета числа разбиений). В тесте она проявляет себя путем указания результатов сравнения, проявляющегося в совпадении или несовпадении признаков классов эквивалентности с соответствующими признаками, имеющимися у теста. Это значит, что тест должен заранее иметь информацию о признаках анализируемых классов эквивалентности. Его конечной функцией являются дешифрация признаков этих классов и выработка управляющих воздействий, указывающих, какой класс из анализируемых должен разбиваться на подклассы на следующем шаге разбиений, или о том, что объект найден и процедура поиска должна быть прекращена.

Существенным для поиска объекта является то, что он может однозначно быть определен только после получения всей информации о нем, что происходит только тогда, когда остаточная энтропия. Это возможно только в случае, если в процессе разбиений будет получен класс эквивалентности, содержащий один объект. В этом случае энтропия и тем самым удовлетворен принцип унитарности.

Такой случай будет тогда, когда исходное число объектов. Если, то при равномерном разбиении последний -й класс эквивалентности будет содержать меньше одного объекта, и в результате будет получена дополнительная информация, детализирующая объект и не используемая при его поиске.

На практике в задачах кодирования широко используется замена исходного числа объектов числом, что, с одной стороны, приводит к удовлетворению принципа унитарности, а с другой - к увеличению количества вырабатываемой тестом избыточной информации.

Подобные документы

Понятие и цели метода фокальных объектов - поиска новых идей путем присоединения к исходному объекту свойств или признаков случайных объектов. Активизация ассоциативного мышления как один из способов эвристического исследования в теории принятия решений.

контрольная работа , добавлен 24.12.2012

Теоретические основы первичной обработки статистической информации. Особенности определения минимального числа объектов наблюдения при оценке показателей надежности. Анализ вероятностной бумаги законов нормального распределения и распределения Вейбулла.

курсовая работа , добавлен 22.03.2010

Основные понятия и способы кодирования информации. Особенности процесса расшифровки штрих-кода. Технология и оборудование для штрихового кодирования. Использование в логистических системах технологии автоматизированной идентификации штриховых кодов.

курсовая работа , добавлен 09.05.2013

Понятие энтропии. Энтропия как мера степени неопределенности. Понятие об информации. Измерение информации. Теорема Шеннона о кодировании при наличии помех. Пример использования энтропии в прогнозировании и ее значение для прогнозирования.

реферат , добавлен 14.12.2008

Разработка экономико-математической модели и решение задачи линейного программирования с использованием математических методов. Транспортная задача в матричной постановке и ее свойства. Построение исходного допустимого плана. Критерий оптимальности.

курсовая работа , добавлен 16.01.2011

Основы математического моделирования детерминированных и стохастических объектов. Идентификация объектов управления по переходной характеристике. Получение модели методом множественной линейной регрессии и проверка ее адекватности по критерию Фишера.

курсовая работа , добавлен 14.10.2014

Простейшие алгоритмы направленного случайного поиска. Алгоритм наилучшей пробы с направляющим гиперквадратом. Многоканальный статистический оптимизатор со случайным поиском. Метод статистического градиента. Локальный случайный поиск по наилучшей пробе.

курсовая работа , добавлен 08.02.2015

Понятия и определения теории генетических алгоритмов. Математический базис изобретательской физики. Генетический алгоритм изобретательской задачи. Описание операторов генетических алгоритмов. Система мысленного поиска и слежения в сознании изобретателя.

курсовая работа , добавлен 22.05.2012

Построение математической модели двойственной задачи (системы ограничений по единичной прибыли и целевую функцию общих издержек на сырье. Определение оптимального набора цен на сырье, обеспечивающего минимум общих затрат на сырье. Анализ переменных.

контрольная работа , добавлен 18.05.2015

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

Структурная мера информации

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

При структурном подходе различаются:

1) Геометрическая мера — предполагает измерение параметра геометрической модели информационного сообщения (длины, площади, объема…) в дискретных единицах.

Информационная емкость модели – максимально возможное количество информации – определяется как сумма дискретных значений по всем измерениям (координатам).

2) Комбинаторная мера – количество информации определяемое как число комбинаций элементов.

3) Аддитивная мера – (мера Хартли) – количество информации измеряется в двоичных единицах – битах.

Используются понятия:

Глубина q числа – количество символов, принятых для представления информации. В каждый момент времени реализуется только один какой-либо символ.

Длина n числа – количество позиций, необходимых и достаточных для представления чисел заданной величины.

При заданных глубине и длине числа количество чисел, которые можно представить N = qn.

Логарифмическая величина: I = log2N =n log2q (бит) — мера Хартли.

Таким образом, количество информации, которое содержит сообщение, закодированное с помощью знаковой системы, равно количеству информации, которое несет один знак, умноженному на количество знаков.

За единицу количества информации принимается такое количество информации, которое содержит сообщение, уменьшающее неопределенность в два раза. Это бит.

Структурное — рассматривает дискретное строение массивов информации и их измерение простым подсчетом информационных элементов. (Простейшее кодирование массивов — комбинаторный метод.)

Структурные меры информации

Структурные меры учитывают только дискретное строение информации. Элементами информационного комплекса являются кванты — неделимые части информации. Различаютгеометрическую , комбинаторную и аддитивную меры.

Определение информации геометрическим методом представляет собой измерение длины линии, площади или объема геометрической модели информационного комплекса в количестве квантов. Максимально возможное число квантов в заданных структурных габаритах определяет информационную емкость системы . Информационная емкость есть число, указывающее количество квантов в полном массиве информации. Согласно рис. 1.2, г , количество информации М в комплексе X (T,N ), определенное геометрическим методом, равняется

Х, Т, N — интервалы, через которые осуществляются дискретные отсчеты.

В комбинаторной мере количество информации вычисляется как количество комбинаций элементов. Здесь учитываются возможные или реализованные комбинации.

Во многих случаях дискретное сообщение можно рассматривать как слово, состоящее из некоторого количества элементов n, заданных алфавитом, состоящим из т элементов-букв. Определим количество различных сообщений, которые можно образовать из данного алфавита. Если сообщение состоит из двух элементов (п= 2), то всего может быть различных сообщений. Например, из десяти цифр (0, 1, 2,…, 9) может быть образовано сто различных чисел от 0 до 99. Если количество элементов равно трем, то количество различных сообщений равно и т.д.

Таким образом, число возможных сообщений определяется:

где L — число сообщений; п — число элементов в слове; т — алфавит.

Чем больше L , тем сильнее может отличаться каждое сообщение от остальных. Величина L может быть принята в качестве меры количества информации. Однако выбор L в качестве меры количества информации связан с неудобствами: во-первых, при L =1 информация равна нулю, поскольку заранее известен характер сообщения (т.е. сообщение есть, а информация равна нулю); во-вторых, не выполняется условие линейного сложения количества информации, т.е. условие аддитивности. Если, например, первый источник характеризуется различными сообщениями, а второй — , то общее число различных сообщений для двух источников определяется произведением

Комбинаторная мера

Для лучшего понимания рассмотрим несколько простейших примеров.

Пример 1 . Проведем опыт. Возьмем игральный кубик. Он имеет шесть сторон, на каждой из которых изображены числа от одного до шести.

Этот пример позволяет перейти к понятию комбинаторной меры информации и дать следующее определение:

Рассмотрим следующий пример.

Пример 2. Пусть задана одна из десятичных цифр, например, цифра 8 и одна из шестнадцатеричных – к примеру, цифра 6 (можно было взять любую другую шестнадцатеричную - 8, В, F и т. д.). Теперь, в соответствии с определением комбинаторной меры, определим количество информации, заключенное в каждой из этих цифр. Поскольку цифра 8 является десятичной, а значит, представляет один символ из десяти, то N 8 = 10 комбинаций. Аналогично, цифра 6 представляет один из шестнадцати символов, а поэтому N 6 = 16 комбинаций. Следовательно, что шестнадцатеричная цифра содержит больше информации, чем десятичная.

Английский инженер Р. Хартли предложил измерять количество информации двоичной логарифмической мерой:

Подсчет дает следующие результаты:

в примере с кубиком I = log 2 6 = 2,585 бит;

в примере с десятичной системой счисления I = log 2 10 = 3,322 бит;

в примере с шестнадцатеричной системой счисления I = log 2 16 = 4 бит;

в примере с двоичной системой счисления I = log 2 2 = 1 бит.

I = log 2 32 = 5.