Алфавитные операторы и алгоритмы

Основные понятия о определения теории алгоритмов.

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

Абстрактным алфавитом называется любая совокупность объектов, называемая буквами или символами данного алфавита.

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

Таким образом, абстрактный алфавит — это конечное множество различных символов.

А = { ᵝ , ᵠ , ᵋ , ᶯ } B = {0,1} C = {♠,♣,♥,♦}

Слово (строка абстрактного алфавита) — это любая конечная упорядоченная последовательность символов.

С = 00111100

Вводится понятие «длина слова» - число символов в данном слове.

На ряду со словами положительной длины, которые состоят из 1 и > символов, в теории алгоритмов оперируют понятием «пустого слова», которое обозначают « е ».

На ряду с понятием целого слова в теории алгоритмов оперерируют понятием «подслова» (начальное)

Слово p называют начальным подсловом некоторого заданного слова q, если выполняется равенство

q = p * r, где r – некоторое слово (в том числе и пустое)

a = aabbh a = pr p = aa r=bbh

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

G = {0,1,2,..9} “23 + 67” = g'

g1 g2

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

23 + 67 = 90 Б: Кре5, Фа7, Ла7, Кф1

G' (23 + 67)= 90 r: Крб3, Лс5, …

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

Алфавитный оператор — это всякое соответствие, сопоставляющее словам некоторого алфавита слова в некотором другом или этом же фиксированном абстрактном алфавите. При этом I алфавит — входной, II – выходной алфавит данного алфавитного оператора.

Слова в А Слова в В

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

Если Аi — слово во входном алфавите, а Bj — выходное, то тогда алфавитный оператор Гai = bj преобразует входное ai в выходное bj.

Различают однозначные и многозначные алфавитные операторы.

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

Многозначный — 1 входной — несколько выходных.

А В

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

С каждым алфавитным оператором связано интуитивное представление о его сложности.

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

Кодирующее отображение — каждый символ Sx во входном слове p заменяется последовательностью символов выходного алфавита. Указанная последовательность называется кодом.

А В

A = {a,b,c,d} Гa = 123

B = {1,2,3....} Гb = 45

Процесс обратный кодированию называется декодированием — замена в слове bj кодов алфавита B символами алфавита A.

Условие обратимости кодирования еще иначе называют условием взаимной однозначности исходного и кодирующего отображения.

Гai = bj

Гbj = ai

A = {a,b,y}

B = {n,m}

Гb = n Гa = m Гy = mn

p = aabya

Гp = mmnmnn = p'

Гp'^-1 = a y y a != p

Лекция 3

Не сложно увидеть, что кодирование будет обратимым, когда выполняются следующее 2 условия:

1) коды различных символов исходного алфавита А должны быть различны;

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

Заметим, что условие 2 всегда выполняется в том случае, если при выполнении условия 1 коды всех символов исходного алфавита А будут иметь одинаковую длину.

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

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

Пусть А — произвольный конечный абстрактный алфавит, состоящий из более чем одного символа. С — стандартный двоичный алфавит. Пусть n – это число символов в алфавите А, а m – число символов в С. Тогда всегда можно подобрать число k так, чтобы выполнялось неравенство

m^k >= n

Число различных слов одинаковой длины k в m-символьном алфавите будет равно m^k, следовательно неравенство показывает, что все символы исходного алфавита А можно закодировать одинаковыми словами длины k в алфавите C. таким образом, чтобы все коды были различными. Любое такое кодирование будет нормальным в следствии чего — порождать обратимое кодирующее отображение слов входного алфавита А кодами выходного алфавита С.

Дано:

А = {α,β,γ,δ}

C = {0,1}

Осуществить нормальное кодирование слова P = αβγδ символами нормального алфавита.

N = 4; M =2 2^k >= 4 k >= 2; kmin = 2 2^2 = 4 (всего комб-й)

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

Таблица графический аналитический способ

Мы уже условились обозначать нормальное кодирование в стандартном алфавите как Гa = C.

Тогда обратное ему отображение имеет вид Гc^-1 = a

Пусть ϕa – произвольный алфавитный оператор в алфавите а такой, что ϕа = а', а ψC – произвольный алфавитный оператор C такой, что ψC = C'. тогда отображение ψC = Гc^-1, ϕа, Га', который получается в результате последовательного выполнения этих отображений, будет представлять собой алфавитный оператор в алфавите С.

ψC = Гс^-1, ϕа, Га'

ψC – сопряженный с фа алфавитный оператор в алфавите С, который получается с помощью кодирования Га' и декодирования Гс^-1.

Исходный алфавитный оператор фа однозначно восстанавливается по сопряженному ψc.

ϕа = Га, ψc, Гс^-1

ψc = Гс^-1, ϕа, Га'

ϕa = Гa, ψc, Гc^-1

a ϕa a'

Га Га Га'

c ψc c'

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

a ϕa b

Га^-1 Гb

c ψc c'

ψc = Гa^-1, ϕa, Гb

ϕa = Гa', ψc, Гс^-1

Лекция 4

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

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

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

I	аi	Гai
	а1	б4
	а2	б3
	а3	б2
	а4	б1

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

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

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

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

Два алгоритма называются эквивалентными, если им соответствует одинаковый алфавитный оператор, но не совпадает система правил.

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

Массовость — это свойство алгоритма быть применимым к множеству строк.

Результативность — это свойство алгоритма для любой из множества строк обеспечивать получение однозначного результата через конечное число шагов.

Из свойства результативности вытекает понятие области применимости алгоритма — множество строк для которых алгоритм результативен.

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