Инф9. Алгоритмы. Рекурсивные функции. Машины Тьюринга.

Алгоритмы [x]

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

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

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

Машины Тьюринга [x]

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

Устройство машины Тьюринга:

• память - бесконечная лента
• процессор - каретка и программа (конечное число команд)

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

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

Это действие имеет вид совокупности элементарных инструкций формы ab (L, R, S) i, в которой присутствует лишь одна из букв L, R, S.

• L означает приказ сдвинуться на следующем такте на одну клетку влево,
• R — вправо,
• S — остаться на месте.

Элементарная инструкция означает следующее: если машина видит a, записать в клетку b, передвинуться в соответствии с командой и перейти к исполнению команды i. Такая элементарность действий машины стала результатом проведённого Тьюрингом методологического анализа элементарных действий человека по исполнению алгоритмов.

Модификация машин Тьюринга

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

Рекурсивные функции

Рекурсивная функция — это числовая функция f(n) числового аргумента, которая в своей записи содержит себя же.

Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции.

Хвостовую рекурсию можно заменить на итерацию.

Примеры C

Хвостовая рекурсия C:

int fact (int n, int acc) {
    return (n==0) ? acc : fact(n - 1, acc * n);
}
int factorial (int n) {
    return fact(n, 1);
}

Не хвостовая рекурсия C:

int factorial (int n) {
    return (n==0) ? 1 : n*factorial(n-1);
}

Примеры Lisp

Хвостовая рекурсия Lisp:

(defun factorial (n)
    (fact n 1))

(defun fact (n res)
    (cond
        ((= n 0) res)
        (T (fact (- n 1) (* res n)))))

Не хвостовая рекурсия Lisp:

(defun factorial (n)
    (cond
        ((= n 0) 1)
        (T (* n (factorial (- n 1))))))

Примеры Prolog

Хвостовая рекурсия prolog:

factorial(0, 1) :- !.
factorial(N, Res) :- factorial(N, 1, Res).
	
factorial(1, Res, Res) :- !.
factorial(N, Cur, Res) :- 
	NewN = N - 1,
	NewMult = Cur * N,
	factorial(NewN, NewMult, Res).

Не хвостовая рекурсия prolog:

factorial(0, 1) :- !.
factorial(N, Res) :-
	NextN = N - 1,
	factorial(NextN, CurRes),
	Res = N * CurRes.