Удивительное дело. Люди, стоявшие у истоков того, что мы сейчас называем computer science, считали "алгоритм" понятием в принципе неопределяемым. Таким же, как, например, "множество". Но, в отличие от "множества"... Кстати, вы много видели определений множества? Кроме совсем смешного, типа: "множество - это совокупность чего-либо" (ага, ага, а совокупность - это множество чего-либо)? В отличие от "множества", в определениях "алгорима" недостатка нет. Вы без труда найдете штук пять или шесть.
Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи.
Алгоритм — это последовательность действий для исполнителя, записанная на формальном языке и приводящая к заданной цели за конечное время.
Алгоритм - описание конечной последовательности шагов в решении задачи, приводящей от исходных данных к требуемому результату.
Алгоритм — конечная совокупность точно заданных правил решения произвольного класса задач или набор инструкций, описывающих порядок действий исполнителя для решения некоторой задачи.
Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.
Алгоритм — это последовательность действий, либо приводящяя к решению задачи, либо поясняющая, почему это решение получить нельзя.
И хотя все эти определения - всего лишь чуть менее смешные, чем приведенное мной ранее определение "множества", такое упорство в общем неглупых людей наводит на мысль, что математики-основатели все-таки ошибались и определение алгоритма существует. Попробуем его найти, но сначала определимся с самим определением (извините за каламбур). Определение - это выражение некоторого сложного понятия через более простые. В идеале, оно должно состоять из одного существительного и одного прилагательного. Конечно, нечто может обладать множеством свойств, но обычно только одно из них является основным и определяющим. Его-то и следует выносить в определение, про все второстепенные можно спокойно забыть.
Я считаю что такое идеальное определение алгоритма есть. Прежде чем я вас с ним познакомлю, давайте разберемся - что не так со всеми прочими определениями.
Навскидку, можно увидеть, что почти в каждом есть слово "задача". Не знаю, как кто, но я бы не стал говорить , что "задача" это более простое понятие.
Дональд Кнут давал такое определение алгоритму:
Алгоритм — это конечный набор правил, который определяет последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность.
Здесь мы опять видим "задачу", а также целых пять свойств. Наверняка здесь что-то лишнее.
Первое свойство - "конечность". Кнут определял его так:
Алгоритм всегда должен заканчиваться после конечного числа шагов.
Ха-ха! "Всех впускать, никого не выпускать" через сколько ходов должно закончиться? А ведь это - алгоритм.
Видимо, количество тех, кому приходилось писать:
while (true)
в наше время достигло некоторой критической точки, поэтому статья в википедии https://ru.wikipedia.org/wiki/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC , например, вводит разделение на вычислительные и управляющие алгоритмы и утверждает, что управляющие могут работать бесконечно. И на том спасибо, но есть еще один немаловажный момент. Один из "отцов-основателей" Алан Тьюринг не только прямо утверждал, что некоторые алгоритмы могут работать бесконечно. Он еще и доказал, что у нас в общем случае нет никакого способа заранее узнать - остановиться ли когда-нибудь вот этот конкретный алгоритм в этом конкретном случае или нет. Т.е. пишешь ты пишешь циклы там, условия. И может быть это и есть самый настоящий алгоритм, а может и нет. Никто ж не знает. Как вы понимаете, это свойство можно смело выкидывать.
Второе свойство - определенность.
Каждый шаг алгоритма должен быть точно определен. Действия, которые нужно выполнить, должны быть строго и недвусмысленно определены для каждого возможного случая.
Для кого, простите, должны быть определены шаги алгоритма? Для исполнителя? Да, некоторые перефразируют этот момент у Кнута во что-то типа: "Алгоритм должен быть понятен исполнителю". Вообще, слово "должен" меня всегда настораживает. Я слишком хорошо знаю, что в этом мире никто никому ничего не должен. Но, допустим, что алгоритм именно должен, именно исполнителю и именно быть понятным. Вам понятно вот это?
Аааааааааа[> Ааааааа> Аааааааааа> Ааа> A< < < < я]>
Аа* > А* Ааааааа* * Ааа* > Аа* < < Ааааааааааааааа* > *
Ааа* яяяяяЯ* яяяяяяяЯ* > А* > *
А это - алгоритм из почтенного семейства алгоритмов Hello World! Он написан на некоторой разновидности брейнфака, которую я только что придумал. Понятен ли он исполнителю? А какому? Нет никакого исполнителя. Возможно он появится, если я напишу примерно шестьдесят строчек кода на C, Java или 1С. Но, скорее всего, я не стану этим заниматься. Видите в чем дело? Нам стоит признать, что алгоритм существует независимо от исполнителя. А как иначе? Алгоритм существует, пока его исполняют? А когда перестают исполнять, он исчезает?
Да, можно сказать, что этот алгоритм понятен мне, его создателю. Но это пока. Завтра я забуду, что я тут напридумывал, и что? Алгоритм исчезнет? А послезавтра я вспомню. Он возродится? Алгоритм существует независимо не только от исполнителя, но и от создателя. Иначе, как вы объясните тот факт, что Евклид, светлая ему память, уже давно прекратил делить большее на меньшее, а алгоритм Евклида все еще существует?
Алгоритм существует независимо от исполнителя и независимо от создателя. И, в принципе, может быть не понятен никому и, при этом, продолжать свое существование. Свойство определенности(понятности) можно убрать.
Третье свойство - ввод.
Алгоритм имеет некоторое (возможно, равное нулю) число входных данных...
То есть, входные данные могут быть, а могут и отсутствовать (и это действительно так). Но если входные данные могут быть, а могут и не быть, то такое свойство для определения не важно.
Самое интересное четвертое свойство - вывод.
У алгоритма есть одно или несколько выходных данных...
То есть, мы должны прийти к какому то результату, решить какую-то задачу. Решить или решать постоянно (это в случае с бесконечными алгоритмами). Почему я говорю, что это свойство самое интересное? Потому что, слова "задача" или "результат" вы обнаружите в любом определении алгоритма.
Можно было бы сказать, что алгоритм - это способ решения задачи. Но это будет плохое определение. А что такое "задача"? Вот есть известный армейский алгоритм - "копать от забора и до обеда". На решение какой задачи будут направлены действия исполнителя? Могут ли существовать действия без задачи? А почему нет!
Нас невозможно сбить с пути, нам все равно, куда идти.
Можно ли описать такие действия? Ну, а какие проблемы!
"Задача", "результат", "цель" - все это лишнее, не приближает нас ни на шаг к пониманию сущности алгоритма.
Да, осталось еще пятое свойство. Но его никто, кроме автора, не воспринимал всерьез (возможно, что и автор тоже).
Эффективность. Алгоритм обычно считается эффективным, если все его операторы достаточно просты для того, чтобы их можно было точно выполнить в течение конечного промежутка времени с помощью карандаша и бумаги.
Итак у нас нет никаких пяти свойств. А также нет ни "задач", ни "результатов". Может показаться, что теперь у нас вообще ничего нет. Но это не так. Представьте себе лестницу из трех ступенек и робота с двумя ногами. Все что он может - это поставить правую или левую ногу на ступеньку под номером 1,2 или 3. Можно сказать что у нас есть всего шесть возможных команд: П1,П2,П3,Л1,Л2,Л3. Попробуйте написать алгоритм подъема снизу на самый верх этой коротенькой лестницы. У вас должно получиться что-то типа:
Л1
П2
Л3
П3
или
П1
Л2
П3
Л3
Есть ли какая-нибудь разница в том, с какой ноги начинать: с правой или с левой? Как вы понимаете, разницы никакой нет. Значит, можно начинать с любой ноги? С любой нельзя. Начинать надо конкретно с правой или конкретно с левой. Вы должны сделать выбор. И пока вы его не сделаете, робот будет стоять внизу.
В этом мире все имеет последствия, но не все имеет причину. Что-то когда-то начинается. У всякой цепочки причин-следствий есть первое звено. Способность создавать такое первое звено, давать начало называется волей.
Безусловно, алгоритм - это проявление воли. Но не только. Для того, чтобы создать алгоритм, мы должны сделать еще кое-что. Мы должны дать нашей воле свободу. Освободить ее от себя. Обеспечить ее независимое существование от нас, ее родителя. В сущности, алгоритм и есть такая освобожденная от родителя воля. Освобождение от родителя (или опекуна) называется словом "эмансипация". Поэтому окончательное определение алгоритма выглядит так:
Алгоритм - это эмансипированная воля.
Как я и обещал, здесь у нас одно существительное и одно прилагательное. Кроме того, "эмансипация" и "воля" - понятия более простые, чем определяемое. Поэтому, я нахожу это определение идеальным.