Теория алгоритмов для чайников. Урок 2. Математическое определение алгоритма.

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

Итак, с математической точки зрения алгоритм можно определить как четверку множеств (Q, I, Ω, f). Q - это множество, содержащее подмножества I и Ω, а f - это функция, переводящее множество Q само в себя. Функция f оставляет неподвижными все точки множества Ω, то есть f(q)=q для всех элементов q из множества Ω. Эти четыре элемента Q, I, Ω, f представляют стояния вычисления, ввод, вывод и правило вычислений. Каждое входное значение x из множества I определяет вычисляемую последовательность x₀, x₁, x₂, ... следующим образом:

x=x₀ и x_k+1=f(x_k) для k≥0.

Если k - это наименьшее целое число, для которого x_k принадлежит Ω, значит вычисляемая последовательность заканчивается через k-шагов. Эта вычислительная последовательность дает x_k для заданного x. Некоторые вычислительные последовательности никогда не заканчиваются, но алгоритм - это метод вычислений, который должен закончится за конечное число шагов для всех x из I.

Под множествами следует понимать совокупность некоторых объектов (чисел, людей, домов, каких то абстракций). Подробнее о множествах можно почитать здесь.

Что значит "множество содержит подмножество"? Если представить, что множество I - это мешок с некими предметами, а Ω - мешок с другими предметами, то множество Q - это третий мешок, в который высыпали содержимое первых двух мешком и до этого там могло что-то быть. Если говорить более строго, то объект, принадлежащий какому то подмножеству, принадлежит также множеству, которое содержит это подмножество. Но это множество может содержать и другие объекты, а может и не содержать.

Идем дальше. Что значит "f - это функция, переводящее множество Q само в себя"? Это означает, что область определения функции (множество Q) содержит в себе область значений функции, т. е. f(q) для всех элементов q множества Q также является элементом множества Q. Иными словами, аргументами функции является тот же набор значений, что и результаты вычислений этой функции. То есть, мы берем любое значение аргумента функции из области допустимых значений (множество Q), в результате получаем что-то, что также мы можем подставить в аргумент функции.

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

Идем дальше.  Чтобы было более понятно, опишу пример прошлого урока (алгоритм Евклида) через данное определение. Пусть элементами множества Q будут является все величины (n), все упорядоченные пары (m, n) и все упорядоченные четверки (m, n, r, p), где p - целое положительное число, r - неотрицательное целое число. Пусть I - это множество всех пар (m, n), Ω - множество всех величин (n). Определим функцию f - следующим образом:

f((m,n))=(m,n,0,1);

f((n))=(n);

f((m,n,r,1))=(m,n, остаток от деления m на n,2);

f((m,n,r,2))=(n) если r=0, иначе (m,n,r,3);

f((m,n,p,3))=(n,p,p,1)

Теперь разберем эту запись более подробно. Итак, мы подставляем в функцию f пару (m,n) и получаем набор (m,n,0,1). Вы, наверное, догадались, что он соответствует первому шагу алгоритма.  Подставив в функцию первый шаг, мы получим данные для второго шага: f((m,n,r,1))=(m,n, остаток от деления m на n,2). А вот подставив в функцию второй шаг, мы получаем либо результат, либо данные для третьего шага: f((m,n,r,2))=(n) если r=0, иначе (m,n,r,3). На а третий шаг переводит множество Q в вид, необходимый для первого шага: f((m,n,p,3))=(n,p,p,1). Обратите внимание, что здесь на месте m стоит n, а на месте n - остаток от деления m на n.

Возникает еще вопрос: "в чем смысл записи f((n))=(n)?". По идее, она должна создать бесконечную рекурсию. Но, это кажется только на первый взгляд. Дело в том, что данная запись - это не алгоритм, а лишь набор формул. А выражение f((n))=(n) означает, что (n) необходимо интерпретировать как выходной параметр очередного, и, в данном случае, конечного шага алгоритма.

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

Итак, пусть A - это ограниченное множество букв, а A^* - множество всех строк, определенных на множестве A, т. е . множество всех упорядоченных последовательностей x₁x₂ ... x_n, где n≥0, и x_iÎA для 1 ≤ i ≤ n. Идея заключается в том, чтобы закодировать состояния вычислений таким образом, чтобы они были представлены строками из множества A^*. Тогда пусть N - целое неотрицательное число, а Q - множество всех пар (σ, i), σÎA^*, а i целое число. 1 ≤ i ≤ N.
Пусть I - подмножество пар из Q, для которых i=0, а Ω - подмножество пар из Q, для которых i=N. Если θ и σ строки из A*, то мы будем говорить, что θ входит в σ, если σ имеет вид αθω, где  α и ω - некоторые строки.

Теперь построим функцию f при помощи строк  θ_i, φ_i и целых чисел a_i, b_i, 0 ≤ i < N:

f(σ, i) = (σ, a_i), если θ_i не входит в σ.

f(σ, i) = (αφ_iω, b_i), если α является самой короткой строкой, для которой σ=αθ_iω.

f(σ, N)=(σ, N).

Теперь объясняю, как эта функция будет работать. На входе у нас есть пары  (σ, i). Мы подставляем  их в функцию f. Если строка σ не содержит в себе  некоторую строку θ_i , то мы получаем (σ, a_i) - то есть пару строка и некое число. Иными словами, номер превращается в число a_i. Заметим, что строка при этом не меняется. Но у нас номер i может превращаться и в b_i в том случае, когда σ уже  содержит в себе  некоторую строку θ_i.

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