Формула Хартли. Формула Шеннона. Теорема Шеннона-Хартли. Теорема Котельникова. ИКМ. Основной цифровой поток DS0

Формула Хартли

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

Имеется алфавит А, из букв которого составляется сообщение:

Количество возможных вариантов разных сообщений:

где N - возможное количество различных сообщений, шт; m - количество букв в алфавите, шт; n - количество букв в сообщении, шт.

Пример: Алфавит состоит из двух букв «B» и «X», длина сообщения 3 буквы - таким образом, m=2, n=3. При выбранных нами алфавите и длине сообщения можно составить разных сообщений «BBB», «BBX», «BXB», «BXX», «XBB», «XBX», «XXB», «XXX» - других вариантов нет.

Формула Хартли определяется:

где I - количество информации, бит.

При равновероятности символов формула Хартли переходит в собственную информацию .

Формула Хартли была предложена Ральфом Хартли в 1928 году как один из научных подходов к оценке сообщений.

Иллюстрация

Допустим, нам требуется что-либо найти или определить в той или иной системе. Есть такой способ поиска, как «деление пополам». Например, кто-то загадывает число от 1 до 100, а другой должен отгадать его, получая лишь ответы «да» или «нет». Задаётся вопрос: «число меньше N?». Любой из ответов «да» и «нет» сократит область поиска вдвое. Далее по той же схеме диапазон снова делится пополам. В конечном счёте загаданное число будет найдено.

Сколько вопросов надо задать, чтобы найти задуманное число от 1 до 100. Допустим загаданное число 27. Вариант диалога:

Больше 50? Нет.

Больше 25? Да.

Больше 38? Нет.

Меньше 32? Да.

Меньше 29? Да.

Больше 27? Нет.

Это число 26? Нет.

Если число не 26 и не больше 27, то это явно 27. Чтобы угадать методом «деления пополам» число от 1 до 100, нам потребовалось 7 вопросов.

Можно просто спрашивать: это число 1? Это число 2? И т. д. Но тогда вам потребуется намного больше вопросов. «Деление пополам» - самый оптимальный способ нахождения числа. Объём информации, заложенный в ответ «да»/«нет», равен одному биту (действительно, ведь бит имеет два состояния: 1 или 0). Итак, для угадывания числа от 1 до 100 нам потребовалось семь бит (семь ответов «да»/«нет»).

Такой формулой можно представить, сколько вопросов (бит информации) потребуется, чтобы определить одно из возможных значений. N - это количество значений, а k - количество бит. Например, в нашем примере 100 меньше, чем 27, однако больше, чем 26. Да, нам могло бы потребоваться и всего 6 вопросов, если бы загаданное число было 28.

Формула Хартли: .

Количество информации (k), необходимой для определения конкретного элемента, есть логарифм по основанию 2 общего количества элементов (N).

Формула Шеннона

Когда события не равновероятны, может использоваться формула Шеннона . , где

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

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

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

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

Формальные определения

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

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

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

Определение по Шеннону

Клод Шеннон предположил, что прирост информации равен утраченной неопределённости, и задал требования к её измерению:

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

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

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

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

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

2. Для целых положительных , должно выполняться следующее неравенство:

3. Для целых положительных , где , должно выполняться равенство

Шеннон показал, что единственная функция, удовлетворяющая этим требованиям, имеет вид

где - константа (и в действительности нужна только для выбора единиц измерения).

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

Теорема Шеннона - Хартли

Теорема Шеннона - Хартли в теории информации - применение теоремы кодирования канала с шумом к архетипичному случаю непрерывного временно́го аналогового канала коммуникаций, искажённого гауссовским шумом . Теорема устанавливает шенноновскую ёмкость канала, верхнюю границу максимального количества безошибочных цифровых данных (то есть, информации), которое может быть передано по такой связи коммуникации с указанной полосой пропускания в присутствии шумового вмешательства, согласно предположению, что мощность сигнала ограничена, и гауссовский шум характеризуется известной мощностью или мощностью спектральной плотности. Закон назван в честь Клода Шеннона и Ральфа Хартли .

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

