Теория алгоритмов для чайников. Урок 1. Введение.

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

Алгоритм - это не просто набор конечной последовательности действия. Он также должен обладать пять следующими свойствами:

• Конечность. Алгоритм всегда должен заканчиваться за конечное число шагов.

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

• Входные данные. Алгоритм должен иметь какие то входные данных. В некоторых частных случаях количество входных данных может быть равно нулю.

• Выходные данные. Выходные данные - это результат работы алгоритма - те переменные или какая то информация, которая образуется в результате работы алгоритма.

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

Часто алгоритм сравнивают с кулинарным рецептом. И там и там есть входные и выходные данные. Например, в кулинарных рецептах на входе - набор продуктов (например, мука, яйца, мясо, соль, сахар), на выходе - готовая еда, например, пирожки с мясом. Но, в отличии от алгоритма, в рецепте часто бывают неконкретные и расплывчатые понятия. Например: "добавьте щепочку соли". Возникает вопрос: а щепотка соли - это сколько в граммах? Конечно, опытный повар прекрасно знает, сколько соли надо добавить в тех или иных ситуациях. Но вот компьютер не сможет выполнить такое действие. Ему нужны точные и конкретные команды. Например, если бы робот из фантастического рассказа готовил обед, то инструкция для него звучала бы примерно так: "насыпать в кастрюлю 1 грамм соли". Но мы живем в реальном мире и роботы пока не умеют готовить обеды. А компьютеры - тем более, у них даже рук то для этого нет. Единственное, что умеют компьютеры - это выполнять определенную последовательность команд, сформулированных на специальном компьютерном языке. Пример такой команды: "Сложить содержимое ячейки A и B и поместить в ячейку C". Именно поэтому алгоритм должен быть сформулирован четко и однозначно, чтобы его можно было перевести в последовательность машинных команд.

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

Итак, пусть даны два числа m и n. Необходимо найти их наибольший общий делитель. Вот так можно описать алгоритм сего действия:

1). Вычислим остаток от деления m на n и поместим результат вычисления в переменную r.

2). Если r=0 тогда прекращаем выполнение программы: искомое значение n.

3). В переменную m поместить значение n, затем в переменную n значение r и перейти к шагу 1.

Давайте подумаем, обладает ли этот алгоритм перечисленными пятью свойствами. В частности, являются ли он конечным? Давайте разберемся. У нас имеются три случая: m=n, m>n и m<n. В первом случае остаток от деление будет равен 0 и алгоритм прекратиться на первой же итерации. Во втором случае на каждой итерации числа m и n буду уменьшаться. Почему? Потому что на третьем шаге переменной m будет присвоена переменная n, которая меньше по условию. А переменной n присвоиться остаток от деления m на n, который тоже меньше n. Получается, что на следующей итерации у нас условие m>n сохраниться, но при этом новые m и n будут меньше старых. До каких пор они могут уменьшаться? До единицы. Если n=1, то остаток от деления m на n будет 0, алгоритм завершен. Остался третий случай. В этом случае сразу понятно, что m нацело не разделиться на n, если конечно, n не равно единице. Но тогда алгоритм сразу же завершиться, поэтому мы этот случай рассматривать уже не будем. Будем рассматривать ситуацию, когда n≠1. Тогда у нас после выполнения шага 1 появиться значение r<n. На шаге 3 мы сделаем присвоение m переменной n. По условию А в n поместим r. Но так как r<n, значит, теперь у нас будет m>n. А для этого случая мы уже доказали, что алгоритм конечный.

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

Приведу примеры неэффективных алгоритмов, чтобы было более понятно, что подразумевается под эффективностью. Например, вышеописанный алгоритм был бы неэффективен, если бы операция вычисления остатка от деления проводилась не над целыми числами, а над действительными числами, которые представляют собой бесконечные десятичные дроби. В этом случае было бы просто невозможно получить остаток от деления. Другой пример. Если наибольшее целое n при котором существует решение уравнения wⁿ+xⁿ+yⁿ=zⁿ равно 4, то переходим к шагу такому то. В этом случае вообще непонятно, как определять это самое n. Но если у нас уже есть разработанный эффективный алгоритм поиска n, то тогда шаг может звучать так "Вызвать предопределенный алгоритм поиска n, при котором существует решение уравнения wⁿ+xⁿ+yⁿ=zⁿ и если результат работы данного алгоритма будет равен 4, то перейти к шагу такому то". Вот тогда это будет уже эффективный алгоритм.

Следует также сказать, что для практических задач, ограничение, состоящее в конечности алгоритма, является недостаточно жестким. При решении практических задач алгоритм должен иметь не просто конечное количество шагов, а количество шагов в пределах разумного. Дело в том, что скорость выполнения операций на компьютере есть определенная конечная величина. Если шагов алгоритма будет слишком много, то программа может выполняться длительно время. Таким образом, под "пределом разумного" тут следует понимать такое число шагов алгоритма, чтобы программа выполнялась не больше времени, чем согласен ждать конечный пользователь. В качестве примера такого алгоритма можно привести задачу определения выигрышной стратегии игры в шахматы путем перебора всех возможных ходов. Американский математик Шеннон примерно посчитал количество вариантов. Это оказалось число 10¹¹⁸ (1 и 118 нулей!). Предположим, что компьютер делает миллиард операций в секунду. Сделаем также очень грубое допущение, что 1 операция - это обработка одного варианта (на самом деле, на обработку одного варианта может потребоваться тысячи операций). Даже с учетом нашего грубого допущения, время просчета всех вариантов составит 10¹⁰⁹ секунд или ≈3•10¹⁰¹ лет. Для сравнения, наша Вселенная существует только 15 млрд. лет 1,5•10¹⁰. Иными словами, окончания работы такой программы мы никогда не дождемся.

Может возникнуть вопрос: а как же тогда компьютеры играют в шахматы, если это "невозможно". Дело в том, что одну и ту же задачу можно решать совершенно разными алгоритмами. Например, надо сложить числа от 1 до 100. Можно их действительно складывать. А можно 101 умножить на 50. Ответ будет точно такой же, потому что меду числам 1 и 100 равно 50 пар чисел, сумма которых 101 (например 100 и 1, 99 и 2, 98 и 3, ...). Таким образом, мы входим в новую область знаний - так называемый анализ алгоритмов. Предметом этой области исследования является определение рабочих характеристик алгоритма.

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

Решение подобных задач и есть анализ алгоритмов. Идея заключается в том, чтобы взять конкретный алгоритм и определить его количественные характеристики. Помимо вычисления среднего, а также минимального и максимального количества итераций, данная область знаний занимается также определением зависимости количества итераций от различных параметров алгоритма. Такая зависимость может быть линейной, квадратно, кубической, n-ой степени, факториально, или, наоборот, логарифмической. В зависимости от этого определяют качество алгоритма. Например, в плохих алгоритмах сортировки количество итераций, как правило, пропорционально квадрату количества сортируемых элементов. Почему это плохо? Потому, что если число элементов увеличить в два раза, то алгоритм будет работать в 4 раза дольше, а если в 1000 раз больше - то время выполнения алгоритма увеличиться в миллион раз (если программа выполняюсь секунду, то после увеличения в миллион раз она будет выполняться более 11дней). Разумеется, есть и хорошие алгоритмы сортировки, где зависимость не такая резкая. См. также циклы уроков Алгоритмы и Алгоритмы (платный раздел).