-
Notifications
You must be signed in to change notification settings - Fork 0
Инф9. Алгоритмы. Рекурсивные функции. Машины Тьюринга.
Алгоритмы [x]
Алгоритм - это точно установленное предписание о выполнении в определённом порядке некоторой последовательности операций, однозначно ведущих к решению той или иной конкретной задачи.
Предписание алгоритма представляет собой конечный набор правил, который задаёт потенциально осуществимый вычислительный процесс, ведущий от варьирующих в определённых пределах исходных данных к получению результата, однозначно определяемого допустимыми исходными данными. Последнее подразумевает, что результат выполнения алгоритма напрямую зависит от исходных данных: то есть один и тот же алгоритм при разных исходных данных даст разные результаты; с другой стороны, если одному и тому же алгоритму передать несколько раз одни и те же данные, он должен столько же раз выдать один и тот же результат.
Простейшими примерами алгоритмов являются арифметические правила сложения, вычитания, умножения, деления и тому подобные.
Машины Тьюринга [x]
Тьюринг предложил понятия абстрактных вычислительных машин. Любой алгоритм может быть реализован на данных машинах, несмотря на кажущуюся примитивность их элементарных действий.
Устройство машины Тьюринга:
- память - бесконечная лента
- процессор - каретка и программа (конечное число команд)
В машине Тьюринга памятью является потенциально бесконечная лента, в каждой клетке которой записан символ из заранее заданного конечного алфавита. Более того, достаточно рассматривать ленту, каждая клетка которой содержит один бит информации, то есть либо пуста, либо содержит символ |.
Процессор машины Тьюринга состоит из головки (каретки), которая в любой момент обозревает одну клетку, и программы, состоящей из конечного числа команд, обычно нумеруемых натуральными числами. Каждая команда представляет собой условное действие, зависящее от символа, записанного в клетке.
Это действие имеет вид совокупности элементарных инструкций формы ab (L, R, S) i
, в которой присутствует лишь одна из букв L, R, S.
- L означает приказ сдвинуться на следующем такте на одну клетку влево,
- R — вправо,
- S — остаться на месте.
Элементарная инструкция означает следующее: если машина видит a, записать в клетку b, передвинуться в соответствии с командой и перейти к исполнению команды i. Такая элементарность действий машины стала результатом проведённого Тьюрингом методологического анализа элементарных действий человека по исполнению алгоритмов.
При модификации машин Тьюринга разделением входной и выходной ленты (со входной можно лишь читать, на выходную — лишь писать, причём после шага записи и чтения лента необратимо сдвигается на одну ячейку) получается важное понятие конечного автомата, моделирующее вычислительные машины без внешней памяти. Возможности конечных автоматов значительно меньше, в частности на них нельзя распознать простые числа.
Рекурсивная функция — это числовая функция f(n) числового аргумента, которая в своей записи содержит себя же.
Хвостовая рекурсия — частный случай рекурсии, при котором любой рекурсивный вызов является последней операцией перед возвратом из функции.
Хвостовую рекурсию можно заменить на итерацию.
Хвостовая рекурсия 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:
(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:
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.