Сдам Сам

ПОЛЕЗНОЕ


КАТЕГОРИИ







Понятие алгоритма и его общие свойства





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

Имеется ряд свойств, присущих любому алгоритму:

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

б) Массовость алгоритма. Алгоритм служит не для решения какой-либо одной конкретной задачи, а для решения целого класса задач. Указания о методе действия применимы к начальным данным, которые могут варьироваться.

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

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

Процедуру для решения одной индивидуальной задачи не назы­вают алгоритмом. Так, например, неизвестен алгоритм, позволяющий для любого n = 1,2,3.4,... определить имеет ли уравнение

(3.7)

целочисленное решение.

Тем не менее для конкретных значений n эта задача может быть решена. Так, для n=2 можно легко подобрать тройку чисел (x=3, y=4, z=5), удовлетворяющую уравнению. Для n=3 удалось до­казать, что уравнение не имеет целочисленных решений. Но эго до­казательство уже не годится для иных n.

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

Так при применении алгоритма поиска к любому как угодно сложному (но конечному!) лабиринту, после конечного числа шагов обязательно наступит остановка либо на площадке F, либо на площадке A. По тому, где наступила остановка, мы делаем вывод о дос­тижимости площадки F.

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



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

0.4

0.4

0.4

….

и так до бесконечности. Подобная картина будет наблюдаться и для пары а=-2, b=6.

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

Так, областью применимости алгоритма Евклида служит мно­жество целых чисел (1. 2, 3, 4,..); областью применимости алго­ритма поиска является множество всех конечных лабиринтов; об­ласть применимости десятичного алгоритма суммирования - все чис­ла в десятичной записи с конечным числом разрядов, и т.д.

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

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

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

Нормальный алгоритм Маркова

По аналогии с интуитивным определением алгоритма определим понятие "алгоритм в алфавите А":

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

Алгоритм применим к некоторому слову Р, если, отправляясь от этого слова и действуя согласно предписаний, мы получим в конце концов новое слово Q, на котором процесс оборвется. Будем тогда говорить, что алгоритм перерабатывает Р в Q.

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

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

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

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

Приведем пример алгоритма в алфавите А в смысле II.

Пусть алфавит А содержит три буквы: А = {а, b, с}, а алгоритм определен с помощью системы подстановок

cd - cc,

cca - ad,

ab - bca

 

и следующего указания о способе применения этих подстановок: исходя из произвольного слова Р, следует просмотреть схему подстановок в том порядке, в каком они выписаны, разыскивая первую формулу, левая часть которой входит в Р. Если же такой формулы не найдется, то процесс обрывается сразу же. В противном случае берется первая из найденных формул и делается подстановка ее правой части вместо первого вхождения ее левой части в слово Р, что дает новое слово Р1, в алфавите А. Затем слово Р1 играет роль Р, т.е. вновь берется в качестве исходного, и процесс повторяет­ся. Остановка наступает в том случае, если на n-м шаге получено слово Pn, в которое не входит ни одна из левых частей формул схемы подстановок.

Итак, схема подстановок вместе с указанием как ими пользо­ваться, определяет алгоритм в алфавите А. Этот алгоритм перера­батывает слово babaac в слово bbcaac (применена 3-я формула), слово cbacacb - последовательно в слова ccacacd, ccacacc, abcacc и, наконец, в bcacacc, на котором процесс обрывается; слово bсасаbс порождает бесконечно повторяющуюся последовательность слов bcacabc. bcacbcac, bcaccac, bcacabc и т. д.. т.е. остановка нe наступит, и, следовательно, к слову bcacabc наш алгоритм неприменим.

Наш алгоритм несколько напоминает такой способ задания дви­жения в бесконечном лабиринте: выйдя на какую-либо площадку, иди в первый коридор направо и т.д. Остановка наступит, когда при­дешь в тупик. Ясно, что здесь также может быть три случая: отхо­дя от данной площадки, мы можем либо попасть в тупик (сравни слово сbасасb), либо бесконечно кружиться по циклу (сравни слово bcacabc), либо двигаться бесконечно долго, не попадая в циклы.

С первого взгляда можно решить, что определение алгоритма в смысле II уже, чем определение в смысле I. Однако оказывается, что на деле такого сужения нет, ибо для любого известного алго­ритма в смысле I может быть построен эквивалентный ему алгоритм в смысле II. Это, конечно, не доказательство того, что определения I и II равносильны: такого доказательства не может существовать вообще в силу неточности и расплывчатости обоих определений (везде фигурируют слова "общепонятное, точное предписание").

Во всяком случае, очевидно, что определение II - шаг вперед по пути уточнения понятия "алгоритм".

Определим теперь понятие эквивалентности алгоритмов: два алгоритма и в некотором алфавите называются эквивалентны­ми, если области их применимости совпадают, и результаты перера­ботки ими любого слова из общей области применимости также сов­падают. Иначе говоря, если алгоритм применим к некоторому слову Р, то и должен быть применим к этому слову, и наоборот;

оба алгоритма должны перерабатывать слово Р в некоторое слово Q. Если же один из алгоритмов неприменим к некоторому слову B, то и другой алгоритм должен быть неприменим к нему.

Для того чтобы дать точное математическое определение алго­ритма, потребовалось сделать еще один шаг по пути дальнейшего уточнения. Этот шаг был сделан А. A. Марковым. Построенный им нормальный алгоритм, так же как и алгоритм в смысле определения II, выражен в терминах системы подстановок; однако вместо расп­лывчатого "общепонятного указания" о том, как пользоваться подс­тановками, Марков дал стандартные, раз и навсегда определенные точные указания о порядке использования подстановок. Определение нормального алгоритма Маркова таково:

Задается алфавит А и фиксируется схема подстановок. Алго­ритм предписывает, исходя из произвольного слова P в алфавите А, просмотреть формулы подстановок в том порядке, в каком они зада­ны в схеме, разыскивая формулу с левой частью, входящей в Р. Ес­ли такой формулы не найдется, то процесс обрывается. В противном случае берется первая из таких формул и делается подстановка ее правой части вместо первого вхождения ее левой части в Р, что дает новое слово Р1, в алфавите А. После только что выполненного первого шага процесса приступают ко второму его шагу, отличающе­муся от первого только тем. что роль Р играет Р1. Далее делают аналогичный третий шаг и т.д. до тех пор, пока не придется обор­вать процесс. Оборваться же он может лишь двумя способами: во-первых, когда мы получим такое слово Рn, что ни одна из левых частей формул схемы подстановок не будет в него входить; во-вторых, когда при получении слова Рn нам придется применить последнюю формулу. В обоих этих случаях мы считаем, что наш алгоритм перерабатывает слово Р в слово Рn.

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

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

Понятие алгоритма в некотором алфавите было уточнено Марко­вым следующим образом: всякий алгоритм в алфавите А эквивалентен некоторому нормальному алгоритму в этом же алфавите.

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

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

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

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

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

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

Впервые такие примеры были построены А. А. Марковым в 1946 г. и Э. Постом в 1947 г.

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

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

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

Пусть в некотором алфавите А={а1, а2, … аn} задан с по­мощью системы подстановок нормальный алгоритм U. В записи этого алгоритма, кроме букв алфавита А, содержатся символы ® и , . При­писав этим символам новые буквы аn+1 и аn+2 мы получим возмож­ность изображать алгоритм U словом в расширенном алфавите А={а1, а2, … аn+2} . Применим теперь алгоритм U к слову, кото­рое его изображает.

Если алгоритм U перерабатывает это слово в некоторое иное слово, после чего наступает остановка, то это означает, что ал­горитм U применим к собственной записи. Такой алгоритм назовем самоприменимым. В противном случае алгоритм будем называть несамоприменимым. Естественно, возникает задача распознавания самоп­рименимости: по записи данного алгоритма определить, самоприме­ним этот алгоритм или нет.

Решение этой задачи мыслится в виде построения некоторого нормального алгоритма V. который, будучи применен ко всякой за­писи самоприменимого алгоритма U, перерабатывает эту запись в некоторое слово М, а примененный ко всякой записи несамоприменимого алгоритма U, перерабатывает эту запись в некоторое иное слово L. В этом случае по результату применения распознающего алгоритма V мы могли бы узнать, является ли данный алгоритм U самоприменимым или нет.

Доказано, что такого нормального алгоритма V не существует: тем самым доказано, что проблема распознавания самоприменимости алгоритмически неразрешима. Доказательство проводится от против­ного. Допустим, что нормальный алгоритм V распознавания построен и перерабатывает всякую запись самоприменимого алгоритма в слово М, а всякую запись несамоприменимого алгоритма в слово L.

Tогда, путем некоторого изменения системы подстановок алгоритма V можно построить иной алгоритм Ũ, который всякую записи несамоприменимого алгоритма по-прежнему перерабатывает в слово L, а ко всякой записи самоприменимого алгоритма неприменим (остановка никогда не наступает). Итак, Ũ применим ко всякой записи несамоприменимого алго­ритма (перерабатывая ее в слово L) и неприменим к записи самоприменимых алгоритмов (остановка не наступает). Однако это приво­дит к противоречию. Действительно:

1. Пусть Ũ самоприменим, т.е. он применим к собственной записи в виде слова (остановка наступает). Но это свидетельствует как раз о том, что Ũ несамоприменим.

2. Пусть Ũ несамоприменим, тогда он применим к своей записи (так. как он применим к любой записи несамоприменимого алгоритма): но это означает как раз, что Ũ самоприменим.

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

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

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

До уточнения понятия "алгоритм" в математике было две точки зрения:

1) Все проблемы, для решения которых. пока не удалось найти алгоритм, алгоритмически разрешимы, но искомый алгоритм еще не найден, потому что не хватает средств в современной математике для его построения. Иначе говоря, в наше время ситуация в ряде проблем похожа на ситуацию, когда пытались найти площадь круга с помощью циркуля и линейки или решить уравнение n-ой степени в радикалах. Естественно, что решения найдено не было, так как для этого использовались недостаточные средства. Может быть и нам для решения проблем, которые мы называем алгоритмически неразре­шимыми, просто не хватает средств современной математики, и построение искомых алгоритмов дело завтрашнего дня?

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

Утверждение это тем более сильно, что оно имеет характер прогноза на все будущие времена, применительно ко всем будущим средствам. Не тратьте сил зря на поиски несуществующих алгорит­мов!

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

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

 









Не нашли то, что искали? Воспользуйтесь поиском гугл на сайте:


©2015- 2018 zdamsam.ru Размещенные материалы защищены законодательством РФ.