2. Кодирование и измерение информации.

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

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

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

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

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

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

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

2.1. Вероятностный подход к измерению информации.

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

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

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

x=log₂N.

Например, сообщение о результате бросания монеты (количество равновероятных исходов равно 2) содержит х=1 бит информации (2^х = 2). Пусть в барабане для розыгрыша лотереи содержится 32 шара. Сколько информации содержит сообщение о первом выпавшем номере ? Поскольку появление любого из 32 шаров равновероятно, то 2^х = 32 и х=5 бит. Рассмотрим еще один пример. При бросании игральной кости используют кубик с шестью гранями. Сколько бит информации получает каждый игрок при бросании кубика ? Так как выпадение каждой грани равновероятно, то 2^х = 6, откуда х=log₂6  2,585 бит.

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

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

где p_i — вероятность того, что именно i-е сообщение выделено в наборе из N сообщений

Легко заметить, что если вероятности p_i равны, то каждая из них равна 1/N, и формула Шеннона превращается в формулу Хартли.

В качестве примера определим количество информации, связанное с появлением каждого символа в сообщениях, записанных на русском языке. Будем считать, что русский алфавит состоит из 33 букв и знака “пробел” для разделения слов. По формуле Хартли x= log₂34  5,09 бит. Однако в словах различные буквы встречаются неодинаково часто. Вероятности частоты употребления различных букв вычисляются на основе анализа очень больших по объему текстов. Если это учесть, то по формуле Шеннона получим H=4,72. Вычисления показывают, что при равновероятных событиях мы получаем большее количество информации, чем при неравновероятных событиях.

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

Задача 1. На вершину горы ведет 7 дорог. Сколькими способами турист может подняться на гору и спуститься с нее если подъем и спуск осуществляется разными путями ?

Задача 2. В группе 30 человек. Необходимо выбрать старосту и профорга. Сколькими способами можно это сделать ?

Задача 3. Сколько существует трехзначных чисел с разными цифрами ?

Задача 4. Сколькими способами можно разместить на полке 4 книги ?

Правило произведения. Если из некоторого конечного множества 1-й объект можно выбрать k₁ способами,

2-й объект можно выбрать k₂ способами,

……………………………………………..

n-й объект можно выбрать k_n способами.

тогда произвольный набор, перечисленных n объектов, из данного множества можно выбрать k₁ k₂ … k_n способами.

Для нахождения числа различных перестановок из nэлементов используют формулуP_n = n! Например, из цифр 3,5,7 можно составить 6 перестановок: 357, 375, 537, 573, 753, 735.

Задача 5. Сколько шестизначных чисел, кратных пяти, можно составить из цифр 1,2,3,4,5,6 при условии, что в числе цифры не повторяются ?

Задача 6. Сколькими способами могут расположиться в турнирной таблице 10 команд, если известно, что никакие две команды не набрали поровну очков ?

Пусть имеется некоторое множество, содержащее n элементов. Все элементы такого множества можно занумеровать, т.е. каждому элементу поставить в соответствие одно из натуральных чисел 1,2,…, n. Такие множества называются упорядоченными.

Любой упорядоченный набор из k элементов n-элементного множества называют размещением изn элементов по k. Все эти подмножества отличаются друг от друга или составом элементов, или порядком их распределения. Но число элементов во всех этих подмножествах равно k.

Например, пусть Х={a,b,c}. Тогда по одному элементу можно образовать три размещения: (a), (b), (c); по два – шесть размещений: (a,b), (b,a), (a,c), (c,a), (b,c), (c,b). Для определения числа размещений изn элементов по k используют формулу

= n(n-1)…(n – k +1) =

Задача 7. В турнире принимают участие 8 команд. Сколько различных предсказаний относительно распределения трех первых мест можно сделать ?

Задача 8. В семестре изучаются 14 предметов. Сколькими способами можно составить расписание занятий на понедельник, если в этот день недели должно быть 5 различных предметов ?

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

Задача 10. Назовите все возможные комбинации из двух различных нот (всего нот семь: до, ре, ми, фа, соль, ля, си).Иногда возникает необходимость не учитывать порядок элементов, входящих в размещение. Например, необходимо составить различные произведения из чисел 3,5,7. Таких произведений будет всего три: 35, 37, 57, так как 35=53 и мы порядок не учитываем.

Количество k-элементных подмножеств n-элементного множества называют сочетаниями и обозначают .Порядок элементов в подмножестве не имеет значения. Обратите внимание: отличие от: в сочетаниях не могут быть два одинаковых подмножества {a,b} и {b,a}.Два различных сочетания отличаются составом входящих в них элементов. Например, ниже выписаны всевозможные сочетания, составленные из 5 элементов 1,2,3,4 и 5 по 3 (столькими способами Вы можете выбрать 3 книги из 5): 123, 124, 125, 134, 135, 145, 234, 235, 245, 345

Число сочетаний из n элементов по k равно

Задача 11. Сколько экзаменационных комиссий, состоящих из 7 членов, можно образовать из 14 преподавателей ?

Задача 12. В турнире принимали участие n шахматистов, и каждые 2 шахматиста встретились 1 раз. Сколько партий было сыграно ?

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

Задача 15. Тетрадь лежит на одной из двух полок - верхней или нижней. Сколько бит несет в себе сообщение, что она лежит на нижней полке?

 Задача 16. Шарик находится в одной из 32 урн. Сколько единиц информации будет содержать сообщение о том, где он находится?

Задача 17. После реализации одного из равновозможных событий получили количество информации равное 10 бит. Какое количество возможных событий было первоначально ?

 Задача 18.   Какое количество информации получит первый игрок после первого хода второго игрока в игре "крестики - нолики" на поле 4 х 4 ?