Закон аддитивности информации

Менеджерами не рождаются, менеджерами становятся

Введение в теорию информации

Когда я учился в институте, очень популярной была игра «Быки и коровы». Я был практически непобедимым игроком, а всё благодаря относительно несложному алгоритму, разработанному мною на основе теории информации. И вот недавно я обнаружил, что в любимую игру моей юности можно сразиться онлайн. И что вы думаете? Я сыграл трижды против самого сильного «соперника» (из тех, что предложил компьютер), и все три раза выиграл! ?

Я решил рассказать о разработанной мною оптимальной стратегии игры «Быки и коровы» на основе теории информации, но для начала – о книге, которая познакомила меня с основами теории информации. В печатном виде найти ее непросто (всё же год издания 1980-й), а вот в электронном – пожалуйста.

Альфред Реньи. Трилогия о математике. – М.: Мир, 1980. – 376 с. В сборник включены научно-популярные произведения известного венгерского математика и популяризатора науки: «Диалоги о математике», «Письма о вероятности», «Дневник. — Записки студента по теории информации», а также четыре статьи: о теории вероятностей, о ее преподавании, о числах Фибоначчи и о математической теории «деревьев».

Скачать краткий конспект в формате Word
Примечание. Файл Word содержит буквы греческого алфавита, благодаря чему восприятие материала облегчено ?

Книга интересна вся, но к разработке алгоритма игры «Быки и коровы» «причастна» лишь новелла «Дневник. — Записки студента по теории информации». Краткое её изложение я вам и представляю.

Возникновение математической теории информации стало возможным после того, как было осознано, что количество информации можно задать числом. Чтобы измерить количество любой информации, необходимо закодировать ее в виде последовательности нулей и единиц наиболее рациональным способом (то есть способом, позволяющим получить самую короткую последовательность). Длина (количество знаков) полученной последовательности нулей и единиц (кодового слова) может служить мерой количества информации. Ответ на вопрос, допускающий лишь два ответа — «да» и нет», а в остальном произвольный, служит единицей для измерения количества информации.

Каждая цифра числа, записанного в двоичной системе счисления, содержит одну единицу информации. Отсюда и название единицы информации — бит (от английского binary digit —двоичная цифра).

