Учебно-методический комплекс дисциплины для обучающегося «Языки программирования» для специальности 5В010900 Математика

Например, если заданы входной А = {а, b, с, d} и выходной В = {0,1,2,3,4, 5,6,7,8,9} алфавиты, а также отображение алфави­та A в алфавит В (рис. 1.3), то для построения искомого кодирую­щего отображения достаточно заменить все символы любого слова а, в алфавите А соответствующими кодами алфавита В.

Процесс, обратный кодированию, т. е. замена в слове кодов алфавита В символами из алфавита А, называется декодированием и обозначается .

Например, для слова = 9314567878 в алфавите В декодирова­ние Г^-1 дает слово а = acbb.

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

В приведенном выше примере обратимость имеет место.

Пусть теперь имеем А = {а, b, с}, В = {0,1}, Га = 0, Гb = 1, Гс = 01 и слово aabca в алфавите А.

Тогда Гааbса = 001010 и Г^-1001010 = aababa (либо одно из слов acaba, aabca, acca), т. е. обратимость отсутствует.

Для обратимости кодирования должны выполняться следующие условия.

1. 
   Коды разных символов исходного алфавита А должны быть различны.
   
2. 
   Код любого символа алфавита А не может совпадать ни с ка­ким из начальных подслов кодов других символов этого алфавита.
   

Второе условие выполняется в том случае, если коды всех сим­волов исходного алфавита А имеют одинаковую длину.

Кодирование, при котором все коды имеют одинаковую дли­ну, называют нормальным.

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

При этом если п — число символов в алфавите 4, то всегда можно выбрать длину слова так, чтобы удовлетворялось условие 2ⁱ > п.

Поскольку число различных слов длины в двоичном алфавите равно 2ⁱ, то все символы в алфавите А можно закодировать слова­ми длины в алфавите В так, чтобы коды различных букв были раз­ными. Любое такое кодирование будет нормальным и порождает обратимое кодирующее отображение слов в алфавите А в слова в алфавите В.

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

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

Основой теории алфавитных операторов являются способы и задания.

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

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

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

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