где - пропускная способность канала, бит /с; - полоса пропускания канала, Гц ; - полная мощность сигнала над полосой пропускания, Вт или В ²; - полная шумовая мощность над полосой пропускания, Вт или В ²; - частное от деления отношения сигнала к его шуму (SNR) на гауссовский шум, выраженное как отношение мощностей.

В данной теореме определено, что достичь максимальной скорости (бит/с) можно путем увеличения полосы пропускания и мощности сигнала и, в то же время, уменьшения шума.

Теорема Шеннона - Хартли ограничивает информационную скорость (бит/с) для заданной полосы пропускания и отношения «сигнал/шум». Для увеличения скорости необходимо увеличить уровень полезного сигнала, по отношению к уровню шума.

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

Удивительно, но не только ограничения полосы пропускания влияют на количество передаваемой информации. Если мы комбинируем шум и ограничения полосы пропускания, мы действительно видим, что есть предел количества информации, которую можно было передать, даже используя многоуровневые методы кодирования. В канале, который рассматривает теорема Шеннона - Хартли, шум и сигнал дополняют друг друга. Таким образом, приёмник воспринимает сигнал, который равен сумме сигналов, кодирующего нужную информацию и непрерывную случайную, которая представляет шум.

Это дополнение создает неуверенность относительно ценности оригинального сигнала. Если приёмник обладает информацией о вероятности ненужного сигнала, который создает шум, то можно восстановить информацию в оригинальном виде, рассматривая все возможные влияния шумового процесса. В случае теоремы Шеннона - Хартли шум, как таковой, произведен гауссовским процессом с некоторыми отклонениями в канале передачи. Такой канал называют совокупным белым гауссовским шумовым каналом , так как гауссовский шум является частью полезного сигнала. «Белый» подразумевает равное количество шума во всех частотах в пределах полосы пропускания канала. Такой шум может возникнуть при воздействии случайных источников энергии, а также быть связан с ошибками, возникшими при кодировании. Зная о вероятности возникновения гауссовского шума, значительно упрощается определение полезного сигнала.

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

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

ИКМ

Передача квантованных значений сигнала с помощью коротких импульсов различной высоты называется амплитудно-импульсной модуляцией (АИМ). Под импульсно-кодовой модуляцией (ИКМ) понимается передача непрерывных функций при помощи двоичного кода.

При кодовой модуляции необходимо передать числа, выражающие величину квантованных отсчетов. Для этого можно воспользоваться двоичным кодом. Числа, подлежащие передаче, надо записать в двоичной системе счисления – это и даст необходимые кодовые комбинации. При помощи n - значных двоичных чисел можно представить чисел. Благодаря квантованию количество чисел, подлежащих передаче, сводится до конечной величины . Если принять шаг квантования за единицу, то будет означать наибольшее квантованное значение. Количество знаков в двоичной кодовой комбинации равно . Если n – не целое, то оно округляется до ближайшего целого числа. На рис. 3 показаны преобразования аналогового сигнала (а) в АИМ (б) и ИКМ (в) для n = 4.

Рис. 3

При выборе шага квантования (или числа ) следует учитывать два фактора. С одной стороны, увеличение числа ступеней квантования увеличивает точность передачи сигнала, с другой – требует удлинения кодовой комбинации ( n ). Так для телефонной передачи установлено, что удовлетворительное качество передачи достигается при , т.е. при семизначном коде.

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

заменяет отношение сигнал – шум.

Пусть число уровней квантования равно . Будем передавать каждое из значений n -значным кодовым числом, составленным из импульсов, квантованных на m уровней (АИМ). Общее число возможных комбинаций равно . Очевидно, что . Пусть шкала уровней симметрична относительно нуля, т. е. разрешенными являются уровни:

Если все уровни равновероятны, средняя мощность сигнала равна

