Алгоритмы

Понятие алгоритма и его характерные черты

Понятие алгоритма принадлежит к числу основных понятий математики. Примерами алгоритмов являются:

1. 
   Правила выполнения арифметических действий над числами.
   
2. 
   Правило отыскания наибольшего общего делителя (алгоритм Евклида).
   
3. 
   Правило извлечения квадратного корня.
   
4. 
   Правило отыскания решений квадратного уравнения.
   
5. 
   Правило отыскания производной многочлена n-ой степени.
   
6. 
   Правило интегрирования рациональной функции.
   

В каждом из приведённых примеров приходится иметь дело с классом однотипных задач, или, как говорят, с массовой проблемой. Задачи такого класса отличаются друг от друга значениями входящих в них параметров. Так, в задаче отыскания решения квадратного уравнения ax²+bx+c=0 участвует три параметра a, b и c; меняя их, получаем различные задачи одного класса.

В связи со сказанным можно дать следующее интуитивное определения понятия алгоритма.

Алгоритмом называется общий единообразный, точно определённый способ решения любой задачи из данной массовой проблемы.

Отметим характерные черты понятия алгоритма.

1. 
   Дискретность алгоритма. Алгоритм – это процесс последовательного построения величин таким образом, что в начальный момент задаётся исходная конечная система величин, а в каждый следующий момент система величин получается по определённому закону из системы величин, имевшихся в предыдущий момент.
   
2. 
   Детерминированность алгоритма. Система величин, получаемых в какой-то не начальный момент, однозначно определяется системой величин, полученных в предшествующие моменты времени.
   
3. 
   Элементарность шагов алгоритма. Закон получения последующей системы величин из предшествующей должен быть простым.
   
4. 
   Массовость алгоритма. Начальная система величин может выбираться из некоторого потенциально бесконечного множества.
   
5. 
   Результативность алгоритма. Последовательный процесс построения величин должен быть конечным и давать результат, то есть решение задачи.
   

Разрешимые и перечислимые множества

Пусть имеется некоторый алфавит. Обозначим через S множество всех слов в данном алфавите, а через M подмножество множества S.

Определение 1. Множество М называется разрешимым, если для него существует алгоритм, решающий проблему вхождения слова x в М.

Определение 2. Множество М называется эффективно перечислимым, если существует алгоритм, позволяющий перечислить все элементы этого множества (возможно с повторениями).

Теорема 1. Если множества М и L эффективно перечислимы, то эффективно перечислимы множества M  L и M  L.

Доказательство. Пусть множества М и L эффективно перечислимы. Тогда для каждого из них существует свой алгоритм, позволяющий перечислить все элементы данного множества. Алгоритм для эффективного перечисления множеств М  L и M  L получается путём одновременного применения алгоритмов для эффективного перечисления множеств М и L.

Теорема 2 (Поста). Множество М разрешимо тогда и только тогда, когда оно само и его дополнение эффективно перечислимы.

Доказательство. Путь множество М и его дополнение СМ эффективно перечислимы, то есть существуют алгоритмы А и В, с помощью которых можно перечислить элементы этих множеств. Но тогда при перечислении элементов множеств М и СМ в их списке встретится элемент х. Следовательно, существует алгоритм С, позволяющий узнать, принадлежит элемент x множеству М или не принадлежит.

Пусть множество М разрешимо. Тогда существует алгоритм, решающий проблему вхождения x в М. Пользуясь этим алгоритмом, составим список элементов, входящих в М, и список элементов, входящих в СМ. Следовательно, мы получим два алгоритма А и В, позволяющих перечислить множества М и СМ. Примерам эффективно перечислимого множества являются множество М = {1, 4, 9 ,…,n²,…} квадратов натуральных чисел.

Действительно, множество М = {n²} перечислимо, т.к. для получения его элементов нужно последовательно брать натуральные числа и возводить их в квадрат. Более того, это множество является также и разрешимым: для проверки того, принадлежит ли некоторое натуральное число х множеству М, нужно разложить число на простые множители, и это даст возможность установить, является ли оно точным квадратом.

Теорема 3. Существует перечислимое, но неразрешимое множество натуральных чисел. Для доказательства теоремы, как это следует из теоремы Поста, достаточно привести пример такого множества натуральных чисел U, которое само было бы перечислимым, а его дополнение CU перечислимым не было.

Пусть М₀, М₁, М₂, … – эффективное перечисление всех перечислимых множеств натуральных чисел, т.е. такое перечисление, что по любому n  N можно восстановить само множество М_n.

Рассмотрим теперь алгоритм А, который последовательно перечисляет все элементы множества U. На шаге с номером (m, n) этот алгоритм вычисляет элемент с номером m множества М_n, и если этот элемент совпадает с n, то оно относит его в множество U, т.е. nU  nM_n.

Отсюда ясно, что множество CU отличается от любого перечислимого множества хотя бы одним элементом, т.к. CU состоит из всех таких элементов n, что n  M_n. Поэтому CU не является перечислимым. Следовательно, согласно теореме Поста U не разрешимо.

Уточнение понятия алгоритма

В истории математики накопилось много случаев длительных и часто безрезультатных поисков тех или иных алгоритмов. При этом естественно возникало сомнение в существовании алгоритма.

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

В 1900 году на втором международном математическом конгрессе в Париже немецкий математик Давид Гильберт огласил список 23 трудных проблем, на важность решения которых он обращал внимание математической общественности. Среди них была и следующая 10-я проблема Гильберта: требуется выработать алгоритм, позволяющий для любого диофантова уравнения выяснить, имеет ли оно целочисленное решение.

Рассмотрим всевозможные диофантовы уравнения, т.е. уравнения вида P = 0, где P является многочленом с целочисленными коэффициентами. Такими будут, например, уравнения

x² + y² – 2xz = 0,

10x⁵ + 7x² + 5 = 0,

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

Так, уравнения x² + y² – 2xz = 0 имеет бесконечное множество целочисленных решений, а уравнение 10x⁵ + 7x² + 5 = 0 таких решений не имеет.

Для частного случая диофантова уравнения с одним неизвестным давно известен алгоритм, позволяющий найти все целочисленные решения. Установлено, что если уравнение

Р_n(x) = a₀xⁿ + a₁x^n-1 +…+ a_n-1x + a_n = 0

с целочисленными коэффициентами имеет целый корень, то он обязательно является делителем а_n. В связи с этим можно предложить такой алгоритм:

1. 
   Найти все делители числа а_n: d₁, d₂, …, d_n.
   
2. 
   Вычислить P_n(x) для каждого из делителей числа а_n.
   
3. 
   Если при некотором i из совокупности 1, 2, …, k Р_n(d_i) = 0, то d_i – корень уравнения. Если при всех i = 1, 2, …, k Р_n(d_i)  0, то уравнение не имеет целочисленных решений.
   

Поиски решения десятой проблемы Гильберта привлекли внимание многих математиков и длились около 70 лет. И только в 1968 году молодым математиком Ю.Матиясевичем было доказано, что нет алгоритма, дающего решение поставленной задачи.

В подходах к определению понятия алгоритма можно выделить три основных направления.

Первое направление связано с уточнением понятия эффективно вычислимой функции. Этим занимались А.Черч, К.Гедель, С.Клини, определившие алгоритм как последовательность построения сложных функций из более простых. В результате был выделен класс так называемых частично-рекурсивных функций, имеющих строгое математическое определение. Анализ идей, приведших к этому классу функций, дал им возможность высказать гипотезу о том, что класс эффективно вычислимых функций совпадает с классом частично рекурсивных функций.

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

Третье направление связано с понятием нормальных алгоритмов, введённым и разработанным российским математиком А.А.Марковым. В рамках этого направления алгоритм рассматривается как конечный набор правил подстановок цепочек символов.

Удивительным научным фактом является доказательство эквивалентности приведенных выше определений алгоритма. Эквивалентность двух абстрактных моделей алгоритма состоит в том, что любой класс проблем, которые можно решить с помощью моделей одного типа, можно решить и на моделях другого типа. Оказалось, что все известные алгоритмы могут быть представлены аналогичными алгоритмами в рамках предложенных направлений (различных определений алгоритма).

Вычислимые функции. Частично рекурсивные и общерекурсивные функции

Для алгоритмических проблем типичным является то обстоятельство, что требуется найти алгоритм для решения задачи, в условия которой входят значения некоторой конечной системы целочисленных параметров x₁, x₂,…, x_n, а искомым результатом также является целое число y. Следовательно, стоит вопрос о существовании алгоритма для вычисления значений числовой функции y, зависящей от целочисленных значений аргументов x₁, x₂,…, x_n.

Определение 1. Функция называется эффективно вычислимой, если существует алгоритм, позволяющий вычислить ее значения.

Переход от алгоритма к эффективно вычислимой функции дает определенные преимущества. Дело в том, что все требования, которые предъявляются к алгоритмам, выполняются и для совокупности всех вычислимых функций, которая получила название совокупности рекурсивных функций.

Класс вычислимых функций можно построить следующим образом. Для начала выбираются простейшие функции:

1. 
   (x) = x + 1 (оператор сдвига),
   
2. 
   O(x) = 0 (оператор аннулирования),
   
3. 
   I_n^m(x₁, x₂,…, x_n) = x_m (оператор проектирования).
   

Ясно, что все три простейшие функции всюду определены и интуитивно вычислимы.

Далее вводятся операции над функциями.

1. 
   Суперпозиция функций. Пусть определены функции f₁(x₁, x₂,…, x_n), f₂(x₁, x₂,…, x_n), …, f_m(x₁, x₂,…, x_n) и функция (x₁, x₂,…, x_m). Говорят, что функция (x₁, x₂,…, x_n) получена суперпозицией функций f_i(x₁, x₂,…, x_n), если справедливо равенство
   

(x₁, x₂,…, x_т) = ( f₁(x₁, x₂,…, x_n), f₂(x₁, x₂,…, x_n), …, f_m(x₁, x₂,…, x_n)).

Если каким-либо образом можно вычислить функции f_i для определенных значений a_i переменных x_i, то, очевидно можно вычислить и функцию .

2. 
   Схема примитивной рекурсии. Пусть имеются две функции (x₂, x₃,…, x_n) и (x₁, x₂,… , x_n, x_n+1) (n > 1). Рассмотрим новую функцию, которая удовлетворяет следующим равенствам:
   

f(0, x₂, x₃,…, x_n) = (x₂, x₃,…, x_n),

f(y + 1, x₂, x₃,…, x_n) = (y, f(y, x₂, x₃,…, x_n), x₂, x₃,…, x_n).

Отметим, что функция  зависит от n – 1 аргументов,  – от n + 1, а f – от n.

Функции, определенные с помощью таких равенств называются функциями, полученными по схеме рекурсии.

В качестве примера рассмотрим функцию f(y, x):

f(0, x) = x,

f(y + 1, x) = f(y, x) + 1.

Здесь функция (x) = x, а (y, f(y, x), x) = y + 1. Рассмотрим, как можно вычислить значение функции f(y, x) при y = 5, x = 2. Так как f(0, x) = (2) = 2, то из второго равенства последовательно имеем (начиная с y = 0):

f(1, 2) = (0, 2, 2) = 2 + 1 = 3,

f(2, 2) = (1, 3, 2) = 3 + 1 = 4,

f(3, 2) = (2, 4, 2) = 4 + 1 = 5,

f(4, 2) = (3, 5, 2) = 5 + 1 = 6,

f(5, 2) = (4, 6, 2) = 6 + 1 = 7 – искомое значение функции.

3. 
   Операция минимизации (-оператор). Пусть задана некоторая функция f(x, y). Зафиксируем значение x и выясним, при каком значении y f(x, y) = 0. Так как результат зависит от x, то наименьшее значение y, при котором f(x, y) = 0, есть функция от x. Принято обозначение
   

(x) = y[f(x, y) = 0].

(читается: «наименьшее y такое, что f(x, y) = 0»)

Аналогично можно определить функцию для многих переменных:

( x₁, x₂,…, x_n) = y[f(x₁, x₂,…, x_n, y) = 0].

Переход от функции f к функции  называется применением -оператора.

Функция  может быть вычислена следующим образом:

1. 
   Вычислим f(x₁, x₂,…, x_n, 0). Если это значение f = 0, то полагаем ( x₁, x₂,…, x_n) = 0 и завершаем вычисление. Иначе переходим к следующему шагу.
   
2. 
   Вычислим f(x₁, x₂,…, x_n, 1). Если это значение f(x₁, x₂,…, x_n, 1) = 0, то полагаем ( x₁, x₂,…, x_n) = 1 и завершаем вычисление. Иначе переходим к следующему шагу. И т.д.
   

Если окажется, что для всех достижимых (т.е. принадлижащих области определения) значений у функция f(x₁, x₂,…, x_n, у)  0, то функцию ( x₁, x₂,…, x_n) считают неопределенной.

Определение 2. Функция f(x₁, x₂,…, x_n) называется частично рекурсивной, если она может быть получена за конечное число шагов из простейших функций при помощи операций суперпозиции, схем примитивной рекурсии и -оператора.

Определение 3. Функция f(x₁, x₂,…, x_n) называется общерекурсивной, если она частично рекурсивна и всюду определена.

Примерами общерекурсивных функций являются: f(x, y) = x + y, f(x, y) = x  y, f(x, y) = x + n.

Тезис А. Чёрча. Каждая интуитивно вычислимая функция является частично рекурсивной.

Этот тезис нельзя доказать, так как он связывает нестрогое понятие интуитивно вычислимой функции со строгим математическим понятием частично рекурсивной функции. Но этот тезис можно опровергнуть, если построить пример функции интуитивно вычислимой, но не являющейся частично рекурсивной.

Машины Тьюринга.

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

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

Рассмотрим один из вариантов указанной машины.

Устройство машины Тьюринга включает в себя:

1. 
   Внешний алфавит, т.е. конечное множество символов А = {а₀, а₁, а₂,…, а_n}. В этом алфавите в виде слова кодируется та информация, которая подаётся в машину. Машина перерабатывает информацию, поданную в виде слова, в новое слово.
   
2. 
   Внутренний алфавит машины, состоящий из символов q₀, q₁, q₂, …, q_m, п, л, н. Символы q₀, q₁, q₂, …, q_m выражают конечное число состояний машины. Для любой машины число состояний фиксировано. Два состояния имеют особое назначение: q₁ – начальное состояние машины, q₀ – заключительное состояние (стоп-состояние). Символы п, л, н – это символы сдвига (вправо, влево, на месте).
   
3. 
   Бесконечная в обе стороны лента (внешняя память машины). Она разбита на клетки. В каждую клетку может быть записана только одна буква. Пустую клетку будем обозначать символом а₀.
   
4. 
   Управляющая головка. Она передвигается вдоль ленты и может останавливаться напротив какой-либо клетки, т.е. воспринимать символ или печатать символ. В одном такте работы машины управляющая головка может сдвигаться только на одну клетку (вправо, влево) или оставаться на месте.
   

Каждое сведение, хранящееся на ленте, изображается конечным набором символов (букв) внешнего алфавита, отличного от а₀. К началу работы машины на ленту подаётся начальное сведение (начальная информация). В этом случае управляющая головка, как правило, находится у крайнего левого знака с указанием начального состояния q₁ (начальная конфигурация).

А0

а1

а2

а3

…

…

…

аn

а0

А0

q₀
Работа машины складывается из тактов, по ходу которых происходит преобразование начальной информации в промежуточные информации.

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

1. 
   После конечного числа тактов машина останавливается (переходит в стоп-состояние q₀), и при этом на ленте оказывается изображённой информация В. В таком случае говорят, что машина применима к начальной информации А и перерабатывает её в результирующую информацию В.
   
2. 
   Машина никогда не останавливается (не переходит в стоп-состояние). В таком случае говорят, что машина не применима к начальной информации А.
   

В каждом такте работы машины она действует по функциональной схеме, которая имеет вид:

a_iq_{j } a_v{п, л, н}q_s

Здесь a_i, a_v – буквы внешнего алфавита; q_j, q_s – состояния машины; п, л, н – символы сдвига.

В зависимости от того, какая буква на ленте обозревается управляющей головкой (в нашей записи a_i) и в каком состоянии (в нашей записи q_j) находится машина, в данном такте вырабатывается команда, состоящая из трёх элементов:

1. 
   Буква внешнего алфавита, на которую заменятся обозреваемая буква (a_v).
   
2. 
   Адрес внешней памяти для следующего такта {п, л, н}.
   
3. 
   Следующее состояние машины (q_s).
   

Совокупность всех команд образует программу машины Тьюринга. Программа представляется в виде двумерной таблицы и называется Тьюринговой функциональной схемой.

	a0	a1	a2
q1	a2 л q3	a1 п q2	a2 л q1
q2	a0 н q2	a2 н q1	a1 н q2
q3	a0 п q1	a1 п q4	a2 н q1
q4	a1 н q3	A0 п q4	a2 п q4

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

