Как найти вероятность символа

МИНИСТЕРСТВО
ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ

Федеральное
государственное автономное образовательное
учреждение

высшего
профессионального образования

«САНКТ-ПЕТЕРБУРГСКИЙ
ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

АЭРОКОСМИЧЕСКОГО
ПРИБОРОСТРОЕНИЯ

КАФЕДРА
«Прикладной математики»

Лабораторная
работа

защищена
с оценкой

Руководитель

ОТЧЕТ
О ЛАБОРАТОРНОЙ РАБОТЕ

«Определение
количества информации, содержащегося

в
сообщении»

ВАРИАНТ
№8

по
дисциплине: ИНФОРМАТИКА

Работу
выполнил(а)

Санкт-Петербург
2014

1. Цель
   работы

Получение
практических навыков численного
определения количества

информации,
содержащейся в сообщении.

1. Таблица
   №1

1. Таблица
   2

1. Рабочие
   формулы:

I_i=-log₂p_i

I_i
— количество информации; p-вероятность
вхождения символа;

D=(H_max-H)/H_max

H_max—
максимальное значение энтропии; D
—относительная избыточность;

D_abc=H_max-H

D_abc—
абсолютная избыточность;

P_i
= k_i/K

P_i
–
вероятность вхождения символа в текст,
k_i
— число вхождений символов в текст, K
— всего символов в текст;

I_ср=
I_ср
=∑ p_i
(-log₂
p_i)
= H
—
энтропия источника;

H₁
= log_a
N
– Исходная неопределенность по методы
Хартли

N—
число возможных значений принятого
слова после получения сообщения;

Разрядность
–
округление неопределенности (ROUNDUP)

1. Вывод:
   

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

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]

• #
• #
• #
• #
• #
• #
• #
• #
• #
• #
• #

2

Информационные веса символов алфавита и вероятность

Кудрявцева Е.В.,

учитель информатики

гимназии №4 г. Перми

Символы в тексте встречаются с одинаковой частотой?

Как рассчитать частоту появления определенного символа в естественном языке?

Кол-во вхождений данного символа

Частота =

Кол-во всех символов текста

Частотные характеристики букв латинского алфавита в английских текстах

Буква

Частота

E

0,130

T

Буква

Частота

A

S

0,105

0,081

0,061

O

H

Буква

D

0,079

U

N

0,052

Частота

0,038

0,071

0,024

Буква

R

G

L

0,068

Частота

I

Y

0,020

0,034

F

K

0,063

0,029

0,019

0,004

P

C

X

0,0015

0,019

W

J

0,027

M

0,0013

0,015

0,025

Q

B

V

0,0011

0,014

Z

0,0007

0,009

Частотные характеристики букв русского алфавита в русских текстах

Буква

_

Частота

0,175

Буква

О

Частота

Р

Е,Ё

0,090

0,072

0,040

Буква

В

А

Л

И

0,038

0,062

Я

Частота

0,062

0,018

0,035

Ы

Буква

К

Т

0,053

М

Н

0,028

0,016

Х

З

Частота

0,053

0,009

0,026

0,016

Ж

С

Ь,Ъ

Д

0,045

0,007

0,014

Б

0,025

Ю

П

0,014

0,023

0,006

У

Г

Ш

0,013

Ч

Ц

0,006

0,021

0,003

0,013

Щ

Й

0,003

Э

0,012

0,003

Ф

0,002

Информационный вес символа с учетом вероятности его появления в тексте

i = log 2 (1/P)

Р – вероятность появление данного символа

Для буквы «О»: i = log 2 (1/0,09) = 3,47 бита

Для буквы «Ф»: i = log 2 (1/0,002) = 8,97 бита

! Чем реже встречается символ, тем больше информации

несет его появление.

Пример

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

Клод элвуд шеннон (1916-2001)

• Решил проблему неизмеряемости информации.
• Основал теорию информации.
• Предложил слово «бит» для наименьшей единицы измерения информации.

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

H = P 1 log 2 (1/P 1 ) + P 2 log 2 (1/P 2 ) +…+ P N log 2 (1/P N )

H – средняя информативность символа в алфавите

P k – вероятность (частота) встречаемости k-ого символа

N – мощность алфавита

Для русского языка средняя информативность символа равна 4,36 бита.

? Для английского языка вычислите самостоятельно с помощью MS Excel

Домашнее задание

Читать §1.2.1 и 1.2.3,

Упражнения 8, 9 после §1.2.3

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

Математическая теория вероятности вышла на первый план в XVII веке – в дискуссиях об игре в кости.

