Основы информатики_Савельев А.Я_Учебник_2001

I. БАЗОВЫЕ ПОНЯТИЯ ИНФОРМАТИКИ 1.1. Общие сведения об информации

Прежде всею определим, что такое вычислительная машина. ИнтуиrriBHo понято, чго это — средство для автоматизации вычислений. Однако вычисли1елы1ые машины используются настолько широко и для решения такою обширною круга задач (от вычислений до составления меню в реегорапе и даже сочинения музыки), что поневоле возникает сомнение в пра­ вильное in итуитив»юго определения.

В «Энциклопедии кибернетики» [20] приведено следующее опреде­

тесным образом связано с понятиями «информация» и «алгоритмическая обработка».

Объект передачи и преобразования в вычислительных системах (ма­ шинах) — информация. В этом смысле вычислительную машину (систе­ му) можно называть информационной, в отличие, например, от энергетиHccKoii системы, где объект передачи и преобразования — энергия. Все процессы, происходящие в вычислительной системе, связаны непосредсгвенно с различными физическими носителями информационных сооб1це1П!Й, и все узлы и блоки этой системы являются физической средой, в которой осуществляются информационные процессы. Специфика информациот!ых процессов состоит не только в передаче информационных сообщений посредством заданной физической среды, но и в преобразова­ нии, переработке и хранении информации. Все это составляет предмет науки информатики. Информатика представляет собой неразрывное единство трех составных частей: теории передачи и преобразования ин­ формации; алгоритмических средств обработки информации и вычисли­ тельных средств.

/ fiasodhte понятия информатики

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

—ввод информации или установка исходных данных;

—переработка или преобразование введенной информации;

—определение результатов и вывод переработанной информации. Вычислительная машина получает информацию, запоминает ее, обра-

ба1ывает по заданным алгоритмам и направляет потребителю (nojibioBaieлю) или в другие системы обработки (рис. 1.1).

Рис. 1.1. Схема взаимодействия пользователя с компыогером

Термин «информация» имеет много определений. В широком смысле

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

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

Информационные меры, как правило, рассматриваются в трех аспек­ тах: структурном, статистическом и семантическом.

В структурном аспекте рассматривается строение массивов информа­ ции и их измерение простым подсчетом информационных элементов нлп комбинаторным методом. Структурный подход применяется для оценки возможностей информационных систем вне зависимости от условий их применения.

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

/ 2 Структурная мера информации

Семян шческий подход позволяет выделить полезность или ценность И1|{})0рмаиионпого сообщения.

1.2. Струк1урпая мера информации

Информация всегда представляется в виде сообщения. Элемеигарная единица сообщений — символ. Символы, собранные в группы, — ашва. Сообщение, оформленное в виде слов или отдельных символов, всегда передао1ся в магериально-энергетической форме (электрический, световой, 1в\ковон cHiHajU'i и т. д.).

i'a3JHi4atoi информацию непрерывную и дискретную.

Рис. 1.2. Способы прелстав;(е1шя информации

Функция х{1), изображенная на рис. i.2, о, может быть представлена в нснрерьниюм (рис. 1.2,6) и дискретном (рис. i.2, в) видах. В непрерывном виде эта (|)ункция может принимать любые вещественные значения в дан­ ном диапазоне изменения аргумента /, т. е. множество значений непрерыв­ ное! функции бесконечно. В дискретном виде функция х(/) может прини­ май) BCifiecTBenHbie значения только при определенных значениях аргуменга. Какой бы малый интервал дискретности (т. е. расстояние между соседними значениями аргумента) не выбирался, множество значений дискрешон функции для заданного диапазона изменений аргумента (если он не бесконечный) будет конечно (ограничено).

/ Пазовые понятия информатики

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

Геометрическая мери предполагает измерение параметра [еомегричеCKOii модели информационного сообщения (длины, площади, объема и т. п) в дискретных единицах. Например, геометрической моделью информации может быть линия единичной длины (рис 1.3, а — одиоразряд1юе слово, приртмающее значение О или 1), квадрат (рис. 1.3, б — двухразрядное сло­ во) или куб (рис 1.3, в — трехразрядное слово). Максимально возможное количество информации в заданных структурах определяет информацнопнук) емкость модели (системы), которая определяется как сумма дискрег-

слов. Рассмотрим две пары слов 1001 IО и 001101, 011 101 и 111010. В них проведена перестановка крайних разрядов (изменено местоположение знакового разряда в числе — перене­ сен слева направо).

Аддитивная мера (мераХартли), в соответствии с которой количество информации измеряется в двоичных единицах — битах, — наиболее рас­ пространена. Вводятся понятия глубины q и длины и числа.

В гл. 3 понятие глубины числа будет трансформировано в понятие основания системы счисления. При заданных глубине и длине числа коли­ чество чисел, которое можно представить, N ~ q" . Величина Л^ не удобна

лиформ

Но количество информации в каждом исходе связано с его вероятностью /J, и выражается в двоичных единицах (битах) как Д - logi(l//',) = = - log, /J, , Тогда

Полученную величину называют энтропией и обозначаю! обычно бук­ вой Н. Энтропия обладает следующими свойствами:

1.Энтропия всегда неотрицательна, так как значения вероятностей вы­ ражаются величинами, не превосходящими единицу, а их логарифмы — отрицательными числами или нулем, так что члены суммы (1.6) — неотри­ цательны.

2.Энтропия равна нулю в том крайнем случае, ко1да одно из р, рав1Ю единице, а все остальные — нулю. Это тот случай, когда об опыте шш ве­ личине все известно заранее и результат не дает новую информацию.

3.Энтропия имеет наибольшее значение, когда все вероятности равны между собой: р, = р , =... = р^ = 1/i . При этом

/f = ^log2(l/i) = l o g j i .

4. Энтропия объекта АВ, состояния которого образуются совместной реализацией состояний А » В, равна сумме энтропии исходных объектов А и В, т. е. Н(_АВ) = Н(А) + Н(В).

Если все события равновероятны и статистически независимы, то оценки количества информации, по Хартли и Шеннону, совпадают. Это свидетельствует о полном использовании информационной емкосчи CHCie-

итическая мера информации

МЫ. В случае неравных вероятностей количество информации, по Шеннону, меньше iiFK|)opManHOHiioii емкости системы. Максимальное значение энтро­ пии достигается при р = 0,5, когда два состояния равновероятны. При ве­ рея I нос [ ях /J - О или р~\, что соответствует полной невозможности или nojEiiofi досшверности события, энтропия равна нулю.

Количество информации только тогда равно энтропии, когда неопре­ деленность ситуации снимается полностью. В общем случае нужно считать, что количество иттформации есть уменьшение энтропии вследствие опыта илтт какото-;тибо лругото акта познания. Если неопределенность снимается TTojTiTOCTbTo, ю ин(|)ормация равна энтропии: I = Н .

В атучае неполного разрешения имеет место частичная информация, явJтятoтнaяcя разттостыо между начальной и конечной энтропией: / = - '/, Я,

Наибо^тьтттее количество информации получается тогда, когда полностьто стнтмается неоттределенность, причем эта неопределенность была наибольтттсй - т!сроятости всех событий были одинаковы. Это соответствует максттмальтто возможттому количеству информации /' , оцениваемому мерой Харпттт:

/'=logjA' = log2(l/p) = - l o g j P ,

тде Л' —• число событий; р — вероятность их реализации в условиях равттотт вероятности событий.

I аким образом, /' = Я,,,.,.

ЛбcoJTloтlтaя избьтточность информации D^ представляет собой разттость между максимально возможным количеством информации и энтро-

ттией: D,5, = /' - Я , или D^ = Я „ „ - Н .

riojTbiyioTCfl также понятием относительной избыточности

V-(U„-H)/H„„. (1.7)

1.4. Семантическая мера информации

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

/ Вазовые понятия информатики

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

Содерлсательность события / выражается через функцию меры m{i) — содержательности его отрицания. Оценка содержательное!и осно­ вана на математической логике, в которой логические функции истинно­ сти m{i) и ложности m{i) имеют формальное сходство с функциями ве­ роятностей события p{i) и антисобытия q(i) в теории вероятностей.

Как и вероятность, содержательность события изменяется в пределах О < т{!) < 1.

Логическое количество информации /„^ , сходное со с!а1ис[ическим количеством информации, вычисляегся по выражениго:

I„f -:iog2[i/m(0J--log^ m{J).

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

Если информация используется в системах у[!равления, то ее полез­ ность целесообразно оценивать по тому эффекту, который она оказываег на результат управления.

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

Мера целесообразности в общем виде может быть аиалитически выра­ жена в виде соотношения

где Ро и р, — начальная (до (юлучения информации) и конечная (после получения информации) вероятности достижения цели.

1.5. Преобразование информации

Cjiejiyer рагпича1ь существенность самого события; существенносп времени совершения события или его наблюдения (рано—поздно— момент); существенность координаты совершения события.

Измерение некоторого параметра X можно характеризовать несколь кими функциями величины х: вероятностью р{х), погрешностью измере ПИЯ 8(л) и существенностью с{х). Каждой из этих функций можно поста BviTb в соответствие определенную меру информации. Мерой Хартл! оцемивается функция погрешности е при фиксированных значениях функ цнн вероягиости (р = const) и существенности (с - const). Мерой Шеннон оценивается функция вероятности {р = var) при фиксированных значения; функций погрешности (е = const) и существенности (с = const). Мера су щес!веиности относится к ситуации с фиксированными функциями пс f реипюстн (е - const) и вероятности {р = const). Можно ввести функци сущесгиеипосги: <\, зависящие от х\ с^ , с^ , зависящие от времени Т iipocipancfBa (канала) N.

1.5. Преобразование информации

Информационное сообщение всегда связано с источником информг НИИ, приемником информации и каналом передачи.

Дискретые сообщения состоят из конечного множества элементе! создаваемых источником последовательно во времени. Набор элементе (симво;юв) составляет алфавит источника.

Непрерывные сообщения задаются какой-либо физической величино! изменяющейся во времени. Получение конечного множества сообщений :: конечный промежуток времени достигается путем дискретизации (во вр( меии), квантования (по уровню) (см. рис 1.2).

В большинстве случаев информация о протекании того или иного ф| зического процесса вырабатывается соответствующими датчиками в ви/ сигналов, непрерывно изменяющихся во времени. Переход от аналоговог иредс1авления сигнала к цифровому дает в ряде случаев значительные npi имущества при передаче, хранении и обработке информации. Преобрмов! пие осуществляется с помощью специальных устройств — иреобразоват! лей непрерывных сигналов и может быть выполнено дискретизацией i времени и квантованием по уровню.

Рассмотрим разновидности сигналов, которые описываются фун1 цией x{t).

/Базовые понятия информатики

1.Непрерывная функция непрерывного аргумента. Значения, которые

x{t) определяются лишь на дискретном множестве значений ар1умеита /,, / - О ± i ± 2 , ... Величина х(/,) может принимать любое значение в интер­

.V|. ^Гз,...,.г^ и f|, ^2'•••''*'^^полняющие интервалы (jr,„„,, х,,,^^) и ( - 7 , 7 ) соответственно.

Первая из рассмотренных разновидностей прина/итежиг ненрерьмигым сигналам, вторая и третья — дискретно-непрерывным, а че|вер1ая дис­ кретным сигналам.

Операцию, переводящую информацию непрерывисто вида в И11(|и)рмацию дискретного вида, называют квантованием по времени, или дискрети­ зацией. Следовательно, дискретизация состоит в преобразовании сигнала х(1) непрерывного аргумента г в сигнал x(t^) дискретного apiyMCHiа /,.

Квантование по уровню состоит в преобразовании непрерывного мно­

купностью отдельных значений дг(Г|). По значениям функции дг(Г,) можно восстановить исходную функцию x{t) с некоторой гюгрешностью. Функ­ цию, полученную в результате восстановления (интерполяции) |Ю значени­ ям Jc((,), будем называть воспроизводящей и обозначать V{f).

При дискретизации сигналов приходится решать вопрос о том, как час­ то следует проводить отсчеты функции, т. е. каков должен бьггь шаг дис­ кретизации А/, - ^, - ^ _ j . При малых шагах дискретизации количество от-