Отсюда шаг квантования равен

откуда

Таким образом, при неизменных мощностях сигнала и помехи выгодно уменьшать основание кода. Наименьшее значение m равно 2 (двоичный код), что соответствует ИКМ. В этом случае т.е. введенная величина совпадает с обычным определением отношения сигнал – помеха.

В обычной АИМ >>1, и в этом случае

Следовательно, ИКМ дает выигрыш в отношении сигнал – помеха в раз.

Какой же ценой достигается этот выигрыш? Если при АИМ за каждый тактовый интервал (отсчет) передается один импульс, то при ИКМ за тот же интервал должны быть переданы n импульсов. При неизменной скважности каждый из этих n импульсов в n раз короче (см. рис. 3), а, следовательно, ширина спектра сигнала в n раз больше, чем ширина спектра сигнала АИМ. Таким образом, за увеличение отношения сигнал – помеха мы расплачиваемся расширением полосы.

Основной цифровой поток DS0

Digital Signal 0 (DS0 или DS-0 ) - основной североамериканский цифровой сигнальный стандарт (64 Кбит/сек кГц и использованием 8 бит импульсно-кодовой модуляции , в результате поток данных составляет 64 кбит/сек. Из-за фундаментальной роли для передачи одного телефонного звонка стандарт DS0 используется как основной в иерархии цифровой мультиплексной передачи в телекоммуникационных системах, используемых в Северной Америке.

С целью уменьшения количества проводов между двумя связанными друг с другом узлами используется мультиплексирование нескольких DS0 в линии с большей пропускной способностью. Линии, в которых мультиплексированы 24 сигнала DS0, получили название DS1, линии с 28 сигналами DS1 - DS3. Переданные по медным проводам DS1 и DS3 соответствуют стандартам T1 и T3 соответственно.

Помимо использования DS0 для голосовой связи, стандарт может поддерживать 20 каналов на 2.4 кбит/сек, 10 каналов на 4.8 кбит/сек, 5 каналов на 9.67 кбит/сек, один канал на 56 кбит/сек, или один канал для передачи данных на 64 кбит/сек.

E0, стандартизированный как ITU G.703 это европейский эквивалент североамериканского DS0 для передачи одного телефонного звонка.

В общем случае , энтропия H и количество получаемой в результате снятия неопределенности информации I зависят от исходного количества рассматриваемых вариантов N и априорных вероятностей реализации каждого из них P : {p 0 , p 1 , …p N -1 } , т.е. H =F (N , P ) . Расчет энтропии в этом случае производится по формуле Шеннона , предложенной им в 1948 году в статье "Математическая теория связи".

В частном случае , когда все варианты равновероятны , остается зависимость только от количества рассматриваемых вариантов, т.е. H =F (N ) . В этом случае формула Шеннона значительно упрощается и совпадает с формулой Хартли , которая впервые была предложена американским инженером Ральфом Хартли в 1928 году, т.е. не 20 лет раньше.

Формула Шеннона имеет следующий вид:

Знак минус в формуле (1) не означает, что энтропия – отрицательная величина. Объясняется это тем, что p i £ 1 по определению, а логарифм числа меньшего единицы - величина отрицательная. По свойству логарифма , поэтому эту формулу можно записать и во втором варианте, без минуса перед знаком суммы.

Интерпретируется как частное количество информации , получаемое в случае реализации i -ого варианта. Энтропия в формуле Шеннона является средней характеристикой – математическим ожиданием распределения случайной величины {I 0 , I 1, … I N -1 } .

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

Таблица 1.

	p i	1/p i	I i = log 2 (1/p i ), бит	p i *log 2 (1/p i ), бит
			log 2 (4/3)=0,42
å				H=0,81 бит

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

Таблица 2.

	p i	1/p i	I i = log 2 (1/p i ), бит	p i *log 2 (1/p i ), бит
	1 /2		log 2 (2 )=1	1/2 * 1 =1/2
	1/2		log 2 (2 )=1	1/2 * 1 =1/2
å				H=1 бит

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

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

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

I = log 2 K , Где К - количество равновероятных событий; I - количество бит в сообщении, такое, что любое из К событий произошло. Иногда формулу Хартли записывают так:

I = log 2 K = log 2 (1 / р) = - log 2 р, т. к. каждое из К событий имеет равновероятный исход р = 1 / К, то К = 1 / р.

Задача.

Шарик находится в одной из трех урн: А, В или С. Определить сколько бит информации содержит сообщение о том, что он находится в урне В.

Такое сообщение содержит I = log 2 3 = 1,585 бита информации.

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

"Однажды в детстве я уронил бутерброд. Глядя, как я виновато вытираю масляное пятно, оставшееся на полу, старший брат успокоил меня:

Не горюй, это сработал закон бутерброда.

Что еще за закон такой? - спросил я.

Закон, который гласит: "Бутерброд всегда падает маслом вниз". Впрочем, это шутка, - продолжал брат.- Никакого закона нет. Прсто бутерброд действительно ведет себя довольно странно: большей частью масло оказывается внизу.

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

Проверили. Из десяти раз восемь бутерброд упал маслом вниз.

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

Наши опыты прервала мать…" (Отрывок из книги "Секрет великих полководцев", В.Абчук).

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

I = - Sum р i log 2 р i , где i принимает значения от 1 до К.

Формулу Хартли теперь можно рассматривать как частный случай формулу Шеннона:

I = - Sum 1 / К log 2 (1 / К) = I = log 2 К.

При равновероятных событиях получаемое количество информации максимально.

Задачи. 1. Определить количество информации, получаемое при реализации одного из событий, если бросают а) несимметричную четырехгранную пирамидку; б) симметричную и однородную четырехгранную пирамидку. Решение. а) Будем бросать несимметричную четырехгранную пирамидку. Вероятность отдельных событий будет такова: р1 = 1 / 2, р2 = 1 / 4, р3 = 1 / 8, р4 = 1 / 8, тогда количество информации, получаемой после реализации одного из этих событий, рассчитывается по формуле: I = -(1 / 2 log 2 1/2 + 1 / 4 log 2 1/4 + 1 / 8 log 2 1/8 + 1 / 8 log 2 1/8) = 1 / 2 + 2 / 4 + + 3 / 8 + 3 / 8 = 14/8 = 1,75 (бит). б) Теперь рассчитаем количество информации, которое получится при бросании симметричной и однородной четырехгранной пирамидки: I = log 2 4 = 2 (бит). 2. Вероятность перового события составляет 0,5, а второго и третьего 0,25. Какое количество информации мы получим после реализации одного из них? 3. Какое количество информации будет получено при игре в рулетку с 32-мя секторами?

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

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

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