Вероятность — очень лёгкая тема, если концентрироваться на смысле задач, а не на формулах. Во-первых, что такое вероятность? Это шанс, что какое-то событие произойдёт. Если мы говорим, что вероятность некоторого события 50%, что это значит? Что оно либо произойдет, либо не произойдет — одно из двух. Т.е. подсчитать значение вероятности очень просто — нужно взять количество подходящих нам вариантов и разделить на количество всех возможных вариантов.

Возьмем самый простой пример – подбросим монету. Какова вероятность, что выпадет «орел»? Ответ очевиден – ½. Когда мы говорим, что подбрасываем монету, мы предполагаем, что это симметричная монета, что вероятность выпадения «орла» равна вероятности выпадения «решки». Мы выяснили, что шанс получить «решку» при подбрасывании монеты это ½. Как мы получаем ½? Всего у нас два возможных варианта (орёл и решка), из них нам подходит один (решка), так мы и получаем вероятность ½.

Зафиксируем формулу для нахождения вероятности:

$ Вероятность= frac {количество; подходящих; вариантов}{количество; возможных; вариантов}$

Вероятность может выражаться в процентах:

$ Вероятность ; 100 (%)= frac {количество; подходящих; вариантов}{количество; возможных; вариантов} cdot 100% $

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

Пример: в урне 10 шаров: 6 белых и 4 черных. Какова вероятность вынуть из урны черный шар?

Решение. Что необходимо для нахождения вероятности? Посчитать количество подходящих вариантов и количество возможных вариантов. Всего шаров – 10, подходящих (т.е. черных) – 4, значит:

$ Вероятность ;=frac {4}{10}=0,4 $

Принято, что вероятность изменяется от 0 (никогда не произойдет – невозможное событие) до 1 (абсолютно точно произойдет – достоверное событие).

Пример: в урне 12 шаров: 6 белых и 6 черных. Какова вероятность вынуть из урны красный шар?

Решение. Интуитивно понятно, что поскольку в урне нет красных шаров, то и вероятность равна нулю. Давайте посчитаем количество подходящих вариантов и количество возможных вариантов. Всего шаров – 10, подходящих (т.е. красных) – 0, значит:

$ Вероятность ;=frac {0}{10}=0 $

В рассмотренном примере событие, заключающееся в вынимании красного шара, невозможное.

Зафиксируем еще одну формулу:

Вероятность подходящих событий + вероятность неподходящих событий = 1

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

Решение. Давайте найдем вероятность противоположного события, что выпадет число, кратное трем. Сколько подходящих событий? Количество подходящих событий (выпадет три, выпадет шесть) – 2, всего событий – 6 (граней на игральном кубике).

$ Вероятность ;(кратно;3)=frac {2}{6}=frac {1}{3} $

Значит, мы можем найти искомую вероятность:

$ Вероятность ;(не кратно;3)=1-frac {1}{3}=frac {2}{3} $

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

Вероятность нескольких событий:

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

1. Если нужно первое И второе событие, то умножаем.

2. Если нужно первое ИЛИ второе событие, то складываем (если события не могут совпасть).

Пример. Вероятности попадания в цель при стрельбе первого и второго орудий соответственно равны P₁=0,7, P₂=0,6. Какова вероятность попадания обоими орудиями одновременно при одном залпе?

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

P= P₁· P₂ = 0,7· 0,6 = 0,42.

Пример. Вероятность того, что в магазине будет продана пара мужской обуви 44-го размера, равна 0,12, 45-го – 0,04, 46-го и большего – 0,01. Какова вероятность того, что будет продана пара мужской обуви не меньше 44-го размера?

Решение. Снова вероятности каждого из событий нам даны. Что будем делать с ними? Нам подходят события: продана обувь 44-го размера ИЛИ продана обувь 45-го размера ИЛИ продана обувь 46-го и выше размеров. Значит, складываем вероятности каждого из событий:

P = 0,12 + 0,04 + 0,01 = 0,17.

Для понимания практического применения теории вероятности давайте рассмотрим еще вот такой шуточный пример. В местном зоопарке живет мартышка (можно дать ей имя). Допустим, что у нее есть старенькая пишущая машинка с 26 клавишами для букв латинского алфавита, одна – с точкой, одна – с запятой, одна – с вопросительным знаком и один пробел, итого – 30 клавиш. Сидит себе наша мартышка в углу и нажимает клавиши наугад. Любая последовательность букв имеет ненулевую вероятность оказаться напечатанной, а это значит, что есть шанс, что мартышка дословно напечатает пьесы Шекспира. Шансы у нее минимальные, но они точно отличны от нуля. Давайте разберемся, какова вероятность того, что наша мартышка напечатает последовательность из 8 символов “To be or” («быть или не»). Что мы должны для этого сделать? Сначала мы должны посчитать вероятность появления каждого символа. Представим 8 ячеек, в которых окажутся 8 символов, включая пробелы:

