Сообщение как материальная форма представления информации

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

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

Рис. 6.1. Различные формы представления числа 4

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

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

Формы сообщений (сигналы, изображения, знаки, языковые сообщения)

Можно выделить несколько основных форм сообщений (в порядке возрастания их сложности).

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

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

Рис. 6.2. График звуковых колебаний

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

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

Физические величины, изменения которых рассматриваются как сигналы или изображения, называются параметрами сигналов. Если параметры сигналов принимают конечное число значений, то такой сигнал называется дискретным.

Некоторые повторяющиеся образцы (фрагменты) сигналов (изменяющихся во времени или в пространстве) в процессе общественной практики человека обособляются, выделяются и трактуются как некоторые новые сущности, а не просто как произвольные фрагменты сигнала. Таким образом возникают фонемы (акустические сигналы) и графемы. Эти новые сущности являются элементами, на основе которых формируется речь и письмо. Число этих элементов конечно. Графемы и фонемы являются частными случаями более общего понятия - знака. Знаком можно считать любую сущность, отличную от других сущностей. Примерами знаков являются буквы различных естественных языков, всевозможные условные обозначения на картах, схемах и других документах, дорожные знаки и многое другое. Разнообразные примеры наборов знаков приведены в 27.

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

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

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

Следует отметить, что наряду с термином "информация" используется термин "данные" (иногда как синонимы). В[28]предлагается различать эти два термина и считать, что данные суть факты, идеи, сведения, которые представлены в знаковой (символьной) форме, позволяющей производить их передачу, обработку и интерпретацию (т.е. толкование, объяснение, раскрытие смысла), а информация - это смысл, который человек приписывает данным на основании известных ему правил представления в них фактов, идей, сообщений.

Полезно сделать еще одно замечание относительно терминов "знак" и "символ". Некоторые знаки приобретают определенное значение. К примеру, буквы свидетельствуют об алфавите, в который они входят, и о языке, который использует эти буквы. Но некоторые буквы (знаки) имеет для людей более глубокий смысл. Например, знак , помимо того, что он является буквой греческого алфавита, означает для людей, знакомых с математикой, отношение длины окружности к длине ее диаметра. Поэтому символом целесообразно называть знак, который имеет специальный смысл (значение), связанный с определенной областью человеческой деятельности. Примерами символов являются следующие знаки: ©, @, $, §, ∞.

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

Основные понятия теории формальных языков

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

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

1. - бинарный, или двоичный, алфавит, состоящий из двух знаков: 0 и 1.

2. - множество строчных букв английского алфавита.

3. Множество ASCII-символов или множество всех печатных ASCII-символов.

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

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

6. Алфавит позволяет записывать арифметические выражения над целыми числами.

Следует отметить, что алфавит содержит 10 десятичных цифр т. е. .

Слово или цепочка - это конечная последовательность знаков некоторого алфавита. Например, 01101 - это цепочка в бинарном алфавите . Цепочки 15903 и 15df10 являются цепочками в алфавите и соответственно.

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

Часто бывает необходимо или удобно классифицировать слова по их длине, т.е. по числу позиций, которые занимают знаки в слове. Например, слово 01101 имеет длину 5. Обычно говорят, что длина цепочки - это число знаков в ней. Это определение широко распространено, но не вполне корректно. Так, в цепочке 01101 всего 2 символа, но число позиций в ней - пять, поэтому она имеет длину 5. Все же следует иметь в виду, что часто пишут "число знаков", подразумевая "число позиций".

Длину некоторой цепочки обычно обозначают . Например, , а .

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

Рассмотрим примеры такой записи независимо от алфавита , т.е. - единственное слово длины 0. Для и так далее. Отметим, что между и есть небольшое различие. Дело в том, что есть алфавит, и его элементы 0 и 1 являются символами, а является множеством слов, и его элементы - это слова 1 и 0, каждое длиной 1. Мы не будем вводить разные обозначения для этих множеств, полагая, что из контекста будет понятно, является {0,1} или подобное ему множество алфавитом или же множеством цепочек.

Множество всех слов над алфавитом принято обозначать . Так, например . По-другому это множество можно записать в виде

Множество всех непустых слов в алфавите обозначают через . Таким образом, имеют место следующие равенства:

Конкатенация слов. Пусть и - слова. Тогда обозначает их конкатенацию (соединение), т.е. слово, в котором последовательно записаны слова и . Более строго, если - слово из символов: , а - слово из символов , то - это слово длины , .

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

Пусть и . Тогда , а и, следовательно, .

Для пустого слова и любого слова справедливы равенства . Таким образом, является единицей (нейтральным элементом) относительно операции конкатенации, поскольку результат ее конкатенации с любым словом дает то же самое слово (аналогично тому, как 0, нейтральный элемент относительно сложения, при сложении с любым числом дает число ). Описанные выше свойства операции конкатенации означают, что множество всех слов является (свободным) моноидом относительно операции конкатенации [29].

Если , то называется началом, или префиксом, слова , а - окончанием, или постфиксом, слова .

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

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

Рис. 6.3. Фрагмент словарного дерева (универсума) для алфавита {0, 1)

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

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

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

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

Однако оправданием использования термина "язык" для множества может служить то, что и обычные языки можно рассматривать как множества цепочек (слов). Возьмем в качестве примера русский язык, где набор всех литературных русских слов есть множество цепочек в алфавите (русских же букв). Еще один пример - язык программирования или любой другой язык программирования, в котором правильно написанные программы представляют собой подмножество множества всех возможных цепочек, а цепочки состоят из символов алфавита данного языка. Этот алфавит является подмножеством символовASCII. Алфавиты для разных языков программирования могут быть различными, хотя обычно они состоят из прописных и строчных букв, цифр, знаков пунктуации и математических символов.

Существует, однако, множество других языков. Приведем несколько примеров.

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

Множество цепочек, состоящих из 0 и 1 и содержащих поровну тех и других: .

Множество двоичных записей простых чисел: .

Множество всех правильных скобочных выражений, .

- язык для любого алфавита .

- пустой язык в любом алфавите.

\{\varepsilon\} - язык, содержащий одну лишь пустую цепочку. Он также является языком в любом алфавите. Заметим, что ; первый не содержит вообще никаких цепочек, а второй состоит из одной цепочки.

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

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

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