На лекции присутствовали 32 студента. Лектор спросил, сколько вопросов необходимо задать, чтобы установить, кого из нас он задумал. Я тотчас ответил, что для этого понадобится 5 вопросов. Тогда лектор попросил меня пояснить, какие вопросы я имею в виду. Я сказал, что, прежде всего, составил бы список присутствующих, расположив их фамилии в алфавитном порядке, и спросил бы (в этом и состоял бы мой первый вопрос), не внесен ли задуманный лектором студент в первую половину списка. Полученный ответ, каким бы он ни был — утвердительным или отрицательным, позволил бы сузить круг поисков, вдвое уменьшив число «подозреваемых» с 32 до 16. Действуя аналогично, я вторым вопросом сократил бы число студентов, среди которых может оказаться задуманный лектором слушатель, до 8, третьим вопросом — до 4, четвертым — до 2 и, задав пятый вопрос, установил бы, кто был задуман. Затем лектор поинтересовался, хватило бы мне пяти вопросов, если бы их надо было задавать все сразу, то есть если бы, ставя очередной вопрос, я не знал ответов на предыдущие вопросы. Мне казалось, что если все вопросы задавать сразу, то их понадобится больше пяти. Но я заблуждался. Лектор показал, как следует задать сразу пять вопросов, чтобы по ответам на них можно было установить, кто из студентов был задуман. Перенумеруем сидящих в аудитории последовательными целыми числами от 0 до 31 и запишем порядковый номер каждого студента в двоичной системе. Каждой из 32 фамилий мы тем самым поставим в соответствие пятиразрядное двоичное число (если двоичная запись порядкового номера окажется короче пяти знаков, припишем недостающие знаки (нули) слева; например, число 1 запишем в виде 00001. Пять вопросов, которые можно задать сразу, заключаются в следующем: верно ли, что в двоичной записи порядкового номера фамилии задуманного студента первая, вторая, третья, четвертая и пятая цифры равны единице?

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

Закон аддитивности информации:

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

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

В общем же случае количество информации Н(x) можно найти по формуле Шеннона:

где x – неизвестный элемент множества Н = <х1, х2, …, хN>, то есть x – случайная величина, принимающая значения х1, х2, …, хN, а рK – вероятность того, что x принимает значения хK(k = 1, 2, … N).

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

Вероятность наступления независимых событий равна произведению их вероятностей.

Если при фиксированном значении N распределение вероятностей (p1, р2, …, рN) отлично от равномерного распределения, то сумма p1log2(1/p1) + p2log2(1/p2) + … + pNlog2(1/pN) всегда меньше чем log2N. Это означает следующее: если о случайной величине x известно лишь, что она принимает N различных значений, то при наблюдении одного значения x наибольшую информацию мы получаем в том случае, если все возможные значения x равновероятны.

Формулу (2) Винер вывел в 1948 г. независимо от Шеннона. Однако еще в XIX веке эта формула встречалась в работах Больцмана, поэтому ее часто называют формулой Больцмана — Шеннона. Больцман пришел к ней, занимаясь совсем другой задачей – изучением энтропии. Энтропия физической системы служит мерой неупорядоченности системы. Следовательно, можно считать, что энтропия системы является мерой неопределенности состояния молекул, образующих систему.

Неопределенность есть не что иное, как недостача информации, или отрицательная информация. Ту же мысль можно выразить иначе: информация есть не что иное, как убыль неопределенности. До наблюдения случайной величины x мы пребываем в полной неопределенности относительно того, какое из своих значений она может принять. После того как наблюдение произведено, неопределенность устраняется. Наблюдение случайной величины x содержит Н(x) битов информации; поскольку эта информация позволила избавиться от неопределенности, существовавшей до наблюдения, естественно принять число Н(x) за меру этой неопределенности. Таким образом, Н(x) можно рассматривать относительно значения, принимаемого величиной x, и как меру неопределенности, существовавшей до наблюдения случайной величины x. Эту меру неопределенности и принято называть энтропией. Итак, формула Шеннона допускает следующую интерпретацию. Если случайная величина x принимает значения х1, х2, …, хN с вероятностями р1, р2, …, рN, то энтропию величины x (то есть меры неопределенности существовавшей до наблюдения величины x), которую мы обозначим Н(x), можно вычислить по формуле:

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

Рис. Зависимость количества информации (энтропии) от вероятности одного из двух событий

Количество информации о случайной величине x, полученной при наблюдении случайной величины h:

Относительно величины I(x, h) можно утверждать следующее:

а) Величина I(x, h) всегда неотрицательна и обращается в 0 лишь в том случае, если x и h независимы. Если x и h независимы, то наблюдение случайной величины h; не дает никакого выигрыша в информации относительно случайной величины x.

б) Справедливо неравенство I(x, h) меньше или равно Н(x), причем равенство в нем достигается в том и только в том случае, если x = f(h), то есть если значения случайной величины h однозначно определяют значения случайной величины x. Действительно, в этом случае наблюдение случайной величины h позволяет точно установить значение случайной величины x, то есть получить полную информацию относительно x. Иначе говоря, наблюдение случайной величины h позволяет полностью устранить всю неопределенность Н(x), относительно случайной величины x.

в) Величина I(x, h) симметрична: I(x, h) = I(h, x), то есть наблюдение случайной величины h позволяет получить точно такое же количество информации относительно случайной величины x, какое наблюдение случайной величины x дает относительно случайной величины h. Именно поэтому величину I(x, h) принято называть взаимной информацией случайных величин x и h. Равенство I(x, h) = I(h, x) также означает, что если мы рассматриваем две случайные величины, в определенной мере зависящие друг от друга, то средства теории информации не позволяют определить, какая из них играет роль причины и какая — следствия. Единственное, что в наших силах, — это установить, насколько тесна связь между двумя случайными величинами – насколько велика корреляция!

baguzin.ru

§1. Основы теории информации

1.1. Понятие информации. Количество информации.

Единицы измерения информации

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

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

Например, если мы подбрасываем вверх монету, то она может упасть двумя различными способами (орлом вверх или решкой вверх). Соответственно, у данного события два возможных исхода. Если же подбрасывать игральный кубик, то исходов будет шесть.