Молекулы ДНК (дезоксирибонуклеиновой кислоты) состоят из четырех различных составляющих (нуклеотидов), которые образуют генетический алфавит. Информационная емкость знака этого алфавита составляет:

4 = 2 I , т.е. I = 2 бит.

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

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

где I - количество информации;
N - количество возможных событий;
р i - вероятность i-го события.

Например, пусть при бросании несимметричной четырехгранной пирамидки вероятности отдельных событий будут равны:

Р 1 = 1/2, р 2 = 1/4, р 3 = 1/8, р 4 = 1/8.

Тогда количество информации, которое мы получим после реализации одного из них, можно рассчитать по формуле (2.2):

I = -(l/2 log 2 l/2 + l/4 log 2 l/4 + l/8 log 2 l/8 + l/8 log 2 l/8) = (1/2 + 2/4 + 3/8 + 3/8) битов = 14/8 битов = 1,75 бита.

Этот подход к определению количества информации называется вероятностным .

Для частного, но широко распространенного и рассмотренного выше случая, когда события равновероятны (p i = 1/N), величину количества информации I можно рассчитать по формуле:

(2.3)

По формуле (2.3) можно определить, например, количество информации, которое мы получим при бросании симметричной и однородной четырехгранной пирамидки:

I = log 2 4 = 2 бита. Таким образом, при бросании симметричной пирамидки, когда события равновероятны, мы получим большее количество информации (2 бита), чем при бросании несимметричной (1,75 бита), когда события неравновероятны.

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

