Что такое алгоритм?

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

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

Начиная с тридцатых годов ХХ века, был предпринят ряд исследований для формализации понятия алгоритма. Перечислим некоторые из предложенных разными авторами в разное время формальных моделей: машины Тьюринга-Поста, частично-рекурсивные функции (Гедель, Клини), ?-исчисление (Черч, Клини), итеративные автоматы Неймана, нормальные алгорифмы Маркова, счетчиковые автоматы Минского, автоматы на графах Колмогорова-Барздиня и др. Заложенные в них идеи в значительной степени повлияли затем на архитектуру и языки программирования реальных компьютеров (например, на базе ?-исчисления построен широко применяемый в задачах искусственного интеллекта язык ЛИСП, а из нормальных алгорифмов Маркова произошел хорошо подходящий для текстовой обработки язык РЕФАЛ). Каждый из многочисленных языков программирования также задает некоторую формальную модель алгоритмов. Мы вначале рассмотрим один из простейших таких языков - простые структурированные программы.
А затем сравним их с двумя другими моделями алгоритмов: описаниями частично рекурсивных функций и машинами Тьюринга.

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

Напомним, что через N обозначается множество натуральных чисел, т.е. N={0,1,2,…}. Для частичной n- местной арифметической функции f: Nn

N через ?f обозначим область ее определения. Чтобы указать, что f не определена на некотором наборе чисел a1,…, an будем писать f(a1,…, an)=?, а если f на этом наборе определена, то будем писать f(a1,…, an) < ?. Таким образом, f ={ (a1,…, an) | f(a1,…, an) < ? }.

Структурированные программы

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

Определим вначале синтаксис структурированных программ. Зафиксируем для этого некоторое счетное множество имен переменных Var, которые будут использоваться в программах. Как обычно, будем считать, что оно включает имена x, x1,x2,…, y, y1,..., z,z1,... и т.п. В последующих определениях x, y, z - это произвольные переменные из Var.

Определение 7.1. Оператор присваивания. Присваивание - это выражение одного из следующих трех видов:

x := x+1 x := 0 x := y.

Определение 7.2. Условия. Условие - это выражение одного из двух видов:

а) x = y или б) x < y.

Структурированные программы определяются индуктивно.

Определение 7.3.Структурированные программы.

Каждое присваивание - это структурированная программа.Если ?1 и ?2 - структурированные программы, то и ?= ?1 ; ?2 - это структурированная программа.

Если ?1 и ?2 - структурированные программы, а ? - это условие, то

является структурированной программой.

Если ?1 - структурированная программа, а ? - это условие, то

все является структурированной программой.

Других структурированных программ нет.

Конструкция в п. (б) называется последовательным применением или композицией программ ?1 и ?2, конструкция в п. (в) называется условным оператором; конструкция в п. (г) - это оператор цикла, ? - условие цикла, а ?1 - тело цикла.

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

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

Определение 7.4. Состояние - это отображение ? из множества переменных Var во множество N.
Для x

Var через ?(x) обозначим значение переменной x в состоянии ?. Через S обозначим множество всех состояний.

Разумеется, при рассмотрении конкретной программы ? нас будут интересовать значения переменных из Var?.

Определение 7.5. Операционная семантика программы ? - это отбражение (вообще говоря, частичное) типа S S, которое программа ? индуцирует на множестве всех состояний. Через ?(?) обозначим состояние - результат применения программы ? к состоянию ?. Оно определяется индукцией по построению программы.

( x := x+1)(?) = ?1, где ?1(y)=?(y) при y x, и ?1(x)=?(x)+1.( x := 0)(?) = ?1, где ?1(y)=?(y) при y x, и ?1(x)=0.( x := y)(?) = ?1, где ?1(z)=?(z) при z x, и ?1(x)=?(y)Пусть ?=?1;?2. Тогда ?(?)=(?1;?2)(?)=?2(?1(?)), при этом, если ?1(?)=? или ?1=?1(?) и ?2(?1)=?, то и ?(?)=?.

Пусть ?= если x = y то ?1 иначе ?2 конец. Тогда





Пусть ?= если x < y то ?1 иначе ?2 конец. Тогда







Пусть ?= пока x = y делай ?1 все. Тогда при ?(x) ?(y) ?(?)= ?, а при ?(x) = ?(y) ?(?) - это первое такое состояние ?m в последовательности состояний ?0=?, ?1=?(?0),…, ?i+1=?(?i),…, что при i m все состояния ?i определены, при i <m имеет место ?i(x) = ?i(y), и ?m(x) ?m(y). Семантику для цикла с условием x < y определите самостоятельно (см. задачу 7.1).

Пусть ? - программа, Var? - множество ее переменных. Выделим среди эти переменных некоторое подмножество входных

переменных x1,…, xn и одну результирующую (выходную) переменную y (она может быть одной из входных). Переменные из Var? , не являющиеся входными, будем называть вспомогательными.

Из определений следует, что при

Задача 7.1.
Определите (по аналогии с п. (ж)) определения 7.5 семантику для программ вида
?= пока x < y делай ?1 все.
Задача 7.2.Построить структурированные программы, вычисляющие в z следующие функции, и доказать их корректность:
f{?}(x,y)= x*y; ffact(x)= x!; f-1(x)= x 1, где 0 1 = 0 и (x+1) 1 = x; f-(x,y)= x y, где x y = x-y, если x y и x y=0, если x < y; fsqr(x)= [sqrt x]; fexp(x)= 2x; flog(x)= [log2x]; f/(x,y)= [x/y].
Задача 7.3.
Пусть ? - структурированная программа и |Var?| = m. Из определений следует, что при различной фиксации входных переменных и выходной переменной программа может вычислять различные функции.
Каково максимальное число функций от n m переменных, которое может вычислять ?? Сколько всего разных функций может вычислить ??Постройте программу ?(m,n), которая вычисляет максимальное число различных функций от n m переменных.Постройте программу ?(m) с |Var?| = m, которая для каждого n m вычисляет максимальное число различных функций от n переменных.
Задача 7.4.Построить структурированные программы, вычисляющие в z следующие функции:









Задача 7.5.
Пусть структурированная программа ? вычисляет в переменной y некоторую всюду определенную взаимно однозначную функцию f(x), область значений которой совпадает с множеством всех натуральных чисел N. Пусть Var?={x, y, z1,… , zm}. Постройте структурированную программу, которая вычисляет обратную функцию f-1(x) = { z | f(z)=x}.
Задача 7.6. Пусть F(x) задана соотношениями F(0)=1, F(1)=1, F(x+2)= F(x)+F(x+1) (элементы последовательности F(x) называются числами Фибоначчи). Постройте структурированную программу, которая вычисляет функцию F(x).

---

---