В алфавитном подходе информация — это сообщение (последовательность символов некоторого алфавита). Причём существенными являются только размер алфавита и количество символов в сообщении. Конкретное содержание сообщения интереса не представляет. Чаще всего алфавит является двоичным (состоит из `2` символов – «`0`» и «`1`»).

После таких определений понятия «информация» можно говорить об её измерении. Введём несколько основных единиц измерения информации.

Чаще всего в качестве основной единицы измерения информации используется бит. При алфавитном подходе один бит — это коли-чество информации, которое можно передать в сообщении, состоящем из одного двоичного знака («`0`» или «`1`»). С точки же зрения содержа-тельного подхода один бит — это количество информации, уменьшающее неопределённость знания в два раза.

Наряду с битами можно использовать и другие единицы измерения информации, например, триты или диты. При алфавитном подходе один трит — это количество информации, которое можно передать в сообщении, состоящем из одного троичного знака («0», «1» или «2»). С точки же зрения содержательного подхода один трит — это количество информации, уменьшающее неопределённость знания в три раза. Соответственно, один дит — это количество информации, уменьшаю-щее неопределённость знания в десять раз, и количество информации, которое можно передать в сообщении, состоящем из одного десятичного знака (арабской цифры). В некоторых задачах (например, в задаче взлома кодового замка) удобнее в качестве основной единицы измере-ния информации использовать не биты, а диты, поскольку угадывание каждой цифры из кода уменьшает количество комбинаций в `10` раз.

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

`1` байт (`1`B) `= 8` бит;

Далее существует две линейки производных единиц для байта – линейка десятичных приставок и линейка двоичных приставок. В случае десятичных приставок каждая следующая единица измерения равна `1000` предыдущих единиц. Обозначаются десятичные приставки латинскими буквами (буква префикса из системы СИ и заглавная «B», обозначающая «байт») Итак:

`1` килобайт (`1` kB) `= 1000` B (1000 байт);

`1` мегабайт (`1` MB) `= 1000` kB ;

`1` гигабайт (`1` GB) `= 1000` MB;

`1` терабайт (`1` TB) `= 1000` GB;

`1` петабайт (`1` PB) `= 1000` TB;

`1` эксабайт (`1` EB) `= 1000` PB;

`1` зеттабайт (`1` ZB) `= 1000` EB;

`1` йоттабайт(`1` YB) `= 1000` ZB.

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

При использовании двоичных приставок, каждая следующая едини-ца измерения равна 1024 предыдущих единиц. В России принято обоз-начать двоичные приставки, записывая префикс заглавной русской буквой и после него слово «байт» целиком и тоже русскими буквами. За рубежом для обозначения двоичных приставок между префиксом и «B» добавляется маленькая буква «i» (от слова «binary»). Кроме того, все префиксы записываются заглавными буквами. Итак:

`1` кибибайт (`1` Кбайт, `1` KiB) `=2^10` байт `= 1024` байт;

`1` мебибайт (`1` Мбайт, `1` MiB) `=2^20` байт `= 1024` Кбайт;

1 гибибайт (`1` Гбайт, `1` GiB) `=2^30` байт `= 1024` Мбайт;

1 тебибайт (`1` Тбайт, `1` TiB) `=2^40` байт `= 1024` Гбайт;

1 пебибайт (`1` Пбайт, `1` PiB) `=2^50` байт `= 1024` Тбайт;

1 эксбибайт (`1` Эбайт, `1`EiB) `=2^60` байт `= 1024` Пбайт;

1 зебибайт (`1` Збайт, `1` ZiB) `=2^70` байт `= 1024` Эбайт;

1 йобибайт (`1` Йбайт, `1` YiB) `=2^80` байт `= 1024` Збайт.

1.2. Формула Хартли измерения количества информации.

Закон аддитивности информации

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

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

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

Например, пусть мы знаем, что некоторая интересная для нас книга находится на одной из полок нашего книжного шкафа, в котором `8` полок. Какое количество информации нам нужно получить, чтобы однозначно узнать полку, на которой находится книга?

Решим эту задачу с точки зрения содержательного и алфавитного подходов. Поскольку изначально в шкафу было `8` полок, а в итоге мы выберем одну, следовательно, неопределённость знания о местоположении книги уменьшится в `8` раз. Мы говорили, что один бит – это количество информации, уменьшающее неопределённость знания в `2` раза. Следовательно, мы должны получить `3` бита информации.