Основная гипотеза теории алгоритмов.

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

На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы:

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

Эта гипотеза называется тезисом Тьюринга. Её нельзя доказать, т.к. она связывает нестрогое определение понятия алгоритма со строгим определением понятия машины Тьюринга.

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

Однако все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем.

Напомним также, что другие способы уточнения понятия алгоритма (понятие нормального алгоритма А.А.Маркова, понятие рекурсивного алгоритма (рекурсивной функции), введённого Чёрчем, Гёделем и Клини) оказались равносильными.

Этот факт является важным доводом в пользу сформулированной гипотезы.

Нормальные алгоритмы Маркова

Основная операция при работе алгоритмов Маркова – это переработка слов в некотором алфавите А. Алфавитом называется всякое непустое конечное множество символов, а сами символы – буквами. Словом в алфавите А называется всякая конечная последовательность букв данного алфавита.

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

Алгоритм представляет собой совокупность строк определенного вида, причем порядок строк имеет важнейшее значение. Формат строки следующий:

{a_i}  {b_j} [•], где

{a_i} – последовательность символов, которая ищется в слове

 – знак перехода к операции записи

{b_j} – последовательность символов, которая записывается вместо найденной [•] – знак принудительного окончания алгоритма (необязательный параметр).

Окончание работы алгоритма происходит в тот момент, когда выполняется строка, содержащая знак принудительной остановки, либо тогда, когда более ни одна строка не может быть выполнена (в слове нет ни одной из искомых последовательностей символов).

Например, алгоритм, состоящий из одной строки, вида 0  * будучи примененным к слову в алфавите {0,1}, заменит все нули на звездочки.

В свою очередь алгоритм0  * • будучи примененным к слову в алфавите {0,1}, заменит на звездочку первый встреченный ноль.

Довольно сложная для реализации на машинах Тьюринга задача сортировки слова по возрастанию, допустим в алфавите {0,1,2}, решается при помощи Маркова весьма изящно:

20  02

10  01

21  12

Некоторые задачи переработки слов нельзя решить без расширения алфавита. Например, дано произвольное двоичное слово. Надо убрать из него два первых знака. Рассмотрим алгоритм вида:

00  •

01  •

10  •

11  •

Если в слове случайно первыми двумя символами были нули (например, «001011»), то алгоритм действительно выполнит указанную задачу. Также работа закончится успешно, если в слове ни разу не встретилось два нуля подряд, а первыми символами оказалась пара 01 (например, «01011101»). Но в слове 1100101 выбросятся два нуля, которые вовсе не являются первыми символами слова. В этом случае существующий алфавит надо расширить вспомогательными буквами, которых нет в начальном слове, и которые появляются в ходе вычисления. По сути, это некоторые аналоги внутренней памяти (состояний машин Тьюринга). Они вводятся с помощью формулы λ  α (α – вспомогательная буква) или, что более корректно, пары формул

λ 0  α 0

λ 1  α 1

Применив такие правила к слову λ 1100101 λ, получим: λ α 1100101 λ.

Дальше мы перемещаем эту букву по слову вправо, стирая и отсчитывая символы

(стерли первый):

α 0  β

α 1  β

(стерли второй):

β 0  •

β 1  •

Однако если мы расположим эти строки в обычном порядке, а именно:

λ 0  α 0

λ 1  α 1

α 0  β

α 1  β

β 0  •

β 1  •

алгоритм будет работать совсем не так, как хотелось бы. В частности вся его деятельность будет сводиться к созданию бесконечно большого числа символов α поочередно со стиранием символов слова. Это связано с тем, что после выполнения каждой замены управление передается снова первой строке, а слово анализируется с левого символа. Поэтому чаще всего алгоритм пишется как бы «снизу-вверх», т.е. в самом начале ставятся строки, относящиеся к группе «окончание алгоритма», далее «тело программы» и в самом низу блок «инициализация», которая будет выполняться только однажды, а затем управление перейдет к более ранним строкам.

Правильный алгоритм выглядит следующим образом.

β 0  •

β 1  •

α 0  β

α 1  β

λ 0  α 0

λ 1  α 1

Ту же самую задачу можно решить, используя всего один дополнительный символ:

α00 •

α01 •

α10 •

α11 •

α0 •

α1 •

λ 0  α 0

λ 1  α 1