Информатика. Лекция 3

User Rating: 5 / 5

Star ActiveStar ActiveStar ActiveStar ActiveStar Active
 

 

Лекция 3

§ 10. Основные теоретические положения информатики. Информация и

информационные процессы как основные понятия теории информации

§ 11. Измерение количества информации. Объемный метод

§ 12. Количество информации. Энтропийный подход

ЛЕКЦИЯ 3

§ 10. ОСНОВНЫЕ ТЕОРЕТИЧЕСКИЕ ПОЛОЖЕНИЯ ИНФОРМАТИКИ.

ИНФОРМАЦИЯ И ИНФОРМАЦИОННЫЕ ПРОЦЕССЫ КАК ОСНОВНЫЕ ПОНЯТИЯ ТЕОРИИ ИНФОРМАЦИИ

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

Некоторое несоответствие определяется следующим положением.

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

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

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

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

Ученые, занимающиеся исследованиями в теории информации, решили, что обычное (всеми принятое) значение слова «информация» слишком расплывчато, и дали ему такое значение: «мера определенности в сообщении». Содержание данного определения будет подробно раскрыто в следующих параграфах.

Таким образом, теорию информации вызвали к жизни потребности практики, ведь любое автоматическое устройство перерабатывает информацию: поезд, нажимая на определённый участок рельса, передаёт сигнал, включающий красный свет светофора; приборы автоматической телефонной станции (АТС) преобразуют номер телефона, набираемый нами, в соединение с нужным абонентом. Вершиной технических достижений в области работы с информацией является компьютер.

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

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

Любой процесс передачи информации можно представить несложной схемой, как на рис.6.

Рис.6. Схема процесса передачи информации

Каждая из трёх частей в приведённой схеме имеет определённые свойства (как принято говорить — параметры). От этих свойств зависит качество передачи.

Что это за свойства, объясняет пример, ставший классическим. Когда вы пишете записку и отдаёте её в руки адресату, то вы играете роль и передатчика, и канала связи. Вид информации при передаче в данном случае не меняется; написанный текст в том же виде передаётся и принимается в нужное время и без искажений. Если же вы посылаете записку через знакомого, то канал связи становится самостоятельной частью схемы, и в нём могут произойти не зависящие от вас события. Например, записка потеряется или попадет под дождь. В таких обстоятельствах говорят: в канале связи возникли помехи. Или передача задержится, если знакомый не сразу найдёт адресата. Значит, увеличится время передачи. Или знакомый записку прочитает и сообщит адресату её содержание на словах. В результате изменится (преобразуется) вид информации — из письменной она превратится в устную. При этом не исключено, что содержание информации исказится — «канал связи» скажет либо не всё, либо не то. И, наконец, вас, вероятно, огорчит, что записку прочитал не только ваш адресат, т. е. произошёл несанкционированный (не разрешенный передатчиком) доступ к информации.

Из этого примера видно, какие параметры может иметь процесс передачи информации и какие проблемы, связанные с ними, приходится решать. Нас интересуют надёжность и время передачи, преобразования и защита информации. Сами части схемы передачи могут быть очень сложны. Например, канал телефонной связи — это не только провода, но и устройства на АТС, соединяющие абонентов; приборы, усиливающие сигнал при передаче на дальние расстояния, и т. д.

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

Считается, что теория информации как самостоятельная научная дисциплина, связанная с восприятием, передачей, переработкой, хранением и использованием информации, была основана американским ученым К. Шенноном в конце 40-х годов XX века.

Предложенная Шенноном теория основывалась на фундаментальном понятии количественной меры неопределенности - энтропии - и связанном с нею понятия количества информации. Другим фактором в становлении теории информации стало осознание того, что носитель информации - сигнал - имеет случайную природу.

§ 11. ИЗМЕРЕНИЕ КОЛИЧЕСТВА ИНФОРМАЦИИ.

ОБЪЕМНЫЙ МЕТОД

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

В технике часто используют довольно простой, но грубый способ измерения информации, который можно назвать объемным. Именно с этим способом вы встречались до настоящего времени. Он основан на подсчете числа символов в сообщении, т. е. связан с его длиной и не учитывает содержания. Правда, длина сообщения зависит от мощности алфавита - числа различных символов, употребляемых для записи сообщения. Например, одно и то же число «девятнадцать» в десятичном алфавите записывается двумя символами - 19, а в двоичном алфавите - пятью символами - 10111.

В десятичной системе мощность алфавита равна 10 (десять цифр), а в двоичной — 2. Чем больше мощность алфавита, тем короче запись. Самый бедный алфавит — двоичный: он состоит из двух символов, неважно каких. И у большого, и у маленького алфавита есть свои плюсы и минусы. Достоинства большого алфавита — короткие записи, но он требует более сложных устройств для кодирования. Чем больше разных символов, тем сложнее их различать, а значит, и труднее передавать без искажений.

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

В вычислительной технике применяются две стандартные единицы измерения: бит и байт. Бит - это один символ двоичного алфавита. (Слово «бит» получилось в результате сокращения английского выражения binary digit — «двоичная цифра»). Байт - это один символ, который можно представить восьмиразрядным двоичным кодом. Мощность алфавита этого представления равна числу различных восьмиразрядных двоичных кодов, т. е. 2 8 = 256, и может включать, например, все символы клавиатуры пишущей машинки или терминала ЭВМ.

У специалистов из области вычислительной техники по этому поводу есть даже шутливая поговорка «За один байт восемь битов дают».

Для сообщения, записанного в двоичной системе, количество информации в нём — просто число двоичных символов. Число 25, выраженное в двоичной системе как 11001, содержит 5 символов и, следовательно, 5 битов информации. Правда, в той же системе его можно записать и по-другому; 0011001. Такое сообщение будет содержать 7 битов информации.

Одним битом можно передать только одно из двух сообщений — 0 или 1. Эти короткие сообщения порой несут большую смысловую нагрузку: могут означать ответ «да» или «нет», сигнал включения или отключения электроэнергии. Но для передачи они предельно просты. Двух битов достаточно для передачи четырёх различных сообщений: 00, 01, 10, 11. Согласно правилам комбинаторики, записью из n двоичных символов можно передать одно из 2n сообщений.

Общее количество символов, используемых в обычных текстах, больше чем 27 = 128, но меньше чем 28 = 256. (На клавиатуре компьютера можно насчитать около 150 знаков.) Поэтому одного байта как раз достаточно, чтобы закодировать в двоичной системе любой символ обычного текста. Для сложных  математических символов (квадратного корня, интеграла и др.), букв различных шрифтов и алфавитов (например, греческого) одного байта недостаточно.

А как измерить количество информации в сообщении, если оно записано не в двоичной системе? И зачем измерять такое сообщение в битах и байтах? Это нужно для того, чтобы знать, сколько символов будет в сообщении, если его закодировать с помощью двоичного алфавита. Конечно, и в двоичной системе, как мы видели, одно и то же число можно закодировать по-разному. Однако для каждого сообщения существует минимальное количество битов. Как его определить?

Рассмотрим запись десятичных чисел в двоичной системе. Первые 2n чисел – от 0 до 2n - 1 – можно записать n битами. Например,  для записи   чисел от 0 до 7 хватит трёх битов (22 < 7 < 23), от 0 до 31 — пяти и т. д. Если N — степень числа 2 (N = 2n), то для его записи нужно n + 1 бит. Так, 32 = 2n соответствует 100 000 в двоичной системе  (6 битов). Для других чисел количество битов равно показателю наибольшей степени двойки, не превышающей этого числа, плюс 1. Например, для числа 57 эта степень равна 5: 57 больше 32, но меньше 64. Поэтому для записи 57 нужно не меньше 5 + 1 = 6 битов. Чтобы найти максимальную степень числа 2 для любого N, необходимо вычислить log2N и взять от него целую часть;  ее обозначают квадратными скобками: [log2N]. Итак, минимальное число битов для записи любого десятичного числа N равно [log2N] + 1.

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

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

кило- 210 = 1024,

мera- 220 = 10242 = 1 048 576,

гига- 230 = 10243 = 1 073 741 824.

Рассмотренный в данном параграфе метод измерения количества информации достаточно прост, но полностью игнорирует человеческую оценку информации. Например, последовательному ряду из 100 букв приписывается определенное значение количества информации.  При этом не обращается внимания на вопрос, имеет ли эта информация смысл, и имеет ли, в свою очередь, смысл ее практическое применение.

В соответствии с объемным методом совокупность 100 букв — фраза из 100 букв из газеты, пьесы Шекспира или теоремы Эйнштейна — имеет в точности одинаковое количество информации». Такой подход к измерению количества информации соответствует техническим задачам, в которых канал связи должен передать всю информацию вне зависимости от ценности этой информации для адресата. Передающей системе важно одно: передать нужное количество информации за определенное количество времени.

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

§ 12. КОЛИЧЕСТВО ИНФОРМАЦИИ.

ЭНТРОПИЙНЫЙ ПОДХОД

В повседневной жизни мы, как правило, оцениваем полученные сведения со смысловой стороны: новые сведения воспринимаем не как определенное количество информации, а как новое содержание. Есть ли информация в сообщении «на Земле существует растительность»? Конечно, нет. Ведь здесь нет никакого нового содержания. А вот фраза «на Марсе есть растительность» содержит информацию, потому что она отражает вероятность знания, возможность явления, а не утверждает всем известное.

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

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

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

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

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

Если вам, допустим, кто-то позвонит по телефону и скажет: «Днем бывает светло, а ночью темно», то такое сообщение вас удивит лишь нелепостью высказывания очевидного и всем известного, а не новостью, которую оно содержит.

Иное дело, например, результат финала в шахматном турнире. Кто выиграет: Карпов или Каспаров? Или партия закончится вничью? Исход здесь трудно предсказать.

И чем больше интересующее нас событие имеет случайных исходов, тем ценнее сообщение о его результате, тем больше информации.

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

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

Мы уже знаем, что количество информации зависит от вероятностей тех или иных исходов события. Если событие имеет два равновероятных исхода, это означает, что вероятность каждого исхода равна 1/2. Такова вероятность выпадения «орла» или «решки» при бросании монеты. Если событие имеет три равновероятных исхода, как в нашем примере с шахматным турниром, то вероятность каждого равна 1/3. Сумма вероятностей всех исходов всегда равна единице: ведь какой-нибудь из всех возможных исходов обязательно наступит. Событие может иметь и неравновероятные исходы. Так, при футбольном матче между сильной и слабой командами  вероятность победы сильной команды велика – например, 4/5. Вероятность ничьей намного меньше, например 3/20. Вероятность же поражения совсем мала.

Рассмотрим классический пример с колодой карт, содержащей 32 различные карты. Чтобы выбрать одну из карт, существует 32 возможности, которые характеризуют исходную неопределенность ситуации. Если при равной вероятности уже выбрана какая-то из них (например, король червей), то неопределенности нет. Таким образом, число 32 в рассматриваемом примере можно было бы считать количеством информации, заложенным в одном   выборе из  32 возможностей.  Р. Хартли предложил в качестве меры неопределенности логарифм от числа возможностей:

H = k log a m. (1)

Здесь H - количество информации, k - коэффициент пропорциональности, m - число возможных выборов, а - основание логарифма. Чаще всего принимают k=1 и a=2. Тогда стандартной единицей количества информации будет выбор из двух возможностей. Такая единица, как вы уже знаете, носит наименование бита и представляется одним символом двоичного алфавита.

Бит выбран в качестве единицы количества информации потому, что принято считать, что двумя двоичными словами исходной длины m или словом длины 2m можно передать в два раза больше информации, чем одним исходным словом. Число выборов при этом увеличивается в 2m раз, тогда как значение H в соотношении (1) просто удваивается. Интересно, что в соотношении (1) Н характеризует число вопросов (двоичных), ответы на которые позволяют выбрать одну из альтернатив. Так, в примере с колодой карт из 32 карт необходимо и достаточно получить ответы «да» и «нет» на пять вопросов (25 = 32). Ответ на каждый вопрос вдвое сокращает область дальнейшего выбора. Пусть, например, необходимо выбрать даму пик. Такими вопросами будут:

1. Карта красной масти?                             Ответ: «нет».

2. Трефы?                                                     Ответ: «нет».

3. Одна из четырех старших?                     Ответ: «да».

4. Одна из двух старших?                           Ответ: «нет».

5. Дама?                                                        Ответ: «да».

Таким образом, выбрана дама пик. Этот выбор можно описать последовательностью из пяти двоичных символов 00101, в которой 0 соответствует «нет», а 1 соответствует «да».

В данном примере предполагалось, что выборы равновероятны и число их конечно. К. Шеннону принадлежит обобщение H на случай, когда H зависит не только от m, но и от вероятностей выбора символов и вероятностей связей между ними.

Соотношение это выглядит следующим образом:

где Рi - вероятность выбора i-го символа алфавита. Удобнее в качестве меры количества информации пользоваться не значением hi, а средним значением количества информации, приходящейся на один символ алфавита:

Значение H достигает максимума при равенстве всех Рi, т. е. при Рi=1/m. В этом случае последнее соотношение превращается в формулу Р. Хартли (1):

H max = - log P = log m.

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

I(C) = – H(C). (4)

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

Подведём итог. Информацию можно измерять длиной сообщения в битах. Такой способ ничего не говорит об информативности сообщения, но зато характеризует объём работы системы связи при передаче. Если же в задаче необходимо учитывать информативность, то следует пользоваться энтропийным подходом к измерению информации. При этом нужно уточнить, о каком множестве событий будет сообщаться, каковы их вероятности, после чего вычислить I(C).