Теперь попробуем использовать алфавитный подход. Закодируем номера всех полок при помощи `0` и `1`. Получим следующие номера: `000, 001, 010, 011, 100, 101, 110, 111`. Для того чтобы узнать, на какой полке находится книга, мы должны узнать номер этой полки. Каждый номер состоит из `3` двоичных знаков. А по определению, `1` бит (в алфавитном подходе) – это количество информации в сообщении, состоящем из `1` двоичного знака. То есть мы тоже получим `3` бита информации.

Прежде чем продолжить рассмотрение поставленной общей задачи введём важное математическое определение.

Назовём логарифмом числа `N` по основанию `a` такое число `X`, что Обозначение: `X=log_aN.

На параметры логарифма налагаются некоторые ограничения. Число `N` обязательно должно быть строго больше `0`. Число `a` (основание логарифма) должно быть также строго больше нуля и при этом не равняться единице (ибо при возведении единицы в любую степень получается единица).

Теперь вернёмся к нашей задаче. Итак, какое же количество информации нам нужно получить, чтобы выбрать один исход из `N` равновероятных? Ответ на этот вопрос даёт формула Хартли: `H=log_aN`, где `N` – это количество исходов, а `H` – количество информации, которое нужно получить для однозначного выбора `1` исхода. Основание логарифма обозначает единицу измерения количества информации. То есть если мы будем измерять количество информации в битах, то логарифм нужно брать по основанию `2`, а если основной единицей измерения станет трит, то, соответственно, логарифм берётся по основанию `3`.

Рассмотрим несколько примеров применения формулы Хартли.

В библиотеке 16 стеллажей, в каждом стеллаже 8 полок. Какое количество информации несёт сообщение о том, что нужная книга находится на четвёртой полке?

Решим эту задачу с точки зрения содержательного подхода. В переданном нам сообщении указан только номер полки, но не указан номер стеллажа. Таким образом, устранилась неопределённость, связанная с полкой, а стеллаж, на котором находится книга, мы всё ещё не знаем. Так как известно, что в каждом стеллаже по `8` полок, следовательно, неопределённость уменьшилась в `8` раз. Следовательно, количество информации можно вычислить по формуле Хартли `H=log_2 8=3` бита информации.

Имеется `27` монет, одна из которых фальшивая и легче всех остальных. Сколько потребуется взвешиваний на двухчашечных весах, чтобы однозначно найти фальшивую монету?

В этой задаче неудобно использовать бит в качестве основной единицы измерения информации. Двухчашечные весы могут принимать три положения: левая чаша перевесила, значит, фальшивая монета находится в правой; правая чаша перевесила, значит, монета находится в левой; или же весы оказались в равновесии, что означает отсутствие фальшивой монеты на весах. Таким образом, одно взвешивание может уменьшить неопределённость в три раза, следовательно, будем использовать в качестве основной единицы измерения количес-тва информации трит.

По формуле Хартли `H = log _3 27 = 3` трита. Таким образом, мы видим, что для того чтобы найти фальшивую монету среди остальных, нам потребуется три взвешивания.

Логарифмы обладают очень важным свойством: `log_a(X*Y)=log_aX+log_aY`.

Если переформулировать это свойство в терминах количества информации, то мы получим закон аддитивности информации: Коли-чество информации`H(x_1, x_2)`, необходимое для установления пары `(x_1, x_2)`, равно сумме количеств информации `H(x_1)` и `H(x_2)`, необходимых для независимого установления элементов `x_1` и `x_2`:

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

Игральная кость может упасть `8` различными способами, следовательно, по формуле Хартли можно вычислить, что, определив число, выпавшее на игральной кости, мы получаем `3` бита информации. Соответственно, монета может упасть только `2` способами и несёт в себе `1` бит информации. По закону аддитивности информации мы можем сложить полученные результаты и узнать, что интересующее нас сообщение несёт `4` бита информации.

Рассмотрим другой способ решения этой задачи. Если мы сразу рассмотрим все возможные исходы падения `2` предметов, то их будет `16` (кость выпадает `8` способами, а монета — орлом вверх, и кость выпадает `8` способами, а монета — решкой вверх). По формуле Хартли находим, что интересующее нас сообщение несёт `4` бита информации.

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

1.3. Примеры решения задач по теме

«Математическая теория информации»

В велокроссе участвуют `130` спортсменов. Специальное устройство регистрирует прохождение каждым из участников промежуточного финиша, записывая его номер с использованием минимально возможного количества бит, одинакового для каждого спортсмена. Каков информационный объём сообщения, записанного устройством, после того как промежуточный финиш прошли `75` велосипедистов?

Первым делом нужно определить, сколько бит необходимо для кодирования `130` номеров спортсменов. Поскольку номера записываются в некотором устройстве, количество бит для кодирования каждого номера обязательно должно быть целым: `H=log_2 130`. После округления результата в большую сторону получим число `8`. Следовательно, для кодирования `1` номера необходим `1` байт. Таким образом, информационный объём сообщения, записанного устройством, составляет `75` байт.

В некоторой стране автомобильный номер состоит из `7` символов. В качестве символов используют `18` различных букв и десятичные цифры в любом порядке.

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

Определите объём памяти, отводимый этой программой для записи `60` номеров.

Первое действие аналогично предыдущей задаче – нужно установить, каким количеством бит кодируется `1` символ. Всего используется `18` букв и `10` десятичных цифр, то есть `28` символов. По формуле Хартли `H=log_2 28`. После округления получается `5` бит на `1` символ. Вторым действием нужно узнать, какой объём памяти занимает `1` номер. Поскольку номер состоит из `7` символов, а каждый символ кодируется `5` битами, нам потребуется `35` бит памяти для хранения `1` номера. Однако по условию каждый номер должен записываться целым количеством байтов, а в каждом байте `8` бит. Ближайшее сверху к `35` число, делящееся на `8` – это число `40`, следовательно, на каждый номер отводится `5` байт. Таким образом, для записи `60` номеров программе потребуется `60*5 = 300` байт памяти.

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

Главная ловушка этой задачи заключается в следующем неверном ходе мыслей: «Раз одной рукой передаётся `3` сигнала, значит, двумя в `2` раза больше, то есть `6`». На самом деле число исходов с добавлением новой руки увеличивается в `3` раза, поскольку можно продублировать все положения первой руки для каждого из `3` возможных положений второй. Таким образом, в ответе получается `9` сигналов.

В течение `5` секунд было передано сообщение, объём ко-торого составил `375` байт. Каков размер алфавита, с помощью кото-рого записано сообщение, если скорость его передачи составила `200` символов в секунду?

Первым делом найдём скорость передачи этого сообщения: `375//5 = 75` байт в секунду. Далее, нам известно, что в секунду передавалось `200` символов, которые занимают `75` байт памяти. Поэтому следующим действием найдём объём памяти, отводимый под `1` символ, переведя ответ в биты (ибо уже из входных чисел очевидно, что под каждый символ отводится менее `1` байта): `75*8//200 = 600//200 = 3`. Таким образом, под каждый символ отводится `3` бита.

Применяя формулу Хартли, находим, что алфавит состоит из `8` символов.

zftsh.online

Закон аддитивности информации

Измерение информации. I (x1,x2) = iх1 + ix2. Закон аддитивности информации. Количество информации, заключенное в сообщении о событии, состоящем в том, что произошло несколько независимых событий, равно сумме количеств информации, заключенных в сообщениях об отдельных событиях. Информационный объем совокупного события складывается из информационных объемов, входящих в него событий.

Слайд 15 из презентации «Система измерения информации». Размер архива с презентацией 1660 КБ.

Информатика 10 класс

«Электронная почта» — Электронная почта. Скорость пересылки. Адрес электронной почты. Компьютерная сеть. Прикрепленные файлы. Функционирование электронной почты. Основные понятия. Практическая работа. Почтовые программы. Коммуникационные технологии. Почта. Пересылка почтовых открыток. Работа с электронной почтой.

«Компьютер и здоровье детей» — Анкетирование. 3.Компьютер — друг и помощник. Устают ли у вас глаза после работы за компьютером? «Компьютер. Отлучить нас – детей от компьютера все равно не удастся, да и не нужно. Во сколько лет вы начали работать за компьютером? Сегодняшние темпы компьютеризации превышают темпы развития всех других отраслей. Делаете ли вы физ-минутку во время работы за компьютером? Тема исследования: «Компьютер.

