Файл: Алферова З.В. Теория алгоритмов учеб. пособие.pdf

Примеры алфавитов: А = {а, |3, у, н } , В = {х, у}.

Под словом или строкой алфавита будем понимать любую ко­ нечную упорядоченную последовательность символов.

Так, например, в алфавите А словами следует считать любые последовательности a, ay, yfi, ^' - 'Р, РР и т. п., в алфавите В— х, у, ху, ух, хх, уу и т. п.

Число символов в слове называется длиной этого слова. Так, слова из алфавита А, приведенные в примере, имеют длину соот­ ветственно 1, 2, 2, 3, 2, . . .

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

Очевидно, что такое понятие слова будет отличаться от понятия слова, принятого в обычном языке. При нашем определении слова­ ми следует считать любые сочетания и последовательности симво­ лов, в том числе и бессмысленные.

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

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

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

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

Пусть нам заданы слова в алфавитах Л и В и заданы соответ­ ствия между этими словами (рис. 1).

Если а — слово в алфавите А, а р — слово в алфавите В, то ал­ фавитный оператор Га = р «перерабатывает» входное слово а в вы­ ходное слово р.

Буква Г в алфавитном операторе означает отображение. Различают однозначные и многозначные алфавитные операторы.

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

9

Алфавитный оператор, не сопоставляющий данному входному слову сц никакого выходного слова bj (в том числе и пустого), не определен на этом слове.

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

Рис. 1

Рис. 2

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

Рассмотрим пример кодирующего отображения. Заданы алфа­

волов А символами В (рис. 3).

Рис. 3

Для построения искомого кодирующего отображения достаточ­ но заменить все символы любого слова ai в алфавите А соответст­ вующими кодами алфавита В.

10

Если п — число символов в алфавите А, а т — число символов в алфавите С, то всегда можно выбрать длину слова / так, чтобы удовлетворялось условие т1^п.

Поскольку число различных слов длины / в m-символьном ал­ фавите равно т1, то все символы в алфавите А можно закодировать словами длины / в алфавите С так, чтобы коды различных букв бы­ ли разными. Любое такое кодирование будет нормальным и порож­ дает обратимое кодирующее отображение слов в алфавите А в сло­ ва в алфавите С.

Обозначим это отображение через Га = с, а обратное ему ото­

Применение формул (1) и (2) позволяет сводить произвольные алфавитные операторы к алфавитным операторам в стандартном алфавите.

Эти соотношения справедливы и для случая, когда входной ал­ фавит А, выходной алфавит В и стандартный алфавит С различны, т. е. для случая алфавитных операторов, у которых входной и вы­ ходной алфавиты различны.

<j)C = Г~'с, сра, П>; сра = Га, Фс, Г - 'с' .

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

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

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

Для некоторых специальных видов информации, например ин­ формации лексической или числовой, применяется алфавитный спо-

12

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

Ч>0

fa

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

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

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

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

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

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

13

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

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

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

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

Третье ограничение обусловлено тем, что полоса пропускания прибора не позволяет ему различать слишком быстрые измене­ ния воспринимаемых величин.

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

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

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

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

Входные слова Выходные слова

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

14