Инф-ка_Л11-12_И_Данные_Код-е_Адекв
.pdfСпособы измерения И
•Объёмный,
•Энтропийный,
•Алгоритмический
41
Объемный способ измерения И
Объем И – кол-во символов в сообщении.
Метод чувствителен к форме представл-я
сообщения:
1510 = 11112 = F16
или XV – в римской Системе Счисл-я
В ВычТехн вся И – в 2-ой форме:
станд-е единицы измер-я И: бит, байт.
42
Единицы измерения Д
• |
1 |
Кбайт = 210 байт, кило, |
103 |
• |
1 |
Мбайт = 220 байт, мега, |
106 |
• |
1 |
Гбайт = 230 байт, гига, |
109 |
•1 Тбайт = 240 байт, тера, 1012
•1 Пбайт = 250 байт, пета, 1015
• 1 Эбайт = 260 байт, экса, 1018
•1 Збайт = 270 байт, зетта, 1021
•1 Йбайт = 280 байт, йотта, 1024
43
Энтропийный способ измерения И
Модель метода: Поль-ль сообщения имеет представление о возможности наступления
События из некоторого множества Соб-й.
Известны Вероятности наступления этих Соб-й.
Вер-ть от 0 – невозможность Соб-я
до 1 – исполнение Соб-я обязат-е!
Примеры: бросание монеты - Вер-ть 0.5, |
0 |
|
Угадайте, цифра 0 или 1 ? |
||
|
э к з а м е н ы - ??? |
44 |
|
|
Энтропийный способ измерения И |
|
Общая мера неопред-ти – Энтропия (Э-я) – |
|
|
характ-ся некоторой матем-ой зависим-ю от |
|
|
вероятностей всех Соб-й множества. |
|
|
Кол-во И в сообщении опред-ся тем, на |
|
|
сколько уменьш-ся Э-я после получения |
|
|
сообщения. |
|
|
В теории И: H = log2 m , – Энтропия, |
|
|
m – число возможных равновер-х выборов: |
|
|
m = 1 |
H = 0 |
|
m = 2 |
H = 1 |
45 |
|
|
|
Пример: Колода карт – 32 различные карты.
При выборе заданной карты количество И:
H = log2 32 = 5.
Это равно числу 2-х вопросов с ответами
|
да или нет, выбор дамы пик: |
|
|
1. |
Карта красной масти ? |
«Нет» |
0 |
2. |
Трефы ? |
«Нет» |
0 |
3. |
Одна из 4-х старших ? |
«Да» |
1 |
4. |
Одна из 2-х старших ? |
«Нет» |
0 |
5. |
Дама ? |
«Да» |
1 |
0 0 1 0 1 – послед-сть 2-х символов
46
Энтропийный способ измерения И
На практике чаще Вер-ти Соб-й множества
различны. В 1948 г. К. Шеннон:
H= -∑ pi log2 pi , i = 1, m,
–Э-я для m событий с Вер-ми pi .
Н зависит от m и от Вер-ей pi
47
Шеннон, Клод Элвуд
48
Энтропийный способ измерения И
Пример для расчета
Колода карт – 32 различные карты.
При выборе заданной карты количество И:
H = log2 32 = 5.
Расчет по ф-ле H = -∑ pi log2 pi , i = 1, m, m = 32 ,
pi = 1 / 32
Н - ?
49
Алг-ий способ оценки И в сообщении
Сложность сообщения опред-ся как min-е число внутренних состояний машины Тьюринга,
требующихся для воспроизвед-я сообщения.
Пример: 000…0 вывод 1-го символа,
0101…01 чуть сложнее,
случайная последов-ть 0 1 – длина П зависит от
длины последов-ти.
Кол-я оценка – сложность П для воспр-я посл-ти.
50