Книги и конспекты / Шпоры / 27

27. Алгоритм, его формальные признаки, виды алгоритмов, эффективность алгоритмов. Машина Тьюринга (МТ), ее устройство. Детерминированная МТ.

Алгоритм – точный набор инструкций, для определенного результата. Формальные признаки алгоритмов (св-ва алгоритмов):

1.Дискретность ( последовательность выполнения действий, для решения задачи, за определенное количество шагов, в конечный период времени)

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

3.Понятность (определенные команды)

4.Завершенность (конечность) (За конечное число шагов алгоритм выдаст искомый результат и прекратит работу)

5.Массовость (алгоритм применим для любых исходных данных определенного типа)

6.Результативность (в завершении алгоритма получается результат)

Виды алгоритмов:

1.прикладные (для определенных задач)

2.рекурсивные (вызывают сами себя)

3.параллельные (в один момент решают разные части программы)

Эффективность алгоритмов

-минимизация времени работы алгоритма, сложности программы, размера

Машина Тьюринга.

МТ – это абстрактный исполнитель. Предложена Аланом Тьюрингом для формализации понятия алгоритма. Согласно тезису Тьюринга, любой алгоритм может быть записан в виде программы для МТ.

Устройство МТ.

МТ состоит из каретки (К) (считывающей и записывающей головки) и бесконечной ленты, разбитой на ячейки.

Каждая ячейка ленты может содержать символ из некоторого алфавита A={a0,a1,…,aN}. Любой алфавит содержит символ «пробел», который обозначается как a0 . При вводе команд пробел заменяется знаком подчеркивания «_».

МТ управляется таблицей. Строки в таблице соответствуют символам выбранного алфавита A, а столбцы —

состояниям автомата Q={q0,q1,…,qM}. В начале работы МТ находится в состоянии q1. Состояние q0 — это конечное состояние: попав в него, МТ заканчивает работу.

Вкаждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей:

1.символ из алфавита A;

2.направление перемещения: > (вправо), < (влево) или . (на месте);

3.новое состояние автомата

Например: Задача: Увеличить число, записанное в двоичной системе счисления на 1. Каретка стоит над числом. Решение:

Входной алфавит А = {0,1} Лента:

К

1 1 0 1

Таблица МТ:

Детерминированная МТ.

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