В каком случае говорят что два алгоритма эквивалентны

ФОРМАЛЬНЫЕ ПРЕОБРАЗОВАНИЯ АЛГОРИТМОВ

Поможем написать любую работу на аналогичную тему

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

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

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

В “чистом виде” понятие эквивалентности двух алгоритмов U1 и U2 будем определять следующим образом. Для каждого алгоритма вводится понятие “входа” и “выхода”. Для каждого входа, который имеет смысл для данного алгоритма, выполнение алгоритма может приводить к некоторому выходу. Пусть х1 и х2 —

входы алгоритмов U1 и U2 соответственно. Алгоритмы U1 и U2 считаются эквивалентными, если из условия х1 == х2 следует, что если хотя бы один алгоритм, например U1, имеет выход у1, то и другой алгоритм также имеет выход у2, причем у1 == у2.

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

В этом случае между некоторыми входами х1 алгоритма U1 и входами х2 алгоритма U2 конструктивно задается некоторый изоморфизм I (в данном случае понимаемый просто как однозначное соответствие). Аналогично задается некоторый изоморфизм J между выходами у1 и у2 алгоритмов U1 и U2 соответственно.

Предикат от двух конструктивных объектов А и В “быть в соответствии, заданном изоморфизмом L ” будем обозначать через Аl

Эквивалентность теперь будет определяться следующим образом. Алгоритмы U1 и U2 считаются эквивалентными, если из условия х1

х2 следует, что если хотя бы один алгоритм имеет выход у1,то и другой алгоритм также имеет выход у2, причем у1

Разные виды эквивалентности отличаются тем, как определяются “входы” и “выходы” алгоритма, а также тем, как фактически выбираются изоморфизмы I и J.

Между различными видами эквивалентности можно ввести частичное отношение порядка, выражающееся словами “сильнее” и “слабее”. Будем считать, что отношение эквивалентности Э1 слабее отношения эквивалентности Э2, если любые алгоритмы U1 и U2, эквивалентные в смысле Э2, эквивалентны и в смысле Э1, и в то же время есть хотя бы одна пара алгоритмов U1,U2 таких, что U1, U2, которые эквивалентны в смысле Э1 и не эквивалентны в смысле Э2.

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

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

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

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

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

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

Источник

АЛГОРИТМОВ ЭКВИВАЛЕНТНОСТЬ

Расстановка ударений: АЛГОРИ`ТМОВ ЭКВИВАЛЕ`НТНОСТЬ

В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны

(оно считается верным, если обе его части осмысленны одновременно и в случае осмысленности принимают одинаковые значения). С. К. Клини (S. C. Kleene; см., напр., [1], с. 314) показал, что для любого всюду определенного вычислимого оператора В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентнынад рекурсивными схемами можно указать схему S такую, что S и В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны(S) функционально эквивалентны (так наз. теорема о неподвижной точке). Отсюда, в частности, вытекает теорема Успенского-Райса о неразрешимости произвольного инвариантного относительно функциональной эквивалентности свойства рекурсивных схем при условии, что имеются схемы S1 и S2 такие, что S1 обладает этим свойством, a S2 им не обладает. Из этой теоремы следует неразрешимость и самого отношения функциональной эквивалентности.

б) Рассматриваются нормальные алгорифмы над фиксированным алфавитом А. Два таких алгорифма В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныи В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныназ. эквивалентными относительно А (см. [2], с. 51), если для любого слова Р в А выполняется следующее условие: если один из этих алгорифмов перерабатывает Р в нек-рое слово Q, снова оказывающееся в алфавите А, то и второй из них также перерабатывает Р в Q. Те же алгорифмы наз. вполне эквивалентными относительно А, если для любого Р в А выполняется условное равенство

В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны

Оба эти отношения неразрешимы.

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

Детальное изучение отношений А. э. представляет большой интерес в связи с рядом актуальных задач (особенно в области теории схем программ), требующих для своего решения развитой техники эквивалентных преобразований алгоритмов. Таковы, напр., задача трансляции алгоритмов (перевод с одного алгоритмич. языка на другой) и их оптимизации (преобразование с целью улучшения «рабочих характеристик»). В этом круге вопросов особое внимание уделяют (см., напр., [5]) возможности отыскания таких разрешимых отношений А. э., к-рые допускали бы удобные в приложениях полные системы эквивалентных преобразований. Концепция, намеченная в [3], во многом предопределила общий подход к исследованию отношений А. э.

Лит. : [1] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; [2] Марков А. А., Теория алгорифмов, М., 1954; [3] Янов Ю. И., «Проблемы кибернетики», 1958, в. 1, с. 75-127; [4] Ершов А. П., «Проблемы кибернетики», 1968, в. 20; [5] его же, там же, 1973, в. 27.

Источник

knigechka

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

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

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

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

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

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

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

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

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

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

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

Алгоритм нахождения минимального числа Х в массиве из n чисел A1, A2,…An.

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

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

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

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

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

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

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

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

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

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

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

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

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

В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны

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

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

В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны

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

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

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

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

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

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

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

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

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

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

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

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

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

В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Источник