Что нужно, чтобы посчитать вероятность появления одного символа? Правильно, нужно

узнать, сколько всего возможно символов и сколько подходящих. Сколько возможных вариантов для одной ячейки? Помним, что всего у воображаемой нами печатающей машинки 30 клавиш, а значит, 30 возможных вариантов. Для первой ячейки – 30, для второй ячейки – 30, и т.д. Какова вероятность символа «t» в первой ячейке? Подходящий символ -1, количество возможных символов – 30, значит, вероятность равна 1/30. Какова вероятность символа «o» во второй ячейке? Тоже 1/30. Составим таблицу:

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

$ P=big(frac{1}{30}big)^{8}=frac{1}{6561}cdot 10^{-8} $

Получили очень малую вероятность. Чтобы понять, насколько она мала, давайте посчитаем, сколько времени придется ждать, чтобы мартышка напечатала указанные символы. Допустим, мартышка бьет по клавише раз в секунду (не прерываясь на сон и другие дела), тогда ожидаемое время составляет чуть более 20 800 лет. Поэтому если вдруг вы затаили дыхание в ожидании Шекспира – выдыхайте, у нее довольно долго будет получаться всякая нечитаемая последовательность типа «xo?h,yt?»

Простые вычисления и кодирования сообщений

МИНОБРНАУКИ
РОССИИ

Федеральное
государственное бюджетное образовательное учреждение

Высшего
профессионального образования

«Пензенский
государственный технологический университет»

(ПензГТУ)

Факультет
«Информационных и образовательных технологий»

Кафедра «Информационные
технологии и системы»

КОНТРОЛЬНАЯ РАБОТА

Выполнил:
студент группы 13ИС2Б

Чинков М.Ю

Проверил: ст.
преподаватель каф. ИТС

Пенза 2015

ВВЕДЕНИЕ

Цель данной контрольной работы — актуализация знаний в предмете «Основы
теории информации».

В рамках контрольной работы было выполнено 5 заданий в соответствии с
моим вариантом (вариант №23):

.        Определить среднее количество информации, содержащееся в сообщении,
используемом три независимых символа S1, S2, S3. Известны вероятности появления
символов p(S1)=p1, p(S2)=p2, p(S3)=p3. Оценить избыточность сообщения.

.        В условии предыдущей задачи учесть зависимость между символами,
которая задана матрицей условных вероятностей P(Si / Sj).

.        Провести кодирование по одной и блоками по две буквы, используя
метод Шеннона — Фано. Сравнить эффективности кодов (величина энтропии). Данные
взять из задачи 1.

.        Алфавит передаваемых сообщений состоит из независимых букв Si.
Вероятности появления каждой буквы в сообщении заданы. Определить и сравнить
эффективность кодирования сообщений методом Хаффмана при побуквенном
кодировании и при кодировании блоками по две буквы.

.        Определить пропускную способность канала связи, по которому
передаются сигналы Si. Помехи в канале определяются матрицей условных
вероятностей P(Si / Sj). За секунду может быть передано N = 10 сигналов.

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

.       

1.      ОПРЕДЕЛЕНИЕ
СРЕДНЕГО КОЛИЧЕСТВА ИНФОРМАЦИИ

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

Задание: определить среднее количество информации, содержащееся в
сообщении, используемом три независимых символа S1, S2, S3. Известны
вероятности появления символов p(S1)=p1, p(S2)=p2, p(S3)=p3. Оценить
избыточность сообщения. Вариант №23: p1=0.12; p2=0.13; p3=0.75.

Решение. Максимальное среднее количество информации на символ сообщения
имеет место при равновероятном распределении и равно, согласно формуле

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

Оценим
избыточность сообщения по формуле.

Максимальная энтропия.

Реальная
энтропия.

Избыточность
сообщения.

2.      ЗАВИСИМОСТЬ
МЕЖДУ СИМВОЛАМИ МАТРИЦЫ УСЛОВНЫХ ВЕРОЯТНОСТЕЙ

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

Задание: в условии предыдущей задачи учесть зависимость между символами,
которая задана матрицей условных вероятностей P(Si / Sj).

Вариант №23.

Решение. Рассчитаем энтропию источника по формуле.

Подставим
числовые данные, используя задание 1.

Вычисление
энтропии в программе MATLAB.

