Решение задач по теме «Количество информации»
При хранении и передаче информации с помощью технических устройств информацию следует рассматривать как последовательность символов — знаков (букв, цифр, кодов цветов точек изображения и т.д.).
| N=2 i | i | Информационный вес символа, бит |
| N | Мощность алфавита | |
| I=K*i | K | Количество символов в тексте |
| I | Информационный объем текста |
Возможны следующие сочетания известных (Дано) и искомых (Найти) величин:
| Тип | Дано | Найти | Формула |
|---|---|---|---|
| 1 | i | N | N=2 i |
| 2 | N | i | |
| 3 | i,K | I | I=K*i |
| 4 | i,I | K | |
| 5 | I, K | i | |
| 6 | N, K | I | Обе формулы |
| 7 | N, I | K | |
| 8 | I, K | N |
Задача 1. Получено сообщение, информационный объем которого равен 32 битам. чему равен этот объем в байтах?
Решение: В одном байте 8 бит. 32:8=4
Ответ: 4 байта.
Задача 2. Объем информацинного сообщения 12582912 битов выразить в килобайтах и мегабайтах.
Решение: Поскольку 1Кбайт=1024 байт=1024*8 бит, то 12582912:(1024*8)=1536 Кбайт и
поскольку 1Мбайт=1024 Кбайт, то 1536:1024=1,5 Мбайт
Ответ:1536Кбайт и 1,5Мбайт.
Задача 3. Компьютер имеет оперативную память 512 Мб. Количество соответствующих этой величине бит больше:
1) 10 000 000 000бит 2) 8 000 000 000бит 3) 6 000 000 000бит 4) 4 000 000 000бит Решение: 512*1024*1024*8 бит=4294967296 бит.
Ответ: 4.
Задача 4. Определить количество битов в двух мегабайтах, используя для чисел только степени 2.
Решение: Поскольку 1байт=8битам=2 3 битам, а 1Мбайт=2 10 Кбайт=2 20 байт=2 23 бит. Отсюда, 2Мбайт=2 24 бит.
Ответ: 2 24 бит.
Задача 5. Сколько мегабайт информации содержит сообщение объемом 2 23 бит?
Решение: Поскольку 1байт=8битам=2 3 битам, то
2 23 бит=2 23 *2 23 *2 3 бит=2 10 2 10 байт=2 10 Кбайт=1Мбайт.
Ответ: 1Мбайт
Задача 6. Один символ алфавита «весит» 4 бита. Сколько символов в этом алфавите?
Решение:
Дано:
| i=4 | По формуле N=2 i находим N=2 4 , N=16 |
| Найти: N — ? |
Ответ: 16
Задача 7. Каждый символ алфавита записан с помощью 8 цифр двоичного кода. Сколько символов в этом алфавите?
Решение:
Дано:
| i=8 | По формуле N=2 i находим N=2 8 , N=256 |
| Найти:N — ? |
Ответ: 256
Задача 8. Алфавит русского языка иногда оценивают в 32 буквы. Каков информационный вес одной буквы такого сокращенного русского алфавита?
Решение:
Дано:
| N=32 | По формуле N=2 i находим 32=2 i , 2 5 =2 i ,i=5 |
| Найти: i— ? |
Ответ: 5
Задача 9. Алфавит состоит из 100 символов. Какое количество информации несет один символ этого алфавита?
Решение:
Дано:
| N=100 | По формуле N=2 i находим 32=2 i , 2 5 =2 i ,i=5 |
| Найти: i— ? |
Ответ: 5
Задача 10. У племени «чичевоков» в алфавите 24 буквы и 8 цифр. Знаков препинания и арифметических знаков нет. Какое минимальное количество двоичных разрядов им необходимо для кодирования всех символов? Учтите, что слова надо отделять друг от друга!
Решение:
Дано:
| N=24+8=32 | По формуле N=2 i находим 32=2 i , 2 5 =2 i ,i=5 |
| Найти: i— ? |
Ответ: 5
Задача 11. Книга, набранная с помощью компьютера, содержит 150 страниц. На каждой странице — 40 строк, в каждой строке — 60 символов. Каков объем информации в книге? Ответ дайте в килобайтах и мегабайтах
Решение:
Дано:
| K=360000 | Определим количество символов в книге 150*40*60=360000. Один символ занимает один байт. По формуле I=K*iнаходим I=360000байт 360000:1024=351Кбайт=0,4Мбайт |
| Найти: I— ? |
Ответ: 351Кбайт или 0,4Мбайт
Задача 12. Информационный объем текста книги, набранной на компьютере с использованием кодировки Unicode, — 128 килобайт. Определить количество символов в тексте книги.
Решение:
Дано:
| I=128Кбайт,i=2байт | В кодировке Unicode один символ занимает 2 байта. Из формулыI=K*i выразимK=I/i,K=128*1024:2=65536 |
| Найти: K— ? |
Ответ: 65536
Задача 13.Информационное сообщение объемом 1,5 Кб содержит 3072 символа. Определить информационный вес одного символа использованного алфавита
Решение:
Дано:
| I=1,5Кбайт,K=3072 | Из формулы I=K*i выразимi=I/K,i=1,5*1024*8:3072=4 |
| Найти: i— ? |
Ответ: 4
Задача 14.Сообщение, записанное буквами из 64-символьного алфавита, содержит 20 символов. Какой объем информации оно несет?
Решение:
Дано:
| N=64, K=20 | По формуле N=2 i находим 64=2 i , 2 6 =2 i ,i=6. По формуле I=K*i I=20*6=120 |
| Найти: I— ? |
Ответ: 120бит
Задача 15. Сколько символов содержит сообщение, записанное с помощью 16-символьного алфавита, если его объем составил 1/16 часть мегабайта?
Решение:
Дано:
| N=16, I=1/16 Мбайт | По формуле N=2 i находим 16=2 i , 2 4 =2 i ,i=4. Из формулы I=K*i выразим K=I/i, K=(1/16)*1024*1024*8/4=131072 |
| Найти: K— ? |
Ответ: 131072
Задача 16. Объем сообщения, содержащего 2048 символов,составил 1/512 часть мегабайта. Каков размер алфавита, с помощью которого записано сообщение?
Решение:
Дано:
Какое кол во информации
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`, что Обозначение:
На параметры логарифма налагаются некоторые ограничения. Число `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` бита информации.
Если в результате вычислений по формуле Хартли получилось нецелое число, а в задаче требуется указать целое число бит, то результат следует округлить в большую сторону.
Как измерить количество информации?
Мы ежедневно работаем с информацией из разных источников. При этом каждый из нас имеет некоторые интуитивные представления о том, что означает, что один источник является для нас более информативным, чем другой. Однако далеко не всегда понятно, как это правильно определить формально. Не всегда большое количество текста означает большое количество информации. Например, среди СМИ распространена практика, когда короткое сообщение из ленты информационного агентства переписывают в большую новость, но при этом не добавляют никакой «новой информации». Или другой пример: рассмотрим текстовый файл с романом Л.Н. Толстого «Война и мир» в кодировке UTF-8. Его размер — 3.2 Мб. Сколько информации содержится в этом файле? Изменится ли это количество, если файл перекодировать в другую кодировку? А если заархивировать? Сколько информации вы получите, если прочитаете этот файл? А если прочитаете его второй раз?
По мотивам открытой лекции для Computer Science центра рассказываю о том, как можно математически подойти к определению понятия «количество информации».
В классической статье А.Н. Колмогорова «Три подхода к определению понятия количества информации» (1965) рассматривают три способа это сделать:
комбинаторный (информация по Хартли),
вероятностный (энтропия Шеннона),
алгоритмический (колмогоровская сложность).
Мы будем следовать этому плану.
Комбинаторный подход: информация по Хартли
Мы начнём самого простого и естественного подхода, предложенного Хартли в 1928 году.
Пусть задано некоторое конечное множество . Количеством информации в будем называть .
Можно интерпретировать это определение следующим образом: нам нужно битов для описания элемента из .
Почему мы используем биты? Можно использовать и другие единицы измерения, например, триты или байты, но тогда нужно изменить основание логарифма на 3 или 256, соответственно. В дальшейшем все логарифмы будут по основанию 2.
Этого определения уже достаточно для того, чтобы измерить количество информации в некотором сообщении. Пусть про стало известно, что . Теперь нам достаточно битов для описания , таким образом нам сообщили битов информации.
Пример
Загадано целое число от до . Нам сообщили, что делится на . Сколько информации нам сообщили?
Воспользуемся рассуждением выше.
(Тот факт, что некоторое сообщение может содержать нецелое количество битов, может показаться немного неожиданным.)
Можно ещё сказать, что сообщение, уменшающее пространство поиска в раз приносит битов информации. В данном примере пространство поиска уменьшилось в 1000/166 раз.
Интересно, что одного этого определения уже достаточно для того, чтобы решать довольно нетривиальные задачи.
Применение: цена информации
Загадано целое число от до . Разрешается задавать любые вопросы на ДА/НЕТ. Если ответ на вопрос «ДА», то мы должны заплатить рубль, если ответ «НЕТ» — два рубля. Сколько нужно заплатить для отгадывания числа ?
Любой вопрос можно сформулировать как вопрос о принадлежности некоторому множеству, поэтому мы будем считать, что все вопросы имеют вид «?» для некоторого множества .
Каким образом нужно задавать вопросы? Нам бы хотелось, чтобы вне зависимости от ответа цена за бит информации была постоянной. Другими словами, в случае ответа «НЕТ» и заплатив два рубля мы должны узнать в два больше информации, чем при ответе «ДА». Давайте запишем это формально.
Пусть , тогда . Подставляем и получаем, что
Это эквивалентно квадратному уравнению Положительный корень этого уравнения . Таким образом, при любом ответе мы заплатим рублей за бит информации, а в сумме мы заплатим примернорублей (с точностью до округления).
Осталось понять, как выбирать такие множества . Будем выбирать в качестве непрерывные отрезки прямой. Пусть нам известно, что принадлежит отрезку (изначально это отрезок ). В следующего множества возмём отрезок , где. Тогда за каждый заплаченный рубль текущий отрезок будет уменьшаться в раз. Когда длина отрезка станет меньше единицы, мы однозначно определим . Поэтому цена отгадывания не будет превосходить
Приведённое рассуждение доказывает только верхнюю оценку. Можно доказать и нижнюю оценку: для любого способа задавать вопросы будет такое число , для отгадывания которого придётся заплатить не менее рублей.
Вероятностный подход: энтропия Шеннона
Вероятностный подход, предложенный Клодом Шенноном в 1948 году, обобщает определение Хартли на случай, когда не все элементы множества являются равнозначными. Вместо множества в этом подходе мы будем рассматривать вероятностное распределение на множестве и оценивать среднее по распределению количество информации, которое содержит случайная величина.
Пусть задана случайная величина , принимающая различных значений с вероятностями . Энтропия Шеннона случайной величины определяется как
(По непрерывности тут нужно доопределить .)
Энтропия Шеннона оценивает среднее количество информации (математическое ожидание), которое содержится в значениях случайной величины.
При первом взгляде на это определение, может показаться совершенно непонятно откуда оно берётся. Шеннон подошёл к этой задаче чисто математически: сформулировал требования к функции и доказал, что это единственная функция, удовлетворяющая сформулированным требованиям.
Я попробую объяснить происхождение этой формулы как обобщение информации по Хартли. Нам бы хотелось, чтобы это определение согласовывалось с определением Хартли, т.е. должны выполняться следующие «граничные условия»:
если все исходы равновероятны (), то ,
если распределение вырождено (и для всех ), то .
Будем искать в виде математического ожидания количества информации, которую мы получаем от каждого возможного значения .
Как оценить, сколько информации содержится в событии ? Пусть — всё пространство элементарных исходов. Тогда событие соответствует множеству элементарных исходов меры . Если произошло событие , то размер множества согласованных с этим событием элементарных исходов уменьшается с до , т.е. событие сообщает нам битов информации. Тут мы пользуемся тем, что количество информации в сообщении, которое уменьшает размер пространство поиска в раз приносит битов информации.
Примеры
Подбрасывание честной монетки. Рассмотрим случайную величину, соответствующую подбрасыванию честной монетки. Выпадение орла и выпадение решки равновероятны, следовательно . Тогда Это соответствует информации по Хартли в двухэлементном множестве.
Подбрасывание нечестной монетки. Пусть . Тогда
Если проанализировать это выражение, то можно заключить, что чем дальше монетка от честной, тем меньше энтропия соответствующей случайной величины.
Бросок игрального кубика. Аналогично честной монетке. Все грани выпадают равновероятно, т.е.. Следовательно, Снова получаем совпадение с информацией по Хартли.
Выбор автомобиля на сайте. Рассмотрим выбор автомобиля на сайте. Как определить, сколько информации в среднем содержит параметр «цвет»? Пусть всего доступны цветов. Обозначим через долю автомобилей с цветом . Пусть белый соответствует у 1/10 доле всех автомобилей. Тогда выбор белого цвета приносит битов информации (по Хартли). В среднем выбор цвета приносит . Это соответствует энтропии Шеннона случайной величины, равномерно распределённой на множестве всех автомобилей.
Свойства энтропии Шеннона
Для случайной величины , принимающей значений с вероятностями , выполняются следующие соотношения.
Чем распределение ближе к равномерному, тем больше энтропия Шеннона.
Энтропия пары
Понятие энтропии Шеннона можно обобщить для пары случайных величин. Аналогично это обощается для тройки, четвёрки и т.д.
Пусть совместно распределённые случайные величины и принимают значения и , соответственно. Энтропия пары случайных величин и определяется следующим соотношением:
Примеры
Рассмотрим эксперимент с выбрасыванием двух игральных кубиков — синего и красного.
Пусть соответствует числу на синем кубике, а — числу на красном кубике. Легко проверить, что Это можно объяснить так: есть 36 различных вариантов значений и , и все они равновероятны. Поэтому и получаем .
Пусть теперь соответствует сумме чисел на кубиках, а — произведению. Легко понять, что т.к. теперь некоторые пары значений и соответствуют нескольким парам чисел на кубиках, т.е. вариантов значений и меньше 36. Например, соответствует значениям (1,3) и (3,1).
Свойства энтропии Шеннона пары случайных величин
Для энтропии пары выполняются следующие свойства.
Условная энтропия Шеннона
Теперь давайте научимся вычислять условную энтропию одной случайной величины относительно другой.
Условная энтропия относительно определяется следующим соотношением:
Примеры
Рассмотрим снова примеры про два игральных кубика.
Пусть соответствует числу на синем кубике, а — числу на красном кубике. Легко проверить, что , т.к. знание никак не позволяет получить какую-либо информацию про значение .
Пусть теперь соответствует сумме чисел на кубиках, а — произведению. В этом случае зная произведение чисел на кубиках вы уже что-то знаете про возможные суммы (например, если произведение равно 1, то сумма определяется однозначно), поэтому . Условная энтропия позволяет ответить на вопрос, сколько информации приносит величина , если вы уже знаете величину .
Свойства условной энтропии
Условная энтропия обладает следующими свойствами
однозначно определяется по .
Взаимная информация
Ещё одна информационная величина, которую мы введём в этом разделе — это взаимная информация двух случайных величин.
Информация в о величине (взаимная информация случайных величин и ) определяется следующим соотношением
Примеры
И снова обратимся к примерам с двумя игральными кубиками.
Пусть соответствует числу на синем кубике, а — числу на красном кубике. Легко проверить, что , т.к. знание никак не позволяет определить .
Пусть теперь соответствует сумме чисел на кубиках, а — произведению. Взаимная информация позволяет оценить количество общей информации, между двумя случайными величинами (в этом случае ).
Свойства взаимной информации
Выполняются следующие соотношения.
. Т.е. определение взаимной информации симметрично и его можно переписать так:
Все информационные величины, которые мы определили к этому моменту можно проиллюстрировать при помощи кругов Эйлера.
Мы пойдём дальше и рассмотрим информационную величину, зависящую от трёх случайных величин.
Пусть , и совместно распределены. Информация в о при условии определяется следующим соотношением:
Свойства такие же как и обычной взаимной информации, нужно только добавить соответствующее условие ко всем членам.
Всё, что мы успели определить можно удобно проиллюстрировать при помощи трёх кругов Эйлера.
Из этой иллюстрации можно вывести все определения и соотношения на информационные величины.
Мы не будем продолжать дальше и рассматривать четыре случайные величины по трём причинам. Во-первых, рисовать четыре круга Эйлера со всеми возможными областями — это непросто. Во-вторых, для двух и трёх случайных величин почти все возможные соотношения можно вывести из кругов Эйлера, а для четырёх случайных величин это уже не так. И в третьих, уже для трёх случайных величин возникают неприятные эффекты, демонстрирующие, что дальше будет хуже.
Рассмотрим треугольник в пересечении всех трёх кругов , и . Этот треугольник соответствуют взаимной информации трёх случайных величин . Проблема с этой информационной величиной заключается в том, что ей не удаётся придать какой-то «физический» смысл. Более того, в отличие от всех остальных величин на картинке может быть отрицательной!
Рассмотрим пример трёх случайных величин равномерно распределённых на . Пусть и будут независимы, а . Легко проверить, что . При этом . В то же время . Получается следующая картинка.
Мы знаем, что . При этом . Получается, что , а , т.е. для таких случайных величин.
Применение энтропии Шеннона: кодирование
В этом разделе мы обсудим, как энтропия Шеннона возникает в теории кодирования. Будем рассматривать коды, которые кодируют каждый символ по отдельности.
Пусть задан алфавит . Код — это отображение из в . Код называется однозначно декодируемым, если любое сообщение, полученное применением к символам некоторого текста, декодируется однозначно.
Код называется префиксным (prefix-free), если нет двух символов и таких, что является префиксом .
Префиксные коды являются однозначно декодируемыми. Действительно, при декодировании префиксного кода легко понять, где находятся границы кодов отдельных символов.
Теорема [Шеннон]. Для любого однозначно декодируемого кода существует префиксный код с теми же длинами кодов символов.
Таким образом для изучения однозначно декодируемых кодов достаточно рассматривать только префиксные коды.
Задача об оптимальном кодировании.
Дан текст . Нужно найти такой код , что
Пусть . Обозначим через частоту, с которой символ встречается в . Тогда выражение выше можно переписать как
Следующая теорема могла встречаться вам в курсе алгоритмов.
Теорема [Хаффман]. Код Хаффмана, построенный по , является оптимальным префиксным кодом.
Алгоритм Хаффмана по набору частот эффективно строит оптимальный код для задачи оптимального кодирования.
Связь с энтропией
Имеют место две следующие оценки.
Теорема [Шеннон]. Для любого однозначно декодируемого кода выполняется
Теорема [Шеннон]. Для любых значений существует префиксный код , такой что
Рассмотрим случайную величину , равномерно распределённую на символах текста . Получим, что . Таким образом, эти две теоремы задают оценку на среднюю длину кода символа при оптимальном кодировании, т.е. и для кодирования Хаффмана.
Следовательно, длину кода Хаффмана текста можно оценить, как
Применение энтропии Шеннона: шифрования с закрытым ключом
Рассмотрим простейшую схему шифрования с закрытым ключом. Шифрование сообщения с ключом шифрования выполняется при помощи алгоритма шифрования . В результате получается шифрограмма . Зная получатель шифрограммы восстанавливает исходное сообщение : .
Мы будем анализировать эту схему с помощью аппарата энтропии Шеннона. Пусть и являются случайными величинами. Противник не знает и , но знает , которая так же является случайной величиной.
Для совершенной схемы шифрования (perfect secrecy) выполняются следующие соотношения:
, т.е. шифрограмма однозначно определяется по ключу и сообщению.
, т.е. исходное сообщение однозначно восстанавливается по шифрограмме и ключу.
, т.е. в отсутствие ключа из шифрограммы нельзя получить никакой информации о пересылаемом сообщении.
Теорема [Шеннон]. , даже если условие нарушается (т.е. алгоритм использует случайные биты).
Эта теорема утверждает, что для совершенной схемы шифрования длина ключа должна быть не менее длины сообщения. Другими словами, если вы хотите зашифровать и передать своему знакомому файл размера 1Гб, то для этого вы заранее должны встретиться и обменяться закрытым ключом размера не менее 1Гб. И конечно, этот ключ можно использовать только однажды. Таким образом, самая оптимальная совершенная схема шифрования — это «одноразовый блокнот», в котором длина ключа совпадает с длиной сообщения.
Если же вы используете ключ, который короче пересылаемого сообщения, то шифрограмма раскрывает некоторую информацию о зашифрованном сообщении. Причём количество этой информации можно оценить, как разницу между энтропией сообщения и энтропией ключа. Если вы используете пароль из 10 символов при пересылке файла размера 1Гб, то вы разглашаете примерно 1Гб – 10 байт.
Это всё звучит очень печально, но не всё так плохо. Мы ведь никак не учитываем вычислительную мощь противника, т.е. мы не ограничиваем количество времени, которое противнику потребуется на выделение этой информации.
Современная криптография строится на предположении об ограниченности вычислительных возможностей противника. Тут есть свои проблемы, а именно отсутствие математического доказательства криптографической стойкости (все доказательства строятся на различных предположениях), так что может оказаться, что вся эта криптография бесполезна (подробнее можно почитать в статье о мирах Рассела Импальяццо, которая переведена на хабре), но это уже совсем другая история.
Доказательство. Нарисуем картинку для трёх случайных величин и отметим то, что нам известно.
, следовательно , а значит .
(по свойству взаимной информации), следовательно , а значит .
В доказательстве мы действительно не воспользовались тем, что .
Алгоритмический подход: колмогоровская сложность
Подход Шеннона хорош для случайных величин, но если мы попробуем применить его к текстам, то выходит, что количество информации в тексте зависит только от частот символов, но не зависит от их порядка. При таком подходе получается, что в «Войне и мире» и в тексте, который получается сортировкой всех знаков в «Войне и мире», содержится одинаковое количество информации. Колмогоров предложил подход, позволяющий измерять количество информации в конкретных объектах (строках), а не в случайных величинах.
Внимание. До этого момента я старался следить за математической строгостью формулировок. Для того, чтобы двигаться дальше в том же ключе, мне потребовалось бы предположить, что читатель неплохо знаком с математической логикой и теорией вычислимости. Я пойду более простым путём и просто буду махать руками, заметая под ковёр некоторые подробности. Однако, все утверждения и рассуждения дальше можно математически строго сформулировать и доказать.
Нам потребуется зафиксировать способ описания битовой строки. Чтобы не углубляться в рассуждения про машины Тьюринга, мы будем описывать строки на языках программирования. Нужно только сделать оговорку, что программы на этих языках будут запускаться на компьютере с неограниченным объёмом оперативной памяти (иначе мы получили бы более слабую вычислительную модель, чем машина Тьюринга).
Сложностью строки относительно языка программирования называется длина кратчайшей программы, которая выводит .
Таким образом сложность «Войны и мира» относительноя языка Python — это длина кратчайшей программы на Python, которая печатает текст «Войны и мира». Естественным образом сложность отсортированной версии «Войны и мира» относительно языка Python получится значительно меньше, т.к. её можно предварительно закодировать при помощи RLE.
Сравнение языков программирования
Дальше нам потребуется научиться любимой забаве всех программистов — сравнению языков программирования.
Будем говорить, что язык не хуже языка программирования и обозначать , если существует константа такая, что для для всех выполняется
Исходя из этого определения получается, что язык Python не хуже (!) этого вашего Haskell! И я это докажу. В качестве константы мы возьмём длину реализации интепретатора Haskell на Python. Таким образом, любая программа на Haskell переделывается в программу на Python просто дописыванием к ней интерпретатора Haskell на Python.
Соломонов и Колмогоров пошли дальше и доказали существования оптимального языка программирования.
Теорема [Соломонова-Колмогорова]. Существует способ описания (язык программирования) такой, что для любого другого способа описания выполняется .
И да, некоторые уже наверное догадались, что — это JavaScript. Или любой другой Тьюринг полный язык программирования.
Это приводит нас к следующему определению, предложенному Колмогоровым в 1965 году.
Колмогоровской сложностью строки будем называть её сложность относительно оптимального способа описания и будем обозначать .
Важно понимать, что при разных выборах оптимального языка программирования колмогоровская сложность будет отличаться, но только на константу. Для любых двух оптимальных языков программирования и выполняется и , т.е. существует такая константа , что Это объясняет, почему в этой науке аддитивные константы принято игнорировать.
При этом для конкретной строки и конкретного выбора колмогоровская сложность определена однозначно.
Свойства колмогоровской сложности
Начнём с простых свойств. Колмогоровская сложность обладает следующими свойствами.
Существует такая, что для всех .
Существует такая, что для всех .
Первое свойство выполняется потому, что мы всегда можем зашить строку в саму программу. Второе свойство верно, т.к. из программы, выводящей строку , легко сделать программу, которая выводит эту строку дважды.
Примеры
Какова колмогоровская сложность «Войны и мира»? Это некоторая константа, зависящая от нашего выбора .
Какова колмогоровская сложность первых знаков числа ? Про число любят расказывать, что там вероятно встречается любая подстрока. Это могло бы свидетельствовать, что в числе заключено очень много информации (все возможные строко). Однако с точки зрения колмогоровской сложности число — это простая последовательность. Ведь для её построения можно написать программу фиксированного размера, в которую достаточно вписать числчтобы она вывела первые цифр числа . Таким образом, колмогоровская сложность не превосходит для некоторой константы .
Несжимаемые строки
Важнейшее свойство колмогоровской сложности заключается в существовании сложных (несжимаемых строк). Проверьте себя и попробуйте объяснить, почему не бывает идеальных архиваторов, которые умели бы сжимать любые файлы хотя бы на 1 байт, и при этом позволяли бы однозначно разархивировать результат.
В терминах колмогоровской сложности это можно сформулировать так.
Вопрос. Существует ли такая длина строки , что для любой строки колмогоровская сложность меньше ?
Следующая теорема даёт отрицательный ответ на этот вопрос.
Теорема. Для любого существует такой, что .
Доказательство. Битовых строк длины всего . Число строк сложности меньше не превосходит число программ длины меньше , т.е. таких программ не больше чем
Таким образом, для какой-то строки гарантированно не хватит программы.
Верна и более сильная теорема.
Теорема. Существует такое, что для слов длины верно
Другими словами, почти все строки длины имеют почти максимальную сложность.
Колмогоровская сложность: вычислимость
В этом разделе мы поговорим про вычислимость колмогоровской сложности. Я не буду давать формально определение вычислимости, а буду опираться на интуитивные предствления читателей.
Теорема. Не существует программы, которая по двоичной записи числа выводит строку , такую что .
Эта теорема говорит о том, что не существует программы-генератора, которая умела бы генерировать сложные строки по запросу.
Доказательство. Проведём доказетельство от противного. Пусть такая программа существует и . Тогда с одной стороны сложность не меньше , а с другой стороны мы можем описать при помощи битов и кода программы.
Это приводит нас к противоречию, т.к. при достаточно больших значениях неизбежно станет больше, чем .
Как следствие мы получаем невычислимость колмогоровской сложности.
Следствие. Отображение не является вычислимым.
Опять же, предположим, что это нет так и существует программа , которая по строку вычисляет её колмогоровскую сложность. Тогда на основе программы можно реализовать программу из теоремы выше: она будет перебирать все строки длины не более и находить лексикографически первую, для которой сложность будет не меньше . А мы уже доказали, что такой программы не существует.
Связь с энтропией Шеннона
Теорема. Пусть длины содержит единиц и нулей, тогда
Я надеюсь, что вы уже узнали энтропию Шеннона для случайной величины с двумя значениями с вероятностями и .
Для колмогоровской сложности можно проделать весь путь, который мы проделали для энтропии Шеннона: определить условную колмогоровскую сложность, сложность пары строк, взаимную информацию и условную взаимную информацию и т.д. При этом формулы будут повторять формулы для энтропии Шеннона с точностью до . Однако это тема для отдельной статьи.
Применение колмогоровской сложности: бесконечность множества простых чисел
Начнём с довольно игрушечного применения. С помощью колмогоровской сложности мы докажем следующую теорему, знакомую нам со школы.
Теорема. Простых чисел бесконечно много.
Очевидно, что для доказательства этой теоремы никакая колмогоровская сложность не нужна. Однако на этом примере я смогу продемонстрировать основные идеи применения колмогоровской сложности в более сложных ситуациях.
Доказательство. Проведём доказательство от обратного. Пусть существует всего простых чисел: . Тогда любое натуральное раскладывается на степени простых:
т.е. определяется набором степеней . Каждое , т.е. задаётся битами. Поэтому любое можно задать при помощи битов (помним, что — это константа).
Теперь воспользуемся теоремой о существовании несжимаемых строк. Как следствие, мы можем заключить, что существуют -битовые числа сложности не менее (можно взять сложную строку и приписать в начало единицу). Получается, что сложное число можно задать при помощи небольшого числа битов.
Применение колмогоровской сложности: алгоритмическая случайность
Колмогоровская сложность позволяет решить следующую проблему из классической теории вероятностей.
Пусть в лаборатории живёт обезьянка, которую научили печатать на печатной машинке так, что каждую кнопку она нажимает с одинаковой вероятность. Вам предлагается посмотреть на лист печатного текста и сказать, верите ли вы, что его напечатала эта обезьянка. Вы смотрите на лист и видите, что это первая страница «Гамлета» Шекспира. Поверите ли вы? Очевидно, что нет. Хорошо, а если это не Шекспир, а, скажем, текст детектива Дарьи Донцовой? Скорей всего тоже не поверите. А если просто какой-то набор русских слов? Опять же, очень сомневаюсь, что вы поверите.
Внимание, вопрос. А как объяснить, почему вы не верите? Давайте для простоты считать, что на странице помещается 2000 знаков и всего на машинке есть 80 знаков. Вы можете резонно заметить, что вероятность того, что обезьянка случайным образом породила текст «Гамлета» порядка , что астрономически мало. Это верно.
Теперь предположим, что вам показали текст, который вас устроил (он с вашей точки зрения будет похож на «случайный»). Но ведь вероятность его появления тоже будет порядка . Как же вы определяете, что один текст выглядит «случайным», а другой — не выглядит?
Колмогоровская сложность позволяет дать формальный ответ на этот вопрос. Если у текста отстутствует короткое описание (т.е. в нём нет каких-то закономерностей, которые можно было бы использовать для сжатия), то такую строку можно назвать случайной. И как мы увидели выше почти все строки имеют большую колмогоровскую сложность. Поэтому, когда вы видите строку с закономерностями, т.е. маленькой колмогоровской сложности, то это соответствует очень редкому событию. В противоположность наблюдению строки без закономерностей. Вероятность увидеть строку без закономерностей близка к 1.
Это обобщается на случай бесконечных последовательностей. Пусть . Как определить понятие случайной последовательности?
(неформальное определение)
Последовательность случайна по Мартину–Лёфу, если каждый её префикс является несжимаемым.
Оказывается, что это очень хорошее определение случайных последовательностей, т.к. оно обладает ожидаемыми свойствами.
Свойства случайных последовательностей
Почти все последовательности являются случайными по Мартину–Лёфу, а мера неслучайных равна .
Всякая случайная по Мартину-Лёфу последовательность невычислима.
Если случайная по Мартин-Лёфу, то
Заключение
Если вам интересно изучить эту тему подробнее, то я рекомендую обратиться к следующим источникам.
Верещагин Н.К., Щепин Е.В. Информация, кодирование и предсказание. МЦНМО. (нет в свободном доступе, но pdf продаётся за копейки)
Курс «Введение в теорию информации» А.Е. Ромащенко в Computer Science клубе.
Если вам интересны подобные материалы, подписывайтесь в соцсетях на CS клуб и CS центр, а так же на наши каналы на youtube: CS клуб, CS центр.
5. Количество информации. Измерение информации. Единицы измерения
За единицу количества информации принимается такое количество информации, которое содержит сообщение, уменьшающее неопределенность в два раза. Такая единица названа «бит».
Для информации существуют свои единицы измерения информации. Если рассматривать сообщения информации как последовательность знаков, то их можно представлять битами, а измерять в байтах, килобайтах, мегабайтах, гигабайтах, терабайтах и петабайтах.
Давайте разберемся с этим, ведь нам придется измерять объем памяти и быстродействие компьютера.
Единицей измерения количества информации является бит – это наименьшая (элементарная) единица.
1бит – это количество информации, содержащейся в сообщении, которое вдвое уменьшает неопределенность знаний о чем-либо.
Байт – основная единица измерения количества информации.
Байтом называется последовательность из 8 битов.
Байт – довольно мелкая единица измерения информации. Например, 1 символ – это 1 байт.
Производные единицы измерения количества информации
1 килобайт (Кб)=1024 байта =210 байтов
1 мегабайт (Мб)=1024 килобайта =210 килобайтов=220 байтов
1 гигабайт (Гб)=1024 мегабайта =210 мегабайтов=230 байтов
1 терабайт (Гб)=1024 гигабайта =210 гигабайтов=240 байтов
Запомните, приставка КИЛО в информатике – это не 1000, а 1024, то есть 210 .
Методы измерения количества информации
Итак, количество информации в 1 бит вдвое уменьшает неопределенность знаний. Связь же между количеством возможных событий N и количеством информации I определяется формулой Хартли:
Алфавитный подход к измерению количества информации
При этом подходе отвлекаются от содержания (смысла) информации и рассматривают ее как последовательность знаков определенной знаковой системы. Набор символов языка, т.е. его алфавит можно рассматривать как различные возможные события. Тогда, если считать, что появление символов в сообщении равновероятно, по формуле Хартли можно рассчитать, какое количество информации несет в себе каждый символ:
Вероятностный подход к измерению количества информации
Этот подход применяют, когда возможные события имеют различные вероятности реализации. В этом случае количество информации определяют по формуле Шеннона:
, где
I – количество информации,
N – количество возможных событий,
Pi – вероятность i-го события.
6. Кодирование информации различных видов
1.6.1. КОДИРОВАНИЕ ЧИСЕЛ.
Используя n бит, можно записывать двоичные коды чисел от 0 до 2n-1, всего 2n чисел.
1) Кодирование положительных чисел: Для записи положительных чисел в байте заданное число слева дополняют нулями до восьми цифр. Эти нули называют незначимыми.
Например: записать в байте число 1310 = 11012
2) Кодирование отрицательных чисел:Наибольшее положительное число, которое можно записать в байт, — это 127, поэтому для записи отрицательных чисел используют числа с 128-го по 255-е. В этом случае, чтобы записать отрицательное число, к нему добавляют 256, и полученное число записывают в ячейку.
1.6.2. КОДИРОВАНИЕ ТЕКСТА.
Соответствие между набором букв и числами называется кодировкой символа. Как правило, код символа хранится в одном байте, поэтому коды символов могут принимать значение от 0 до 255. Такие кодировки называют однобайтными. Они позволяют использовать 256 символов. Таблица кодов символов называется ASCII (American StandardCodeforInformationInterchange- Американский стандартный код для обмена информацией). Таблица ASCII-кодов состоит из двух частей:
Коды от 0 до 127 одинаковы для всех IBM-PC совместимых компьютеров и содержат:
коды управляющих символов;
коды цифр, арифметических операций, знаков препинания;
некоторые специальные символы;
коды больших и маленьких латинских букв.
Вторая часть таблицы (коды от 128 до 255) бывает различной в различных компьютерах. Она содержит:
коды букв национального алфавита;
коды некоторых математическихсимволов;
коды символов псевдографики.
В настоящее время все большее распространение приобретает двухбайтная кодировка Unicode. В ней коды символов могут принимать значение от 0 до 65535.
1.6.3. КОДИРОВАНИЕ ЦВЕТОВОЙ ИНФОРМАЦИИ.
Одним байтом можно закодировать 256 различных цветов. Это достаточно для рисованных изображений типа мультфильмов, но не достаточно для полноцветных изображений живой природы. Если для кодирования цвета использовать 2 байта, можно закодировать уже 65536 цветов. А если 3 байта – 16,5 млн. различных цветов. Такой режим позволяет хранить, обрабатывать и передавать изображения, не уступающие по качеству наблюдаемым в живой природе.
Из курса физики известно, что любой цвет можно представить в виде комбинации трех основных цветов: красного, зеленого, синего (их называют цветовыми составляющими). Если кодировать цвет точки с помощью 3 байтов, то первый байт выделяется красной составляющей, второй – зеленой, третий – синей. Чем больше значение байта цветовой составляющей, тем ярче этот цвет.
Белый цвет – у точки есть все цветовые составляющие, и они имеют полную яркость. Поэтому белый цвет кодируется так: 255 255 255. (11111111 11111111 11111111)
Черный цвет – отсутствие всех прочих цветов: 0 0 0. (00000000 00000000 00000000)
Серый цвет – промежуточный между черным и белым. В нем есть все цветовые составляющие, но они одинаковы и нейтрализуют друг друга.
Например: 100 100 100 или 150 150 150. (2-й вариант — ярче).
Красный цвет – все составляющие, кроме красной, равны 0. Темно-красный: 128 0 0. Ярко-красный: 255 0 0.
Зеленый цвет – 0 255 0.
Синий цвет – 0 0 255.
1.6.4. КОДИРОВАНИЕ ГРАФИЧЕСКОЙ ИНФОРМАЦИИ.
Рисунок разбивают на точки. Чем больше будет точек, и чем мельче они будут, тем точнее будет передача рисунка. Затем, двигаясь по строкам слева направо начиная с верхнего левого угла, последовательно кодируют цвет каждой точки. Для черно-белой картинки достаточно 1 байта для точки, для цветной – до 3-х байт для одной точки.
Двоичная система счисления
В двоичной системе счисления используются всего две цифры 0 и 1. Другими словами, двойка является основанием двоичной системы счисления. (Аналогично у десятичной системы основание 10.)
Чтобы научиться понимать числа в двоичной системе счисления, сначала рассмотрим, как формируются числа в привычной для нас десятичной системе счисления.
В десятичной системе счисления мы располагаем десятью знаками-цифрами (от 0 до 9). Когда счет достигает 9, то вводится новый разряд (десятки), а единицы обнуляются и счет начинается снова. После 19 разряд десятков увеличивается на 1, а единицы снова обнуляются. И так далее. Когда десятки доходят до 9, то потом появляется третий разряд – сотни.
Двоичная система счисления аналогична десятичной за исключением того, что в формировании числа участвуют всего лишь две знака-цифры: 0 и 1. Как только разряд достигает своего предела (т.е. единицы), появляется новый разряд, а старый обнуляется.
Попробуем считать в двоичной системе:
1 – это один (и это предел разряда)
11 – это три (и это снова предел)
100 – это четыре
Перевод чисел из двоичной системы счисления в десятичную
Не трудно заметить, что в двоичной системе счисления длины чисел с увеличением значения растут быстрыми темпами. Как определить, что значит вот это: 10001001? Непривычный к такой форме записи чисел человеческий мозг обычно не может понять сколько это. Неплохо бы уметь переводить двоичные числа в десятичные.
В десятичной системе счисления любое число можно представить в форме суммы единиц, десяток, сотен и т.д. Например:
1476 = 1000 + 400 + 70 + 6
Можно пойти еще дальше и разложить так:
1476 = 1 * 103 + 4 * 102 + 7 * 101 + 6 * 100
Посмотрите на эту запись внимательно. Здесь цифры 1, 4, 7 и 6 — это набор цифр из которых состоит число 1476. Все эти цифры поочередно умножаются на десять возведенную в ту или иную степень. Десять – это основание десятичной системы счисления. Степень, в которую возводится десятка – это разряд цифры за минусом единицы.
Аналогично можно разложить и любое двоичное число. Только основание здесь будет 2:
10001001 = 1*27 + 0*26 + 0*25 + 0*24 + 1*23 + 0*22 + 0*21 + 1*20
Если посчитать сумму составляющих, то в итоге мы получим десятичное число, соответствующее 10001001:
1*27 + 0*26 + 0*25 + 0*24 + 1*23 + 0*22 + 0*21 + 1*20 = 128 + 0 + 0 + 0 + 8 + 0 + 0 + 1 = 137
Т.е. число 10001001 по основанию 2 равно числу 137 по основанию 10. Записать это можно так:
Почему двоичная система счисления так распространена?
Дело в том, что двоичная система счисления – это язык вычислительной техники. Каждая цифра должна быть как-то представлена на физическом носителе. Если это десятичная система, то придется создать такое устройство, которое может быть в десяти состояниях. Это сложно. Проще изготовить физический элемент, который может быть лишь в двух состояниях (например, есть ток или нет тока). Это одна из основных причин, почему двоичной системе счисления уделяется столько внимания.
Перевод десятичного числа в двоичное
Может потребоваться перевести десятичное число в двоичное. Один из способов – это деление на два и формирование двоичного числа из остатков. Например, нужно получить из числа 77 его двоичную запись:
77 / 2 = 38 (1 остаток)
38 / 2 = 19 (0 остаток)
19 / 2 = 9 (1 остаток)
9 / 2 = 4 (1 остаток)
4 / 2 = 2 (0 остаток)
2 / 2 = 1 (0 остаток)
1 / 2 = 0 (1 остаток)
Собираем остатки вместе, начиная с конца: 1001101. Это и есть число 77 в двоичном представлении. Проверим:
1001101 = 1*26 + 0*25 + 0*24 + 1*23 + 1*22 + 0*21 + 1*20 = 64 + 0 + 0 + 8 + 4 + 0 + 1 = 77
ASCII(англ. American Standard Code for Information Interchange) — американская стандартная кодировочная таблица для печатных символов и некоторых специальных кодов. В американском варианте английского языка произносится [э́ски], тогда как в Великобритании чаще произносится [а́ски]; по-русски произносится также [а́ски] или [аски́].
ASCII представляет собой кодировку для представления десятичных цифр, латинского и национального алфавитов, знаков препинания и управляющих символов. Изначально разработанная как 7-битная, с широким распространением 8-битного байта ASCII стала восприниматься как половина 8-битной. В компьютерах обычно используют расширения ASCII с задействованным 8-м битом и второй половиной кодовой таблицы (например КОИ-8).
Поскольку ASCII изначально предназначался для обмена информацией (по телетайпу), в нём, кроме информационных символов, используются символы-команды для управления связью. Это обычный набор спецсигналов, применявшийся и в других докомпьютерных средствах обмена сообщениями (азбука Морзе, семафорная азбука), дополненный с учётом специфики устройства.
(После названия каждого символа указан его 16-ричный код)
NUL, 00 — Null, пустой. Всегда игнорировался. На перфолентах 1 представлялась отверстием, 0 — отсутствием отверстия. Поэтому пустые части перфоленты до начала и после конца сообщения состояли из таких символов. Сейчас используется во многих языках программирования как конец строки. (Строка понимается как последовательность символов.) В некоторых операционных системах NUL — последний символ любого текстового файла.
SOH, 01 — Start Of Heading, начало заголовка.
STX, 02 — Start of Text, начало текста. Текстом называлась часть сообщения, предназначенная для печати. Адрес, контрольная сумма и т. д. входили или в заголовок, или в часть сообщения после текста.
ETX, 03 — End of Text, конец текста. Здесь телетайп прекращал печатать. Использование символа Ctrl-C, имеющего код 03, для прекращения работы чего-то (обычно программы), восходит ещё к тем временам.
EOT, 04 — End of Transmission, конец передачи. В системе UNIX Ctrl-D, имеющий тот же код, означает конец файла при вводе с клавиатуры.
ENQ, 05 — Enquire. Прошу подтверждения.
ACK, 06 — Acknowledgement. Подтверждаю.
BEL, 07 — Bell, звонок, звуковой сигнал. Сейчас тоже используется. В языках программирования C и C++ обозначается \a.
BS, 08 — Backspace, возврат на один символ. Сейчас стирает предыдущий символ.
TAB, 09 — Tabulation. Обозначался также HT — Horizontal Tabulation, горизонтальная табуляция. Во многих языках программирования обозначается \t .
LF, 0A — Line Feed, перевод строки. Сейчас в конце каждой строчки текстового файла ставится либо этот символ, либо CR, либо и тот и другой (CR, затем LF), в зависимости от операционной системы. Во многих языках программирования обозначается \n и при выводе текста приводит к переводу строки.
VT, 0B — Vertical Tab, вертикальная табуляция.
FF, 0C — Form Feed, прогон страницы, новая страница.
CR, 0D — Carriage Return, возврат каретки. Во многих языках программирования этот символ, обозначаемый \r, можно использовать для возврата в начало строчки без перевода строки. В некоторых операционных системах этот же символ, обозначаемый Ctrl-M, ставится в конце каждой строчки текстового файла перед LF.
SO, 0E — Shift Out, измени цвет ленты (использовался для двуцветных лент; цвет менялся обычно на красный). В дальнейшем обозначал начало использования национальной кодировки.
SI, 0F — Shift In, обратно к Shift Out.
DLE, 10 — Data Link Escape, освобождение канала данных — следующие символы представляют собой данные, а не управляющие символы.
DC1, 11 — Device Control 1, 1-й символ управления устройством — включить устройство чтения перфоленты.
DC2, 12 — Device Control 2, 2-й символ управления устройством — включить перфоратор.
DC3, 13 — Device Control 3, 3-й символ управления устройством — выключить устройство чтения перфоленты.
DC4, 14 — Device Control 4, 4-й символ управления устройством — выключить перфоратор.
NAK, 15 — Negative Acknowledgment, не подтверждаю. Обратно Acknowledgment.
SYN, 16 — Synchronization. Этот символ передавался, когда для синхронизации было необходимо что-нибудь передать.
ETB, 17 — End of Text Block, конец текстового блока. Иногда текст по техническим причинам разбивался на блоки.
CAN, 18 — Cancel, отмена (того, что было передано ранее).
EM, 19 — End of Medium, конец носителя (кончилась перфолента и т. д.)
SUB, 1A — Substitute, подставить. Ставится на месте символа, значение которого было потеряно или испорчено при передаче. Сейчас Ctrl-Z используется как конец файла при вводе с клавиатуры в системах DOS и Windows. У этой функции нет никакой очевидной связи с символом SUB.
ESC, 1B — Escape. Следующие за ним символы имеют какое-то другое значение, отличное от того, которое определено в ASCII. Обычно начинал управляющие последовательности.
FS, 1C — File Separator, разделитель файлов.
GS, 1D — Group Separator, разделитель групп.
RS, 1E — Record Separator, разделитель записей.
US, 1F — Unit Separator, разделитель юнитов. То есть поддерживалось 4 уровня структуризации данных: сообщение могло состоять из файлов, файлы из групп, группы из записей, записи из юнитов.
DEL, 7F — Delete, стереть последний символ. Символом DEL, состоящим в двоичном коде из всех единиц, можно было забить любой символ. Устройства и программы игнорировали DEL так же, как NUL. Код этого символа происходит из первых текстовых процессоров с памятью на перфоленте: в них удаление символа происходило забиванием его кода дырочками (обозначавшими логические единицы).
Растровая и векторная графика
Способы представления изображений в памяти ЭВМ
Формальное определение компьютерная (машинная) графика – это создание, хранение и обработка моделей объектов и их изображений с помощью ЭВМ. Под интерактивной компьютерной графикой понимают раздел компьютерной графики, изучающий вопросы динамического управления со стороны пользователя содержанием изображения, его формой, размерами и цветом на экране с помощью интерактивных устройств взаимодействия.
Под компьютерной геометрией понимают математический аппарат, применяемый в компьютерной графике.
Необходимо отметить следующую отличительную черту компьютерных изображений. Изображения, которые мы встречаем в нашей повседневной жизни, реальные картины природы, можно бесконечно детализировать, выявлять все новые цвета и оттенки. Изображения, хранящиеся в памяти компьютера, независимо от способа их получения и представления, всегда являются усеченной моделью картины реального мира. Их детализация возможна лишь с той степенью, которая была заложена при их создании или получении, и их цветовая гамма будет не шире заранее оговоренной.
Одно и то же изображение может быть представлено в памяти ЭВМ двумя принципиально различными способами и получено два различных типа изображения: растровое и векторное. Рассмотрим подробнее эти способы представления изображений, выделим их основные параметры и определим их достоинства и недостатки.
Что такое растровое изображение?
Возьмём фотографию (например, см. рис. 1.1). Конечно, она тоже состоит из маленьких элементов, но будем считать, что отдельные элементы мы рассмотреть не можем. Она представляется для нас, как реальная картина природы.
Теперь разобьём это изображение на маленькие квадратики (маленькие, но всё-таки чётко различимые), и каждый квадратик закрасим цветом, преобладающим в нём (на самом деле программы при оцифровке генерируют некий «средний» цвет, т. е. если у нас была одна чёрная точка и одна белая, то квадратик будет иметь серый цвет).
Как мы видим, изображение стало состоять из конечного числа квадратиков определённого цвета. Эти квадратики называют pixel (от PICture ELement) – пиксел или пиксель.
Рис. 1.1. Исходное изображение
Теперь каким-либо методом занумеруем цвета. Конкретная реализация этих методов нас пока не интересует. Для нас сейчас важно то, что каждый пиксель на рисунке стал иметь определённый цвет, обозначенный цифрой (рис. 1.2).
Рис. 1.2. Фрагмент оцифрованного изображения и номера цветов
Теперь пойдём по порядку (слева направо и сверху вниз) и будем в строчку выписывать номера цветов встречающихся пикселей. Получится строка примерно следующего вида:
1 2 8 3 212 45 67 45 127 4 78 225 34 .
Вот эта строка и есть наши оцифрованные данные. Теперь мы можем сжать их (так как несжатые графические данные обычно имеют достаточно большой размер) и сохранить в файл.
Итак, под растровым (bitmap, raster) понимают способ представления изображения в виде совокупности отдельных точек (пикселей) различных цветов или оттенков. Это наиболее простой способ представления изображения, ибо таким образом видит наш глаз.
Достоинством такого способа является возможность получения фотореалистичного изображения высокого качества в различном цветовом диапазоне. Недостатком – высокая точность и широкий цветовой диапазон требуют увеличения объема файла для хранения изображения и оперативной памяти для его обработки.
Для векторной графики характерно разбиение изображения на ряд графических примитивов – точки, прямые, ломаные, дуги, полигоны. Таким образом, появляется возможность хранить не все точки изображения, а координаты узлов примитивов и их свойства (цвет, связь с другими узлами и т. д.).
Вернемся к изображению на рис. 1.1. Взглянем на него по-другому. На изображении легко можно выделить множество простых объектов — отрезки прямых, ломанные, эллипс, замкнутые кривые. Представим себе, что пространство рисунка существует в некоторой координатной системе. Тогда можно описать это изображение, как совокупность простых объектов, вышеперечисленных типов, координаты узлов которых заданы вектором относительно точки начала координат (рис. 1.3).
Рис. 1.3. Векторное изображение и узлы его примитивов
Проще говоря, чтобы компьютер нарисовал прямую, нужны координаты двух точек, которые связываются по кратчайшей прямой. Для дуги задается радиус и т. д. Таким образом, векторная иллюстрация – это набор геометрических примитивов.
Важной деталью является то, что объекты задаются независимо друг от друга и, следовательно, могут перекрываться между собой.
При использовании векторного представления изображение хранится в памяти как база данных описаний примитивов. Основные графические примитивы, используемые в векторных графических редакторах: точка, прямая, кривая Безье, эллипс (окружность), полигон (прямоугольник). Примитив строится вокруг его узлов (nodes). Координаты узлов задаются относительно координатной системы макета.
А изображение будет представлять из себя массив описаний – нечто типа:
Каждому узлу приписывается группа параметров, в зависимости от типа примитива, которые задают его геометрию относительно узла. Например, окружность задается одним узлом и одним параметром – радиусом. Такой набор параметров, которые играют роль коэффициентов и других величин в уравнениях и аналитических соотношениях объекта данного типа, называют аналитической моделью примитива. Отрисовать примитив – значит построить его геометрическую форму по его параметрам согласно его аналитической модели.
Векторное изображение может быть легко масштабировано без потери деталей, так как это требует пересчета сравнительно небольшого числа координат узлов. Другой термин – «object-oriented graphics».
Самой простой аналогией векторного изображения может служить аппликация. Все изображение состоит из отдельных кусочков различной формы и цвета (даже части растра), «склеенных» между собой. Понятно, что таким образом трудно получить фотореалистичное изображение, так как на нем сложно выделить конечное число примитивов, однако существенными достоинствами векторного способа представления изображения, по сравнению с растровым, являются:
· векторное изображение может быть легко масштабировано без потери качества, так как это требует пересчета сравнительно небольшого числа координат узлов;
· графические файлы, в которых хранятся векторные изображения, имеют существенно меньший, по сравнению с растровыми, объем (порядка нескольких килобайт).
Сферы применения векторной графики очень широки. В полиграфике – от создания красочных иллюстраций до работы со шрифтами. Все, что мы называем машинной графикой, 3D-графикой, графическими средствами компьютерного моделирования и САПР – все это сферы приоритета векторной графики, ибо эти ветви дерева компьютерных наук рассматривают изображение исключительно с позиции его математического представления.
Как видно, векторным можно назвать только способ описания изображения, а само изображение для нашего глаза всегда растровое. Таким образом, задачами векторного графического редактора являются растровая прорисовка графических примитивов и предоставление пользователю сервиса по изменению параметров этих примитивов. Все изображение представляет собой базу данных примитивов и параметров макета (размеры холста, единицы измерения и т. д.). Отрисовать изображение – значит выполнить последовательно процедуры прорисовки всех его деталей.
Для уяснения разницы между растровой и векторной графикой приведем простой пример. Вы решили отсканировать Вашу фотографию размером 10´15 см чтобы затем обработать и распечатать на цветном принтере. Для получения приемлемого качества печати необходимо разрешение не менее 300 dpi. Считаем:
10 см = 3,9 дюйма; 15 см = 5,9 дюймов.
По вертикали: 3,9 * 300 = 1170 точек.
По горизонтали: 5,9 * 300 = 1770 точек.
Итак, число пикселей растровой матрицы 1170 * 1770 = 2 070 900.
Теперь решим, сколько цветов мы хотим использовать. Для черно-белого изображения используют обычно 256 градаций серого цвета для каждого пикселя, или 1 байт. Получаем, что для хранения нашего изображения надо 2 070 900 байт или 1,97 Мб.
Для получения качественного цветного изображения надо не менее 256 оттенков для каждого базового цвета. В модели RGB соответственно их 3: красный, зеленый и синий. Получаем общее количество байт – 3 на каждый пиксел. Соответственно, размер хранимого изображения возрастает в три раза и составляет 5,92 Мб.
Для создания макета для полиграфии фотографии сканируют с разрешением 600 dpi, следовательно, размер файла вырастает еще вчетверо.
С другой стороны, если изображение состоит из простых объектов, то для его хранения в векторном виде необходимо не более нескольких килобайт.