Теория алгоритмов для чайников. Урок 2. Математическое определение алгоритма. |
![]() |
![]() |
Автор megabax | |
08.01.2020 г. | |
Теория алгоритмов для чайников. Урок 2. Математическое определение алгоритма.Сначала я опишу строгое математическое определение алгоритма через теорию множеств, затем разъясню смысл этого определения простыми словами. Итак, с математической точки зрения алгоритм можно определить как четверку множеств (Q, I, Ω, f). Q - это множество, содержащее подмножества I и Ω, а f - это функция, переводящее множество Q само в себя. Функция f оставляет неподвижными все точки множества Ω, то есть f(q)=q для всех элементов q из множества Ω. Эти четыре элемента Q, I, Ω, f представляют стояния вычисления, ввод, вывод и правило вычислений. Каждое входное значение x из множества I определяет вычисляемую последовательность x0, x1, x2, ... следующим образом: x=x0 и xk+1=f(xk) для k≥0. Если k - это наименьшее целое число, для которого xk принадлежит Ω, значит вычисляемая последовательность заканчивается через k-шагов. Эта вычислительная последовательность дает xk для заданного 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, т. е . множество всех упорядоченных
последовательностей x1x2 ... xn,
где n≥0, и xiÎA
для 1 ≤ i ≤ n.
Идея заключается в том, чтобы закодировать состояния вычислений таким
образом, чтобы они были представлены строками из множества A*.
Тогда пусть N - целое неотрицательное число, а
Q - множество всех пар (σ, i),
σÎA*,
а i целое число. 1 ≤ i ≤ N. Теперь построим функцию f при помощи строк θi, φi и целых чисел ai, bi, 0 ≤ i < N: f(σ, i) = (σ, ai), если θi не входит в σ. f(σ, i) = (αφiω, bi), если α является самой короткой строкой, для которой σ=αθiω. f(σ, N)=(σ, N). Теперь объясняю, как эта функция будет работать. На входе у нас есть пары (σ, i). Мы подставляем их в функцию f. Если строка σ не содержит в себе некоторую строку θi , то мы получаем (σ, ai) - то есть пару строка и некое число. Иными словами, номер превращается в число ai. Заметим, что строка при этом не меняется. Но у нас номер i может превращаться и в bi в том случае, когда σ уже содержит в себе некоторую строку θi. Метод вычисления, основанный на этой модели, безусловно, является эффективным. Также опыт показывает, что в таком виде можно представить любую задачу, которая решается с помощью карандаша и бумаги. Существуют и другие эквивалентные данному способы формирования понятий эффективного алгоритма, например, машина Тьюринга.
|
|
Последнее обновление ( 08.01.2020 г. ) |
« След. | Пред. » |
---|