38) Машина Поста – абстрактная вычислительная машина, предложенная Эмилем Леоном Постом, которая отличается от машины Тьюринга большей простотой. Принцип работы:

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на секции бесконечной в обе стороны ленты. Каждая секция ленты может быть либо пустой — 0, либо помеченной меткой 1. За один шаг каретка может сдвинуться на одну позицию влево или вправо, считать, поставить или стереть символ в том месте, где она стоит. Работа машины Поста определяется программой, состоящей из конечного числа строк. Всего команд шесть: → j сдвиг вправо перейти к j строке. ← j сдвиг влево, N. 1 J запись метки N. a(альфа)j удаление метки перейти к j строке. ?j1,j2 если в ячейке нет метки, то перейти к j1,если в ячейке есть место, то к j2 строке. !-остановка

Ограничим ленту с одной стороны и покажем, что машина Тьюринга с

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

а) рабочая область ленты ограничена двумя маркерами: неподвижным - слева и подвижным - справа;

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

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

Тьюринга нужно сдвинуть вплотную к левому маркеру.

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

39) Недетерминированная машина Тьюринга

Обобщение детерминированной машины Тьюринга, в которой, при каждом переходе, можно выполнять переход одновременно в несколько (константа) состояний — можно считать, что происходит «клонирование» машины (состояние, содержимое лент, положение головок).

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

Недетерминированная машина Тьюринга выдаст ответ 1, если существует хотя бы один путь развития вычисления, на котором выдается ответ 1, и 0 — в противном случае (таким образом, ответы «ДА» и «НЕТ» в случае недетерминированных вычислений несимметричны).

40)

41) Понятие сложности алгоритма( временной сложности). Порядок роста функций. Длина описания задачи.

Временная сложность— основной параметр, характеризующий алгоритм; определяется как число шагов, выполняемых алгоритмом в худшем случае, обычно рассматривается как функция размера задачи, представленной входными данными. Обычно под размером теоретико-графовой задачи понимается число вершин графа , число дуг или пара . Под шагом алгоритма понимается выполнение одной из команд некоторой гипотетической машины. Поскольку при таком определении шага сложность алгоритма зависит от конкретного вида машинных команд, во внимание принимается асимптотическая сложность, т.е. асимптотическая скорость увеличения числа шагов алгоритма, когда размерность задачи неограниченно растет. Ясно, что при двух произвольных "разумных" способах перевода алгоритма в последовательность машинных команд соответствующие сложности различаются не более чем на мультипликативную константу, а их скорость роста одинакова.

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

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

42)

1