АЛГОРИТМОВ ЭКВИВАЛЕНТНОСТЬ

В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны

Оба эти отношения неразрешимы.

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

Детальное изучение отношений А. э. представляет большой интерес в связи с рядом актуальных задач (особенно в области теории схем программ), требующих для своего решения развитой техники эквивалентных преобразований алгоритмов. Таковы, напр., задача трансляции алгоритмов (перевод с одного алгорптмич. языка на другой) и их оптимизации (преобразование с целью улучшения «рабочих характеристик»). В этом круге вопросов особое внимание уделяют (см., напр., [5]) возможности отыскания таких разрешимых отношений А. э., к-рые допускали бы удобные в приложениях полные системы эквивалентных преобразований. Концепция, намеченная в [3], во многом предопределила общий подход к исследованию отношений А. э.

Лит.:[1] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957; [2] Марков А. А., Теория алгорифмов, М., 1954; [3] Янов К). И., «Проблемы кибернетики», 1958, в. 1, с. 75-127; [4] Ершов А. П., «Проблемы кибернетики», 1968, в. 20; [5] е го же, там же, 1973, в. 27.

Источник

knigechka

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

3. Формальные преобразования алгоритмов

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

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

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

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

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

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

На формальном уровне понятие эквивалентности двух алгоритмов U1 и U2 будем определять следующим образом:

• для каждого алгоритма вводится понятие «входа» и «выхода»;

• для каждого входа, который имеет смысл для данного алгоритма, выполнение алгоритма может приводить к некоторому выходу.

Алгоритмы U1 и U2 считаются эквивалентными, если из условия Х1=Х2 следует, что если алгоритм U1 имеет выход У1, то и другой алгоритм U2 имеет выход У2=У1.

На практике большое значение имеет определение эквивалентности с точностью до изоморфизма.

Изоморфизм – это взаимно однозначное соответствие между двумя множествами каких-либо объектов.

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

В этом случае между некоторыми входами Х1 алгоритма U1 и входами X2 алгоритма U2 конструктивно задается некоторый изоморфизм i (в данном случае понимаемый как однозначное соответствие).

Аналогично задается некоторый изоморфизм j между выходами Y1 и Y2 алгоритма U1 и U2 соответственно.

Эквивалентность теперь будет определяться стандартным образом:

-алгоритмы U1 и U2 считаются эквивалентными, если из условия Х1 i

Х2 следует, что если хотя бы один алгоритм имеет выход Y1, то другой алгоритм имеет выход Y2, причем Y1 j

Разные виды эквивалентности отличаются тем, как определяются «входы» и «выходы» алгоритма, а также тем, как выбираются изоморфизмы i и j. Между различными видами эквивалентности можно ввести частичное отношение порядка, выражающиеся словами «сильнее» и «слабее».

Будем считать, что отношение эквивалентности Э1 слабее отношения эквивалентности Э2, если любые алгоритмы U1 и U2, эквивалентные в смысле Э2, эквивалентны и в смысле Э1, и в то же время есть хотя бы одна пара алгоритмов U1 и U2, таких, что U1 и U2 эквивалентны в смысле Э1 и не эквивалентны в смысле Э2.

Очевидно, чем слабее отношение эквивалентности, тем шире класс алгоритмов, эквивалентных согласно этому отношению.

С одной стороны такое расширение классов рассматриваемых алгоритмов – хорошо, однако, при слишком слабом определении эквивалентности алгоритмов проблема распознавания эквивалентности алгоритмов может оказаться неразрешимой.

С другой стороны, слишком сильное определение эквивалентности чрезмерно сужает классы эквивалентных алгоритмов.

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

На степень широты понятия эквивалентности наиболее существенно влияет выбор определения «выхода» алгоритма.

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

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

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

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

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

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

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

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

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

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

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

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

Соответствующие им переменные, играющие аналогичную роль в U2:

Алгоритмы U1 и U2 эквивалентны по отношению к выделенным переменным В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныВ каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныВ каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны Y1,…Yn и В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны1,…В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныn, если для любого набора исходных данных В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны1,…В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныs, имеет место следующее утверждение:

если какой-либо из этих алгоритмов, например, U1 имеет значение для исходных данных В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны1,…В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныs и S – представления выделенных переменных имеет вид: T1(Xi11,…Xi1m1,Pj11,…Pj1l1)àY1;

то другой алгоритм U2 также имеет значение для исходных данных В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны1,…В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныs и S-представления выделенных переменных имеют вид:

T1(В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныi11,… В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныi1m1, В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныj11,… В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныj1l1)à В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны1;

T2(В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныi21,… В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныi2m2, В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныj21,… В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныj2l2)à В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентны2;

Tn(В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныin1,… В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныinmn, В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныjn1,… В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныjnln)à В каком случае говорят что два алгоритма эквивалентны. Смотреть фото В каком случае говорят что два алгоритма эквивалентны. Смотреть картинку В каком случае говорят что два алгоритма эквивалентны. Картинка про В каком случае говорят что два алгоритма эквивалентны. Фото В каком случае говорят что два алгоритма эквивалентныn;

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

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

Источник

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *