2015-05-13
564
Под этим интуитивно понятным на первый взгляд словом кроется огромная теория и годы усиленных трудов многих математиков. Казалось бы, сформулировать определение алгоритма проще простого: алгоритм — четкое и понятное исполнителю указание выполнить последовательность действий, направленных на получение какого-то результата. Однако, существуют такие задачи, решение которых опирается на некую последовательность действий, которая укладывается в данное определение, но говорят, что для решения этой задачи не существует алгоритма. Например, знаменитая задача коммивояжера, в которой имеется таблица стоимости проезда из одного города в другой. Требуется посетить все города, но по такому маршруту, чтобы стоимость путешествия была наименьшей. Единственным решением на сегодняшний день является перебор всевозможных маршрутов с замером стоимости. Всего таких маршрутов будет n!, где n — число городов. Если число городов будет 100, то перебрать нужно будет 100! вариантов, а это число больше, чем количество частиц во всей Вселенной. Понятно, что решить эту задачу невозможно, хотя для того, чтобы ее решить, нужно выполнять последователь действий, похожих по определению на алгоритм.
Для того, чтобы утверждать, что задача имеет алгоритм, достаточно просто предъявить его; а для того, чтобы утверждать, что задача не имеет решения, необходимо это доказать. Для доказательства используют специальные теории (для этого используется абстрактная машина Тьюринга или абстрактная машина Поста).
Понятие алгоритма четко привязано к понятию исполнителя. Исполнитель умеет исполнять команды, но не вникает в смысл команд, поэтому он может выполнить только то, что ему предписано. Предположим, что ребенок — это исполнитель, и мы пошлем его в магазин.
1. Если мы ему скажем «пойди в магазин и купи чего-нибудь», то в итоге мы не получим результата, потому что нарушается свойство определенности. Алгоритм не должен содержать команды, смысл которых может быть понятен неоднозначно.
2. Если мы скажем ребенку «go to the shop and buy a bread», то он вряд ли вообще что-то сделает, так как скорее всего он не поймет наших слов. Алгоритм должен быть понятен исполнителю, то есть команды должны содержаться в системе команд исполнителей (СКИ).
3. Мы можем сказать «пойди в магазин и купи хлеба». А если в магазине хлеба нет, то мы останемся без хлеба. Значит, алгоритм должен выдавать результат.
4. Если поступит команда «пойди в магазин, купи хлеба. Если хлеба в этом магазине нет, то пойди в следующий». В этом случае ребенок может пойти в один другой магазин, если в первом магазине нет хлеба, то ребенок может пойти в тот, в котором он уже был, затем опять во второй и т.д. Вывод: алгоритм должен заканчиваться, а не продолжаться бесконечно.
5. Если мы скажем ребенку «понимаешь, нет хлеба, поэтому было бы неплохо, если бы ты сходил в этот магазин или какой-то другой, если считаешь, что тот, куда ты пошел в первый раз по каким-то причинам тебе не подходит. Только не ходи в те, где ты уже был», то получится, что мы рассказали ребенку целую историю и в итоге в нем не содержится именно последовательности действий. Алгоритм должен содержать именно последовательность действий, то есть быть дискретным.
6. Наконец, наши команды должны «посылать» ребенка не только за хлебом, но, например, и за молоком, то есть для любых входных данных мы должны получить требуемый результат.
Итак, свойства алгоритма:
1) определенность;
2) понятность;
3) результативность;
4) конечность;
5) дискретность;
6) массовость.
