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

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

Первоначально для записи алгоритмов использовались средства обычного языка. И поэтому изучение теории алгоритмов целесообразно начать именно со словесного описания алгоритмов.

Пример1. _n

Например: С= П А_i

ⁱ⁼¹

Процесс вычисления может быть записан в виде следующей системы указаний:

1 Полагаем С=1 и переходим к следующему указанию.

2 Полагаем i=1 и переходим к следующему указанию.

3 Полагаем С=С*А_i и переходим к следующему указанию.

4 Проверяем равно ли i числу N+1 . Если i=N+1 вычисления прекращаем , иначе увеличиваем i на 1 и переходим к указанию 3.

В этом простейшем алгоритме в качестве элементарных операций используются

простейшие арифметические операции.

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

Пример 2.

Алгоритм нахождения минимального числа Х в массиве из n чисел A₁, A₂,…A_n.

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

Примерами логических алгоритмов могут служить алгоритмы поиска минимального числа, пути в графе, пути в лабиринте и т.п.

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

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

Примеры A={ a, b, g, ¾ }

B={ x, y }

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

a, ab, ¾bb, a ¾b, ….

Xy, yyy, xyxx…..

Число символов в слове называется длиной слова.

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

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

Так например, в алфавите А={0,1,2,…,9} выражение 63+79 представляет собой 2 слова, соединенных знаком +, а в алфавите В={+,0,1,2,…,9} это будет одно слово.

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

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

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

Пусть нам заданы слова в алфавитах А и В и заданы соответствия между этими словами.

Если a – слово в алфавите А, а b – слово в алфавите , то алфавитный оператор Гa=b перерабатывает входное слово a в выходное слово b.

Г - алфавитное отображение.

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

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

a₁----------------------------------------------b₂

a₂----------------------------------------------b₃

a₃----------------------------------------------b₁

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

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

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

Большое значение имеют так называемые кодирующие отображения.

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

Рассмотрим пример кодирующего отображения:

Заданы 2 алфавита:g

А={p,r,s,t} – входной;

B={aa,b,c,d,f,g,h,m,n,q} –выходной;

Отображения символов А символами В:

P qdb

R mn

S fgh

T abcd

Пусть задано слово

a=sstr , тогда Гa=fghfghabcdmn – код некоторого слова a в алфавите В.

Процесс обратный кодированию, т.е. замена в слове b_j кодов алфавита В словами из алфавита А, называется декодированием и обозначается Г^-1b_j = a_i.

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

Если при кодировании слова a_i получаем некоторое слово b_{j ,} а декодирование дает исходное слово a_i (Гa_i = b_j,, Г^-1b_j = a_i. ), то имеет место обратимость кодирования.

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

Рассмотрим еще один пример:

Даны А = {a,b,c}

B = {a,b}

Гa = a, Гb = b, Гc=a_b

И слово aabca в алфавите А.

Гaabca = aababa

Г^-1aababa = aababa

acca

aabca

acaba

т.е. обратимость отсутствует.

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

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

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

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

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

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

Наиболее часто в качестве такого алфавита выбирается двоичный алфавит С={0,1}.

Если n- число символов в алфавите А, а m- число символов в алфавите С, то всегда можно выбрать длину слова l так, чтобы удовлетворялось условие m^l >= n.

Поскольку число различных символов длины l в m-символьном алфавите равно m^l, то все символы в алфавите А можно закодировать словами длины l в алфавите С так, чтобы коды различных букв были различны. Любое такое кодирование будет нормальным и порождает обратное кодирующее отображение слов в алфавите А в слова в алфавите С. Обозначим это отображение через Гa = c, а обратное ему отношение Г^-1с=a, где

a- слово в алфавите А,

с-слово в алфавите С.

Пусть ja – произвольный оператор в алфавите А такой, что ja = a¹, а yc – произвольный алфавитный оператор в алфавите С такой, что yc =с¹. Тогда отображение yc = Г^-1с, ja, Гa¹, ( 1 )

получаемое в результате последовательного выполнения отображений Г^-1с, ja, Гa¹ будет представлять собой некоторый оператор в стандартном алфавите С.

Назовем этот оператор yc алфавитным оператором в алфавите С сопряженным (при помощи кодирования Гa¹ и декодирования Г^-1с ) с алфавитным оператором ja. Оператор ja однозначно восстанавливается по сопряженному оператору yc и соответствующим кодирующему Гa и декодирующему Г^-1с , отображениям ja=Гa, yc , Г^-1с¹ ( 2 )

Рассмотрим взаимосвязь сопряженных операторов на графе.

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

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

yc = Г^-1с, ja, Гb

ja=Гa, yc , Г^-1с¹

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

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

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

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

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

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

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

Но это не совсем так.

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

1) Ограничение разрешающей способности прибора, воспринимающего информацию.

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

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

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

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

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

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

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

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

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

Всякий АО является непременно алгоритмом.

Однако в понятии АО существенно лишь само соответствие, устанавливаемое мужду входными и выходными словами, а не способ, которым это соответствие устанавливается.

В понятии алгоритма, наоборот, основным является способ задания соответствия, устанавливаемого алгоритмом.

Т.о, алгоритм – АО вместе с правилами, определяющими его действияю

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

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

Два алгоритма считаются эквивалентными, если у них совпадают АО, но не совпадают способы их задания ( система правил )

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

Такие алгоритмы и соответствующие им АО называются детерминированными.

К числу других свойств алгоритмов относятся массовость и результативность.

Массовость – свойство алгоритма быть применимым для множества слов.

Результативность – свойство, обеспечивающее получение результата через конечное число шагов.

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

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

Теперь эквивалентность алгоритма может быть определена следующим образом:

Два алгоритма эквивалентны, если совпадают их области применимости и результаты переработки любого слова из этой “области”.

В общем случае различают еще случайные и самоизменяющиеся алгоритмы.

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

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

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

Всякий общий способ задания алгоритмов называется алгоритмической систеимой.

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

Основные формализмы прикладной теории алгоритмов можно разделить на 2 направления:

- “алгебраическое”

- “геометрическое”

“Алгебраическая” теория строится в некоторой конкретной символике, при которой алгоритмы рассматриваются как некоторые линейные тексты.

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

К первому направлению относятся рекурсивные функции, машины Тьюринга,, опреторные системы Ван-Хао, А.В. Ляпунова, логические схемы алгоритмов Ю.И.Якоби и др.

Ко 2-му направлению относятся представления нормальных алгоритмов А.А.Маркова в виде граф-схем, предложенных Л.А.Калужинным и др.

Предлагаю ознакомиться с аналогичными статьями: