Теория алгоритмов (стр. 2 из 3)
Структура МТ имеет следующий вид:
| S1 | S2 | … | Sk | … | Sm |
Q - ячейка хранит символ состояния, а Р - ячейка – символ сдвига. В них происходит задержка данных символов до начала следующего такта.
В качестве начальной информации на ленту можно записать любую конечную последовательность символов (входное слово) U внешнего алфавита. В начале работы алгоритма устройство управления находится в начальном состоянии, головка обозревает первый слева непустой символ входного слова U. Если после конечного числа тактов МТ останавливается, переходя в заключительное состояние, а на ленте оказывается информация B, то говорят, что машина применима к последовательности U и перерабатывает ее в последовательность B.
Если остановка и сигнал об остановке никогда не поступают, то говорят, что МТ не применима к последовательности U.
Рассмотрим функционирование МТ на примере сложения двух чисел, которые будем изображать в виде набора единиц.
Внешний алфавит будет состоять из символов: {1, +, Ù}, где Ù – пустой символ.
Внутренний алфавит будет состоять из четырех символов {q1, q2, q3, !}, где символ q1 означает начальное состояние, а ! – заключительное состояние.
Пусть на ленте записана начальная информация:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 1 | + | 1 |
МТ должна ее переработать в результирующую информацию:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 1 | 1 |
Абстрактная программа, реализующий операцию сложения, будет иметь вид:
1q1  →Ùq3П1q3→1q3П+q3→+q3П | Ùq3→1q2H +q2 →+q2Л1q2→1q2Л Ùq2 →Ùq1П +q1 →Ù!Н |
Начальное состояние УУ=q1, состояние ленты имеет вид:
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | 1 | + | 1 |
После первого шага состояние YY=q3, состояние ленты как на рис. | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | + | 1 |
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
| 1 | + | 1 | 1 |
После пятого шага YY перейдёт в состояние q2. Состояние ленты показано на рис.
После десятого шага YY в состоянии q1 (рис. )
| 1 | 2 | 3 | 4 | 5 | 6 | 7 |
 1 | + | 1 | 1 |
Последовательность команд, реализующих операцию сложения, удобно задать таблицей, которую называют функциональной схемой алгоритма.
| q1 | q2 | q3 | |
| 1 | Ùq3П | 1q2Л | 1q3П |
| Ù | Ùq1П | Ùq1П | 1q2H |
| + | Ù!Н | +q2Л | +q3П |
Основная гипотеза теории алгоритмов (тезис Чёрча)
Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга.
Обоснование гипотезы.
Речь не идет о доказательстве гипотезы, так как она содержит не формализованные математические понятия.
Уверенность в справедливости гипотезы основана, главным образом, на опыте. Все известные к настоящему времени алгоритмы могут быть заданы посредством тьюринговых функциональных схем. Кроме того, внутри самой теории алгоритмов основная гипотеза не применяется, то есть при доказательстве теорем этой теории ссылок на основную гипотезу не делается.
Машина Тьюринга крайне примитивна. Но примитивность ее не в том, что она использует ленту и механическое движение головки, а то, что ее набор операций с памятью очень прост (запись и чтение символов) и что доступ к памяти в ней происходит не по адресу, а путем последовательного перемещения вдоль ленты. Поэтому выполнение на ней даже таких простых функций как сложение и умножение требует много шагов. Машина Тьюринга была придумана не для того, чтобы производить на ней реальные вычисления, а чтобы показать, что сколь угодно сложный алгоритм можно построить из очень простых операций, причем сами операции и переход от одной операции к другой выполняются автоматически.
Универсальная машина Тьюринга
Универсальная машина позволяет решить любую задачу, если наряду с исходными данными в неё записать алгоритм. Как и любая машина Тьюринга, универсальная машина должна иметь конечные внешний и внутренний алфавиты, в то же время она должна иметь возможность принимать в качестве внешнего алфавита любые алфавиты. Это достигается за счёт кодирования внешнего алфавита в алфавите универсальной машины Тьюринга.
Требования к кодированию:
1. различным буквам должны сопоставляться различные кодовые группы, и одна и та же буква везде заменяется одной и той же кодовой группой;
2. Строка текста должна однозначным образом разбиваться на кодовые группы.
Сложность универсальной машины Тьюринга определяется произведением числа символов её внешнего алфавита на число состояний усторйства управления.
Теорема Триттера определяет, что минимальная универсальная машина Тьюринга имеет 4 символа во внешнем алфавите и её УУ имеет 6 состояний.
МЕPЫ СЛОЖНОСТИ АЛГОPИТМОВ
Оценка алгоритма
Оценка алгоритма бывает нужной в том случае, когда при решении некоторой задачи есть несколько разных алгоритмов, и стоит задача выбора одного из них для реализации. Даже если задача решается единственным алгоритмом, бывает нужно оценить сложность его реализации и его работы (объём памяти, время решения).
Под пространственной эффективностью понимают объём памяти, требуемой для выполнения программы.
Временная эффективность программы определяется временем, необходимым для ее выполнения. При этом необходимо учитывать следующие моменты.
Во-первых, время работы программы может ограничиваться ее назначением. Если эта программа реального времени, например, бронирования авиабилетов, то время обработки задания не должно превышать нескольких минут. Если эта программа автоматического управления каким-либо устройством (например, управлением самолёта), то она должна «успевать» отрабатывать поступающую информацию и своевременно выдавать управляющие воздействия.
Во-вторых, бывает важно знать, как изменяется время работы программы при увеличении размерности задачи. Это позволит оценить объем исходных данных, которые могут быть обработаны на компьютере за приемлемое время.
Реальное время работы программы на компьютере зависит не только от выбранного алгоритма. В значительной степени оно определяется типом ЭВМ, структурой представления данных, программной реализацией.
Самым простым способом оценить алгоритм – сопоставить ему число элементарных операций в описании. При реализации это может быть число команд в программе или объём памяти, которую занимает программа. В этом случае оценка d алгоритма A есть некоторое число k: d(A) = k.
Более интересной может быть оценка пары: алгоритма A и конкретной задачи a, которая им решается. Например, оценкой может быть объем памяти под программу, исходные и промежуточные данные, необходимые для решения данной задачи a, или время для решения данной задачи с помощью алгоритма A. В любом случае это будет число d(A(a)) = k(a).
Свойство массовости алгоритма предполагает, что алгоритм будет использоваться для решения класса A подобных задач, с разными исходными данными. Поэтому более сложной оценкой будет оценка как функция свойства задачи. Cопоставим каждой задаче из класса задач, решаемым алгоритмом, некоторый вектор числовых параметров задачи N = (n1, n2, …, nt). В этом случае оценка d(A(A)) = k(N), и это уже будет функция от параметров задачи.
Пример. Необходимо ценить алгоритм Прима – алгоритм выделения минимального остова. В первом случае мы рассматриваем число операторов в описании программы, реализующий алгоритм – число сравнений, условных переходов и т.д. Во втором случае анализируется работа алгоритма (программы) выделения остова некоторого заданного графа и определяется необходимый объём памяти. В последнем случае графу припишем параметры – число вершин в графе и число его рёбер, и сопоставим решению задачи функцию от этих параметров.
Во многих задачах возможно свести вектор задачи к одному параметру. Так, для графа возможно характеризовать его числом вершин, учитывая, что число ребер в нём коррелированно с числом вершин. Для задач, связанных с булевыми функциями, параметром может быть число аргументов функции.
Будем рассматривать только такие задачи. В этом случае оценкой алгоритма будет функция от одного параметра. Временная сложность алгоритма отражает требующиеся для его работы затраты времени Эта функция вставит каждой входной длине n в соответствие максимальное ( по всем индивидуальным задачам длины n) время, затрачиваемое алгоритмом на решение индивидуальных задач этой длины.
Пример. Пусть функция оценки имеет вид как на рис.1. Необходимо решать задачи с параметром n, лежащим в пределах от 5 до 15. В этом случае необходимо выбрать для реализации алгоритм A1. Если параметр меняется от 20 до 30, лучше использовать алгоритм A2. Если параметр меняется в пределах от 10 до 35, то возможно или выбрать любой из данных алгоритмов, или построить новый алгоритм, который, например, проверяет каждый раз значение параметра и выбирает соответствующий алгоритм.