Выбор оптимальной стратегии в игре "Угадай число". На получении максимального количества информации строится выбор оптимальной стратегии в игре "Угадай число", в которой первый участник загадывает целое число (например, 3) из заданного интервала (например, от 1 до 16), а второй - должен "угадать" задуманное число. Если рассмотреть эту игру с информационной точки зрения, то начальная неопределенность знаний для второго участника составляет 16 возможных событий (вариантов загаданных чисел).

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

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

Задания

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

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

1.4. Вероятность первого события составляет 0,5, а второго и третьего - 0,25. Какое количество информации мы получим после реализации одного из них?

1.5. Какое количество информации получит второй игрок в игре "Угадай число" при оптимальной стратегии, если первый игрок загадал число: от 1 до 64? От 1 до 128?

Http://informatika.Sch880.Ru/p1aa1.Html

Http://teo-inf1.Narod.Ru/shen.Html

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

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

В окружающем нас мире существует множество явлений, которые каждый раз происходят несколько по-иному, приводят к неожиданному результату. Эти явления называют случайными. Случай играет не последнюю роль в жизни человека. Издавна существует понятие "Его Величество Случай".

Многие явления в технике, природе и других областях также носят случайный характер, т. е. невозможно точно предсказать, как явление будет происходить. Но при наблюдении этого явления достаточное число раз при неизменных условиях можно описать его течение количественно. Так, например, при бросании монеты нельзя предсказать, выпадет "орел" или "решка".

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

Если опыт подразделяется только на конечное число элементарных событий, которые являются к тому же равновероятными, то говорят, что речь идет о классическом случае. Примерами таких опытов являются бросания монеты, бросание игральной кости. Для опытов такого типа еще Лаплас разработал теорию вероятности. (Р(А) = число элементарных событий благоприятных для А / число всех возможных элементарных событий).

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

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

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

На примере игры "Угадай число" можно рассмотреть уменьшение неопределенности. Один из участников загадывает целое число (например, 30) из заданного интервала (например, от 1 до 32), цель второго - "угадать" число первого участника. Для второго игрока начальная неопределенность знания составляет 32 возможных события. Чтобы найти число, необходимо получить определенное количество информации. Первый участник может отвечать только "да" и "нет". Второй должен выбрать следующую стратегию: последовательно, на каждом шаге уменьшать неопределенность знания в два раза. Для этого он должен делить числовой интервал пополам, задавая свои вопросы.

Протокол игры.

Для того чтобы угадать число из интервала от 1 до 32 потребовалось 5 вопросов. Количество информации, необходимое для определения одного из 32 чисел, составило 5 бит.

Количество возможных событий К и количество информации I связаны между собой формулой:

Данная формула позволяет определять:

количество информации, если известно количество событий;

количество возможных событий, если известно количество информации;

1. Конфеты находятся в одной из 10 коробок. Определить информационную неопределенность.

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

Ответ: 1 бит.

3. Шарик находится в одной из трех урн: А, В или С. Определить информационную неопределенность.

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

Ответ: 5 бит.

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

Ответ: 4 вопроса.

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

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

8. Определить стратегию угадывания одной карты из колоды из 32 игральных карт (все четыре шестерки отсутствуют), если на вопросы будут даны ответы "да" или "нет".

Одна из стратегий:

Вопрос второго	Ответ первого	Кол-во возможных событий (неопределенность знаний)	Полученное количество Информации
Задумана карта красной масти
Задумана карта крестовой масти?
Задумана карта -картинка?
Задумана дама или туз крестовой масти?
Задуман валет крестовой масти?