«Как создать презентацию в Microsoft PowerPoint» — Как создать презентацию в Microsoft PowerPoint. Анимация. Что можно вставить в слайд. Как найти. Расположение объектов. Что такое Microsoft PowerPoint. Показ слайдов. Оформление текста. Звук. Создание нового слайда. Критерии оценивания презентации. Оформление слайда. Изменение размера. Сохранение презентации. Выделите нужный объект. Мышь.

«Система измерения информации» — Кодирование векторной графики. Вычислим объем видеопамяти. Двоичное кодирование видео информации. Племя Мумбу-Юмбу. Измерение. Сообщение, уменьшающее неопределенность знаний. Виды компьютерных изображений. Сообщение о выпадении грани. Число символов. Дискретизация графики. Кодирование растровой графики. Закон аддитивности информации. Вопросы. Количество равновероятных событий. Измерение количества информации.

«Классификация ЭВМ по поколениям» — Поколения ЭВМ. История ЭВМ. Электровакуумные лампы. Электронная вычислительная машина. Первое поколение ЭВМ. ЭВМ общего назначения. Электронные лампы. Второе поколение ЭВМ. Элементная база ЭВМ. Эффективные компиляторы. Программное обеспечение. Поколение ЭВМ. Полупроводниковые приборы. Русский математик. Снижение цен на аппаратное обеспечение. Патент на счетный прибор. Многопроцессорный вычислительный комплекс.

«ОС компьютера» — Ос windows. Операционная система. Этапы загрузки ОС. Основные функции ос. Состав ос. 1.Автоматическое обращение процессора к ПЗУ (энергонезависимое запоминающее устройство). Многозадачность. Интерфейс — взаимодействие между участниками (графический, программный,аппаратный). Приложения-программы, которые работают под управлением Windows.

Всего в теме «Информатика 10 класс» 50 презентаций

5klass.net

Пусть задано множество X, содержащее N1 элементов xi Є X,а также множество Y,содержащее N2 элементов yj Є Y. Составим пары элементов (xi yj). Очевидно, что множество пар будет содержать N1·N2 элементов.

Количество информации (двоичных разрядов), необходимое, чтобы каждой паре (xi yj) поставить в соответствие двоичный код составит:

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

Формула Хартли получена при ограничениях.

1. Отсутствие смысловой ценности информации.

2. N возможных состояний равновероятны:

log N = -log 1/N = -log p

p = 1/N— вероятность появления одного сообщения.

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

log N = — log 1/N= — log p

р=1/N— вероятность появления любого значения из N возможных.

Возникают ситуации, в которых отмеченные выше ограничения не действуют, поэтому для них формула Хартли дает неверные результаты. Другое представление количества информации было найдено Клодом Шенноном примерно через 20 лет после опубликования формулы Хартли.

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

x1, x2,… xi xn Σ Pi = 1

Верхняя строка содержит сообщение (значение дискретной случайной величины), нижняя — вероятности их появления.

Пусть получено сообщение xi, вероятность которого Pi. Очевидно, что сообщение содержит некоторую информацию, обозначим её I(xi).Что принять в качестве количественной меры информации в данном случае. Поскольку кроме вероятности появления этого сообщения ничего неизвестно, то естественным является связать количество информации в этом сообщении с вероятностью его появления.

Жизненный опыт подсказывает, что информация о событии тем значительнее, чем меньше вероятность появления такого события. Однако, мера количества информации в виде 1/P(xi)не удобна по двум причинам: она не обладает свойством аддитивности и не обслуживает случай достоверного события.

В теории информации в качестве меры количества информации принята логарифмическая мера.

Определение 1. Количеством собственной информации в сообщении xi Є Xназывается число I(xi),определяемое соотношением:

Единица измерения количества информации и её названия зависит от основания логарифма. Если основанием логарифма является:

· Число 2, т.е. log2P(xi)[бит]

· Число e, т.е. logeP(xi)=lnP(xi)[нат] «natural digit»

· Число 10, т.е. . lg10P(xi)[дит]

Собственная информация неотрицательно и сообщение, имеющее меньшую вероятность несет большую информацию.