=p1*((0.7*log2(0.7)+0.3*log2(0.3)))+p2*((0.5*log2(0.5)+0.5*log2(0.5))++p3*(-(0.1*log2(0.1)+0.5*log2(0.5)+0.4*log2(0.4)));

3.      КОДИРОВАНИЕ
МЕТОДОМ ШЕННОНА-ФАНО

Кодирование Шеннона — Фано (англ. Shannon-Fano coding) — алгоритм
префиксного неоднородного кодирования. Относится к вероятностным методам сжатия
(точнее, методам контекстного моделирования нулевого порядка). Алгоритм Шеннона
— Фано использует избыточность сообщения, заключённую в неоднородном
распределении частот символов его (первичного) алфавита, то есть заменяет коды
более частых символов короткими двоичными последовательностями, а коды более
редких символов — более длинными двоичными последовательностями. Алгоритм был
независимо друг от друга разработан Шенноном (публикация «Математическая теория
связи», 1948 год) и, позже, Фано (опубликовано как технический отчёт).

Задание: провести кодирование по одной и блоками по две буквы, используя
метод Шеннона — Фано. Сравнить эффективности кодов (величина энтропии). Данные
взять из задачи 1.

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

Кодовые комбинации по одной букве.

Кодовые комбинации по две буквы.

Рассчитаем энтропию по формуле.

Рассчитаем
среднюю длину кодовой комбинации по формуле.

Рассчитаем
эффективность кода, согласно формуле.

Энтропия
источника. По одной букве:

Средняя
длина кодовой комбинации источника. По одной букве:

По
две буквы:

Эффективность
кода. По одной букве:

По
две буквы:

4.      КОДИРОВАНИЕ
АЛГОРИТМОМ ХАФФМАНА

Один из первых алгоритмов эффективного кодирования информации был
предложен Д.А. Хаффманом в 1952 году.

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

Символам с большей вероятностью ставятся в соответствие более короткие
коды.

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

Далее на основании этой таблицы строится дерево кодирования Хаффмана
(Н-дерево).

Задание: алфавит передаваемых сообщений состоит из независимых букв Si.
Вероятности появления каждой буквы в сообщении заданы. Определить и сравнить
эффективность кодирования сообщений методом Хаффмена при побуквенном
кодировании и при кодировании блоками по две буквы. Вариант №23:
(0,8;0,0;0,08;0,12).

Решение. Проведем кодирование методом Шеннона-Фэно.

По одной букве.

По две буквы.

Проведем кодирование по методу Хаффмена. Исходный алфавит состоит из
нескольких букв с заданными вероятностями. Составим таблицу.

По одной букве

По две буквы.

Характеристики кода рассчитываются по тем же формулам, что и для кода
Шеннона-Фано.

Рассчитаем энтропию по формуле.

Рассчитаем
минимальную среднюю длину кодовой комбинации по формуле.

Рассчитаем
эффективность кода, согласно формуле.

Энтропия
источника. По одной букве:

По
две буквы:

Средняя
длина кодовой комбинации источника. По одной букве:

По
две буквы:

Эффективность
кода. По одной букве:

По
две буквы:

5.      ПРОПУСКНАЯ
СПОСОБНОСТЬ КАНАЛА СВЯЗИ

хаффман
код шеннон символ

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

Задание: Определить пропускную способность канала связи, по которому
передаются сигналы Si. Помехи в канале определяются матрицей условных
вероятностей P(Si / Sj). За секунду может быть передано N = 10 сигналов.

Вариант №23.

Решение. Рассчитаем условную энтропию по формуле.

Рассчитаем
пропускную способность канала связи по формуле.

Условная
энтропия.

Пропускная
способность канала связи.

заключение

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

Было выполнено 5 заданий:

.        Определить среднее количество информации, содержащееся в
сообщении, используемом три независимых символа S1, S2, S3. Известны
вероятности появления символов p(S1)=p1, p(S2)=p2, p(S3)=p3. Оценить
избыточность сообщения.

.        В условии предыдущей задачи учесть зависимость между символами,
которая задана матрицей условных вероятностей P(Si / Sj).

.        Провести кодирование по одной и блоками по две буквы, используя
метод Шеннона — Фано. Сравнить эффективности кодов (величина энтропии). Данные
взять из задачи 1.

.        Алфавит передаваемых сообщений состоит из независимых букв Si.
Вероятности появления каждой буквы в сообщении заданы. Определить и сравнить
эффективность кодирования сообщений методом Хаффмана при побуквенном
кодировании и при кодировании блоками по две буквы.

.        Определить пропускную способность канала связи, по которому
передаются сигналы Si. Помехи в канале определяются матрицей условных
вероятностей P(Si / Sj). За секунду может быть передано N = 10 сигналов.

список литературы

1.      Зверева
Е.Н. Сборник примеров и задач по основам теории информации и кодирования
сообщений/ Е.Н. Зверева, Е.Г.Лебедько. — СПб: НИУ ИТМО, 2014. — 76 с.

.        Калинцев
С.В. Методические указания к контрольной работе по курсу «Теория кодирования»/
С.В.Калинцев. -2012. — 20 с.