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

Областью применимости алгоритманазывается совокупность тех объектов, к которым он применим. Про алгоритмUговорят, что он:

1. «Выявляет функцию f», коль скоро его область применимости совпадает с областью определенияf, иUперерабатывает всякий х из своей области применимости вf(x);

2. «Разрешает множество А относительно множества Х», коль скоро он применим ко всякому х из Х и перерабатывает х из ХА в слово «да», а всякий х из Х\А в слово «нет»;

3. «Перечисляет множество В», коль скоро его область применимости есть натуральный ряд, а совокупность результатов есть В.

Функция называется вычислимой, если существует вычисляющий ее алгоритм. Множество называетсяразрешимым (рекурсивным)относительно Х, если существует разрешающий его относительно Х алгоритм. Множество называетсяперечислимым (рекурсивно-перечислимым), если либо оно пусто, либо существует перечисляющий его алгоритм.

Замечания:

1. Область возможных исходных данных и область применимости любого алгоритма суть перечислимые множества;

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

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

4. Процесс выполнения алгоритма называется алгоритмическим процессом.

Основные теоремы теории алгоритмов.

Теорема 1:Функцияfвычислима тогда и только тогда, когда перечислим ее график, то есть множество всех пар вида <x,f(x)>.

Теорема 2:Подмножество А перечислимого множества Х разрешимо относительно Х тогда и только тогда, когда А и Х\А перечислимы.

Теорема 3:Если А и В перечислимы, то АВ и АВ также перечислимы.

Теорема 4:В каждом бесконечном перечислимом множестве Х существует перечислимое подмножество с неперечислимым дополнением (в силу теоремы 2 это перечислимое подмножество будет неразрешимым относительно Х).

Теорема 5: Для каждого бесконечного перечислимого множества Х существует вычислимая функция, определенная на подмножестве этого множества и не продолжаемая до вычислимой функции, определенной на всем Х.

Параметры алгоритма.

Как правило, для данного алгоритма можно выделить семь независимых характеризующих его параметров:

1. совокупность возможных исходных данных;

2. совокупность возможных результатов;

3. совокупность возможных промежуточных результатов;

4. правило начала;

5. правило непосредственной переработки;

6. правило окончания;

7. правило извлечения результата;

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

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

Алгоритмические (формальные математические) модели.

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

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

Так, понятие машины Тьюринга как FS¹следующим образом может быть использовано для уточнения общего представления об алгоритме в данном алфавите, еслиТьюринговским алгоритмом в алфавите Аназывается всякий алгоритмUследующего вида:

• фиксируется некоторая машина Тьюринга в алфавите А, то есть <A,Q,R>, здесьQ– множество внутренних состояний машины, аR– правило перехода из одной конфигурации машины к другой);

• задается - слово, принимаемое в качестве исходного данного дляU(A^*);

• строится исходная конфигурация машины a₀q₀a₀, гдеq₀ – начальное состояние машиныq₀Q,a₀ – пустой символ,a₀А;

• машина, отправляясь из a₀q₀a₀, заканчивает работу в заключительной конфигурации.

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

Замечания:

1. Доказать тезис Тьюринга нельзя, поскольку само понятие алгоритма (или эффективной процедуры) является неточным. Это не теорема и не постулат математической теории, а утверждение, которое связывает теорию с теми объектами, для описания которых она создана. По своему характеру тезис Тьюринга напоминает гипотезы физики об адекватности математических моделей физическим явлениям и процессам. Подтверждением правильности тезиса Тьюринга является математическая практика, а также эквивалентные тезисы и, в частности, тезис Черча для рекурсивных функций: «Всякая функция, вычислимая некоторым алгоритмом, частично-рекурсивная».

2. Из сопоставления двух вышеприведенных тезисов вытекает утверждение: «Функция вычислима машиной Тьюринга тогда и только тогда, когда она частично-рекурсивна». Это утверждение об эквивалентности двух алгоритмических моделей является (в отличие от тезисов) вполне точным математическим утверждением и, следовательно, доказуемо, то есть имеют место две теоремы:

Теорема 1:Всякая частично-рекурсивная функция вычислима на машине Тьюринга.

Теорема 2: Всякая функция, вычислимая на машине Тьюринга частично-рекурсивная.

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

4. Тезисы позволяют выявлять случаи невозможности алгоритмов, однако, не указывают в случае их существования пути построения удобного для практики алгоритма (Напоминание: «Теория алгоритмов не учит строить конкретные алгоритмы»).