Количество информации, определяемое соотношением (1) является действительной функцией на ансамбле и следовательно, представляет собой случайную функцию со значениями I(x1), I(x2),…, I(xn).

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

Выражение (2) является формулой Шеннона и решает одну из основных задач теории информации, задачу количественной меры информации. Для двоичных сообщений формула имеет вид:

Формула Шеннона отображает общий случай, для произвольного закона распределения, когда вероятности отдельных сообщений не равны. Легко показать, что формула Хартли является частным случаем формула Шеннона, когда вероятности сообщений равны между собой. Если в формуле Шеннона принять одинаковую вероятность всех сообщений равную Pi(xi)=1/N=1/2 n , если N=2 n , то после преобразований получим:

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

Энтропия

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

Определение. Математическое ожидание H(X) случайной величины I(xi),определенной на ансамбле называется энтропией этого ансамбля:

Энтропия источника – среднее количество информации в одном сообщении. Не следует путать энтропию источника с количеством информации в одном конкретном сообщении I(xi).

Свойства энтропии источника дискретных сообщений:

1. Энтропия ограничена, неотрицательна, вещественна. Это вытекает из свойства вероятности:

0 ≤ P(xi) ≤ 1

2. Энтропия детерминированного сообщения равна нулю.

Запишем формулу энтропии в виде:

Если P1=1, то сумма всех остальных вероятностей равна 0. Первый член в выражении (2) равен нулю. Рассмотрим одно слагаемое в сумме, устремив Pi→0.

Раскрыв неопределённость по Лопиталю, получим:

lim (1/ ß) ·ln2 = 0

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

3. Энтропия альтернативного сообщения.

Альтернативный источник имеет только два выходных значения с вероятностями p и q, где q=(1-p), выражение для энтропии имеет вид:

Это функция двух переменных p и q. Учитывая, что q=(1-p), получим:

Изменяя p от 0 до 1 можно построить график рис. 2.

4. Энтропия дискретного источника со многими состояния максимальна, если состояния равновероятны.

Термин «энтропия» имеет несколько неопределённый смысл, что вызвано использованием его в термодинамике и статистической механике для выражения несколько иных понятий.

Результатом рассмотрения информационных моделей сигналов являлась оценка информации для каждого символа:

И формула энтропии источника дискретных сообщений:

H(x) = M[I(xi)] = -Σ Pi log2Pi

Из свойств энтропии следует, что количество информации в битах на символ лежит в пределах:

0 ≤ H(X) ≤ log2N

Нижний предел соответствует отсутствию неопределённости, а верхний максимальной неопределённости или равновероятности исходов наблюдений. Если распределение алфавита неравномерно информационное содержание алфавита меньше максимального и может быть найдено по формуле Шеннона:

В формуле предполагается, что символы источника является статистически независимыми, т.е. для двух символов (xjxk):

Если такое утверждение справедливо для источника, то такой источник называется источником без памяти.Энтропия источника без памяти называется безусловной энтропией.

Между максимальной энтропией Hmax(x)и безусловной Hбез(x)должно соблюдаться очевидное условие:

Уменьшение безусловной энтропии обусловлено различием вероятностей сообщений.

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

Условная частная энтропия, вычисляемая для каждого сообщения xi. Между услновной энтропией и безусловной соблюдается неравенство:

Hусл (x) ≤ Hбез(x)

По сравнению с безусловной энтропией условная энтропия учитывает более тонкую структуру вероятностных свойств источника, поэтому является более точной характеристикой источника.

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

Зависимость символов означает, что для последовательности Ксимволов неопределённость относительно К-го символа уменьшается, если известны (K-1) предыдущие. В слове СТУДЕН_неопределённость относительно последней буквы уменьшается, если известны предшествующие.

Энтропия системы зависимых случайных величин

или , (1.4)

где H(X) — безусловная энтропия величины Х;

H(Y) — безусловная энтропия величины Y;

H(Y/X) — условная энтропиявеличины Y относительно величины Х;

H(X/Y) — условная энтропия величины X относительно Y.

Для независимых величин и .

Условная энтропия X относительно Y

, (1.5)

где P(xi/yj) — вероятность значения xi величины X при условии, что величина Y приняла значение yj (условная вероятность).

Условная энтропия величины X относительно значения yj величины Y

. (1.6)

lektsii.org