Лабораторная работа Количественная оценка информации 1 Цель работы
 Скачать 0.56 Mb.
|
Лабораторная работа № 3. Количественная оценка информации 1 Цель работы − Освоение навыков определения количества информации; − Определение энтропии непрерывных сообщений. 2 Теоретические сведения Важной задачей теории информации является количественная оценка передаваемых сообщений, которая называется количеством информации. Количество информации не отображает качественное содержание сообщения, а определяет меру его неопределенности. Если алфавит некоторого источника сообщений состоит из m знаков, каждый из которых может служить элементом сообщения, то количество N возможных сообщений длины n равно числу перестановок с неограниченными повторениями: N = m n (2.1) В том случае, если все N сообщений от источника будут равновероятными, получение определенного сообщения равносильно для него случайному выбору одного из N сообщений с вероятностью Р = 1/N. Чем больше N, тем большая степень неопределенности характеризует этот выбор и тем более информативным можно считать сообщение. Поэтому число N может служить мерой информации. С точки зрения теории информации, мера информации должна быть пропорциональна длине сообщения. В качестве меры неопределенности выбора 3 Все знаки алфавита составляют полную систему случайных событий, поэтому: Формулы Шеннона для количества информации и энтропии: Свойства энтропии. 1) Энтропия Н - величина вещественная, неотрицательная и ограниченная, т.е. Н ≥ 0. 2) Энтропия равна нулю, если вероятность одного из элементов множества равно единице. 3) Энтропия максимальна, если все знаки алфавита равновероятны, т.е. Нmax = log m. (2.7) Избыточностью называется где - это случайная величина, N- число сообщений. Пример1. Вычислить количество информации, содержащееся в телевизионном сигнале, соответствующем одному кадру развертки. В кадре 625 строк, а сигнал, соответствующий одной строке, представляет собой последовательность из 600 случайных по амплитуде импульсов, причем амплитуда импульса может принять любое из 8 значений с шагом в 1 В. Решение. В рассматриваемом случае длина сообщения, соответствующая одной строке, равна числу случайных по амплитуде импульсов в ней: n = 600. Количество элементов сообщения (знаков) в одной строке равно числу значений, которое может принять амплитуда импульсов в строке m = 8. Количество информации в одной строке I = n log 8, а количество информации в кадре Iк =625*I = 625*600*log 8= 1,125*10 6 бит. Пример 2. Даны 27монет равного достоинства, среди которых есть одна фальшивая с меньшим весом. Вычислить сколько раз надо произвести взвешивание на равноплечих весах, чтобы найти фальшивую монету. Решение. Так как монеты внешне одинаковы, они представляют собой источник с равновероятными состояниями, а общая неопределенность ансамбля, характеризующая его энтропию H1 = log 2 27. Одно взвешивание способно прояснить неопределенность ансамбля насчитывающего три возможных исхода (левая чаша весов легче, правая чаша весов легче, весы находятся в равновесии). Все исходы являются равновероятными (нельзя заранее отдать предпочтение одному из них), поэтому результат одного взвешивания представляет источник с равновероятными состояниями, а его энтропия H2 = log 2 3 бит. Так как энтропия отвечает требованию аддитивности и при этом H1 = 3*H2 = 3* log 2 3, то для определения фальшивой монеты достаточно произвести три взвешивания. Алгоритм определения фальшивой монеты следующий. При первом взвешивании на каждую чашку весов кладется по девять монет. 5 Фальшивая монета будет либо среди тех девяти монет, которые оказались легче, либо среди тех, которые не взвешивались, если имело место равновесие. Аналогично, после второго взвешивания число монет, среди которых находится фальшивая монета, сократится до трех. Последнее, третье, взвешивание дает возможность точно указать фальшивую монету. Контрольные вопросы Дать определение понятия «количество информации», привести формулу и пояснить все составляющие этой формулы. 1 В чем отличие формулы количества информации для равновероятных событий и разновероятных? Пояснить на примере, привести формулы. 2 Дать определение энтропии. Записать и пояснить формулу Шеннона. 3 Перечислить и доказать основные свойства энтропии. 4 Записать и пояснить формулу Хартли. 5 Что является единицей измерения количества информации, энтропии? Назвать и пояснить все единицы измерения количества информации. 6 Приведите примеры, в которых энтропия сообщения равна нулю, принимает максимальное значение? 7 Дать определение и пояснить правило сложения энтропий для независимых источников? 8 Пояснить как определяется количество информации непрерывных сообщений. 9 Записать и пояснить формулу избыточности кода. УДК 004(076.5) Измерение информации : методические указания к выполнению практической работы по информатике для студентов всех направленийдневной формы обучения / сост. Н. Д. Берман, Н. И. Шадрина. – Хабаровск : Изд-во Тихоокеан. гос. ун-та, 2013. – 27 с. Методические указания составлены на кафедре информатики. Включают общие сведения об информации, свойствах информации, представлении информации в компьютере, примеры решения задач и задания для самостоятельного выполнения. Печатается в соответствии с решениями кафедры информатики и методического совета факультета компьютерных и фундаментальных наук. 7 © Тихоокеанский государственный университет, 2013 Понятие информации Термин «информация» происходит от латинского information, что означает разъяснение, осведомление, изложение. С позиции материалистической философии информация есть отражение реального мира с помощью сведений (сообщений). В широком смысле информация – это общенаучное понятие, включающее в себя обмен сведениями между людьми, обмен сигналами между живой и неживой природой, людьми и устройствами. Информация – сведения об объектах и явлениях окружающей среды, их параметрах, свойствах и состоянии, которые уменьшают имеющуюся о них степень неопределенности, неполноты знаний. Информация, предназначенная для передачи, называется сообщением. Сообщение может быть представлено в виде знаков и символов, преобразовано и закодировано с помощью электрических сигналов. Информация, представленная в виде, пригодном для обработки (человеком, компьютером), называется данными. Данные могут быть, например, числовыми, текстовыми, графическими. Чтобы происходил обмен информацией, должны быть источник информации, передатчик, канал связи, приемник и получатель. Обычно в качестве получателя выступает человек, который оценивает информацию с точки зрения ее применимости для решения поставленной задачи. Процедура оценки информации проходит в три этапа, определяющие ее синтаксический, семантический и прагматический аспекты. Определенный набор данных вне зависимости от смысловых и потребительских качеств характеризует синтаксический аспект информации. Сопоставление данных с тезаурусом (тезаурус – полный систематизированный набор данных и знаний в какой-либо области) формирует знание о наблюдаемом факте, это является семантическим аспектом информации (отражает смысловое содержание информации). Оценка практической полезности информации отражает ее прагматический аспект. 9 Свойства информации Информация характеризуется определенными свойствами, зависящими как от данных (содержательной части информации), так и от методов работы с ними. Свойства информации делятся на две группы: атрибутивные и потребительские. Атрибутивные свойства - это свойства, которые отображают внутреннюю природу информации и особенности ее использования. Наиболее важными из этих свойств являются следующие: • информация представляет новые сведения об окружающем мире, отсутствовавшие до ее получения; • информация не материальна, несмотря на то, что она проявляется в форме знаков и сигналов на материальных носителях; • знаки и сигналы могут предоставить информацию только для получателя, способного их воспринять и распознать; • информация неотрывна от физического носителя, но в то же время не связана ни с конкретным носителем, ни с конкретным языком; • информация дискретна – она состоит из отдельных фактических данных, передающихся в виде сообщений; • информация непрерывна – она накапливается и развивается поступательно. Качество информации определяется ее свойствами, отвечающими потребностям пользователя. Рассмотрим наиболее важные потребительские свойства информации: • полнота (достаточность); • достоверность; • адекватность; • доступность; • актуальность. 10 Полнота (достаточность) информации. Под полнотой информации понимают ее достаточность для принятия решений. Достоверность информации. Под достоверностью информации понимают ее соответствие объективной реальности окружающего мира. Свойство достоверности информации имеет важное значение в тех случаях, когда ее используют для принятия решений. Адекватность информации – это степень соответствия информации, полученной потребителем, тому, что автор вложил в ее содержание. Адекватность информации иногда путают с ее достоверностью. Это разные свойства. Можно привести пример адекватной, но недостоверной информации. Так, если 1 апреля в газете появится заведомо ложное сообщение, то его можно считать адекватным. Адекватно толковать его не как информационное, а как развлекательное. То же сообщение, опубликованное 2 апреля, будет и недостоверным, и неадекватным. Доступность информации – это мера возможности получить ту или иную информацию. Актуальность информации – это степень соответствия информации текущему моменту времени. Нередко с актуальностью, как и с полнотой, связывают коммерческую ценность информации. Поскольку информационные процессы растянуты во времени, то достоверная и адекватная, но устаревшая информация может приводить к ошибочным решениям. Единицы измерения количества информации За единицу количества информации принимается такое ее количество, которое содержит сообщение, уменьшающее неопределенность в два раза. Единица измерения информации называется бит (bit) – сокращение от английских слов binarydigit, что означает «двоичная цифра». Если положить в мешок два шара разного цвета, то, вытащив вслепую один шар, получим информацию о цвете шара в 1 бит. 11 В компьютерной технике бит соответствует физическому состоянию носителя информации: намагничено – не намагничено, есть сигнал – нет сигнала. При этом одно состояние принято обозначать цифрой 1, а другое - цифрой 0. В информатике часто используется величина, называемая байтом (byte) и равная 8 битам. И если бит позволяет выбрать один вариант из двух возможных, то байт, соответственно, 1 из 256 (2 8 ). Наряду с байтами для измерения количества информации используются более крупные единицы: 1 Килобайт (Кбайт) = 1024 байт = 2 10 байт =2 13 бит; 1 Мегабайт (Мбайт) = 1024 Кбайт = 2 10 Кбайт = 2 20 байт = 2 23 бит; 1 Гигабайт (Гбайт) =1024 Мбайт = 2 10 Мбайт = 2 30 байт = 2 33 бит; 1 Терабайт (Тбайт) = 1024 Гбайт = 2 10 Гбайт = 2 40 байт = 2 43 бит; 1 Петабайт (Пбайт) = 1024 Тбайт = 2 10 Тбайт = 2 50 байт = 2 53 бит; 1 Эксабайт (Эбайт) = 1024 Пбайт = 2 10 Пбайт = 2 60 байт = 2 63 бит. Представление информации в компьютере Любой компьютер предназначен для обработки, хранения, преобразования данных. Для выполнения этих функций компьютер должен обладать некоторыми свойствами представления этих данных. Представление этих данных заключается в их преобразовании в вид, удобный для последующей обработки либо пользователем, либо компьютером. В зависимости от этого данные имеют внешнее и внутреннее представление. Во внешнем представлении (для пользователя) все данные хранятся в виде файлов. Простейшими способами внешнего представления данных являются: • числовые данные (вещественные и целые); • текст (последовательность символов); • изображение (графика, фотографии, рисунки, схемы); звук. 12 Внутреннее представление данных определяется физическими принципами, по которым происходит обмен сигналами между аппаратными средствами компьютера, принципами организации памяти, логикой работы компьютера. Для автоматизации работы с данными, относящимися к различным типам, важно унифицировать их форму представления. Для этого обычно используется прием кодирования, т. е. выражение данных одного типа через данные другого типа. Любые данные для обработки компьютером представляются последовательностью двух целых чисел – единицы и нуля. Такая форма представления данных получила название двоичного кодирования. Кодирование числовых данных Числовая информация в памяти компьютера хранится и обрабатывается в двоичном коде. Применяется две формы кодирования двоичных чисел: с фиксированной и плавающей запятой. В форме с фиксированной запятой хранятся и обрабатываются целые числа. В ячейках памяти из n разрядов можно закодировать (записать) целые числа от Х = 0 до X = 2 n – 1. Например, с помощью 8 бит можно закодировать целые числа от 0 до 255. В форме с плавающей запятой хранятся и обрабатываются вещественные числа. При этом предполагается запись вещественного числа в экспоненциальном виде: Х = ± m · q p , где m – мантисса числа (|M| < 1); q – основание системы счисления; р – порядок числа (р – целое число). 13 Кодирование логических данных Логические данные принимают два значения: «Истина» или «Ложь» (1 или 0). В компьютере для логического значения отводится 2 байта, или 16 разрядов (бит), которые заполняются единицами, если значение «Ложь», и нулями, если значение «Истина». Кодирование текстовых (символьных) данных Правило кодирования символьных данных (букв алфавита и других символов) заключается в том, что каждому символу ставится в соответствие двоичный код – совокупность нулей и единиц. Технически это выглядит просто, но существуют организационные сложности. В первые годы развития вычислительной техники эти сложности были связаны с отсутствием необходимых стандартов, а в настоящее время вызваны, наоборот, изобилием одновременно действующих и противоречивых стандартов. Для того чтобы весь мир одинаково кодировал текстовые данные, нужны единые таблицы кодирования. Наиболее распространенный стандарт кодировки символов ASСII-код (American Standard Code for Information Interchange – американский стандартный код для обмена информацией) был введен институтом стандартизации США в 1963 г. и после модификации в 1977 г. был принят в качестве всемирного стандарта. Каждому символу в этой таблице поставлено в соответствие двоичное число от 0 до 255 (8-битовый двоичный код), например, A – 01000001, B– 01000010, C – 01000011, D – 01000100 и т. д. В системе ASCII закреплены две таблицы кодирования – базовая и расширенная. Базовая таблица закрепляет значения кодов от 0 до 127, а расширенная относится к символам с номерами от 128 до 255. Первые 32 кода отданы производителям аппаратных средств. В этой области размещаются так называемые управляющие коды, которым не соответствуют никакие символы языков, и, соответственно, эти коды не выводятся ни на экран, ни на устройства 14 печати, но ими можно управлять, например, тем, как производится вывод прочих данных. Начиная с 32-го кода по 127-й размещены коды символов английского алфавита, знаков препинания, цифр, знаков арифметических действий, некоторые вспомогательные символы (число 127 представляет команду DELETE). Базовая таблица кодировки ASCII приведена в таблице. Число Символ Число Символ Число Символ Число Символ Число Символ Число Символ 32 пробел 48 0 64 @ 80 P 96 ` 112 p 33 ! 49 1 65 A 81 Q 97 a 113 q 34 “ 50 2 66 B 82 R 98 b 114 r 35 # 51 3 67 C 83 S 99 c 115 s 36 $ 52 4 68 D 84 T 100 d 116 t 37 % 53 5 69 E 85 U 101 e 117 u 38 & 54 6 70 F 86 V 102 f 118 v 39 ‘ 55 7 71 G 87 W 103 g 119 w 40 ( 56 8 72 H 88 X 104 h 120 x 41 ) 57 9 73 I 89 Y 105 i 121 y 42 * 58 : 74 J 90 Z 106 j 122 z 43 + 59 ; 75 K 91 [ 107 k 123 { 44 , 60 < 76 L 92 \ 108 l 124 | 45 - 61 = 77 M 93 ] 109 m 125 } 46 62 > 78 N 94 ^ 110 n 126 47 / 63 ? 79 O 95 _ 111 o 127 DEL Национальные системы кодирования занимают расширенную часть, определяющую значения кодов с 128 до 255. В России наиболее широкое применение нашли кодировки Windows 1251 (была введена компанией Microsoft), КОИ-8 (код обмена информацией восьмизначный), ISO (International Standard Organization – Международный институт стандартизации) – международная кодировка, в которой предусмотрено кодирование символов русского алфавита. Организационные трудности, связанные с созданием единой системы кодирования текстовых данных, вызваны ограниченным набором кодов (256). Если, например, кодировать символы не восьмиразрядными двоичными числами, а числами с большим количеством разрядов, то и диапазон возможных 15 значений кодов станет намного больше. Такая система, основанная на 16- разрядном кодировании символов, получила название универсальной UNICODE. Шестнадцать разрядов позволяют обеспечить уникальные коды для 65 536 (2 16 ) различных символов – этого поля достаточно для размещения в одной таблице символов большинства языков планеты. Несмотря на тривиальную очевидность такого подхода, простой механический переход на данную систему долгое время сдерживался из-за недостаточных ресурсов средств вычислительной техники (в системе кодирования UNICODE все текстовые документы автоматически становятся вдвое длиннее). Во второй половине 90-х г. технические средства достигли необходимого уровня обеспеченности ресурсами, и сегодня переход документов и программных средств на универсальную систему кодирования в основном осуществлен. |
I = log
2
N = log
2
m n
= n log
2
m
(2.2)
Эта логарифмическая функция характеризует количество информации.
Количество информации, приходящееся на один элемент сообщения (знак, букву), называется энтропией:
Вычислительные системы основаны на элементах, имеющих два устойчивых состояния «0» и «1», поэтому выбирают основание логарифма равным двум. При этом единицей измерения количества информации, приходящейся на один элемент сообщения, является двоичная единица - бит.
Двоичная единица (бит) является неопределенностью выбора из двух равновероятных событий.
Так как из log
2
m = 1 следует m = 2, то ясно, что 1 бит - это количество информации, которым характеризуется один двоичный элемент при равновероятных состояниях 0 и 1.
Представленная оценка количества информации базируется на предположении о том, что все знаки алфавита сообщения равновероятны. Для общего случая каждый из знаков появляется в сообщении с различной вероятностью. На основании статистического анализа известно, что в сообщении длины n знак xi появляется ni раз, т.е. вероятность появления знака: