22
h 1 L h 1 y x | h x L .
|
y L |
· · · · · · · · · · · · · · · · · · · · · · · · |
Пример · · · · · · · · · · · · · · · · · · · · · · · |
Пусть h – гомоморфизм h(0) = a и h(1) = a, тогда h–1(a) = {0, 1};
h–1(a*) = {0, 1}*.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
1.5 АЛГОРИТМЫ
Алгоритм – центральное понятие в компиляции и программировании,
поэтому важно его формальное определение.
1.5.1 ЧАСТИЧНЫЕ АЛГОРИТМЫ
Можно дать следующее неформальное определение.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Частичный алгоритм состоит из конечного числа ко-
манд, каждая из которых может выполняться механически за фиксированное время и с фиксированными затратами.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Для того чтобы быть точным, необходимо определить термин «коман-
да». Кроме того, частичный алгоритм имеет любое число входов и выходов.
Эти переменные тоже требуют определения.
· · · · · · · · · · · · · · · · · · · · · · · · |
|
Пример · · · · · · · · · · · · · · · · · · · · · · · |
|
|
|
Алгоритм Евклида (поиск наибольшего общего делителя двух чисел):
Вход: p и q – положительные целые числа.
Выход: g – наибольший общий делитель p и q.
23
Метод:
Шаг 1. Найти r – остаток от деления p и q.
Шаг 2. Если r = 0, положить g = q и остановиться. В противном случае положить p = q, затем q = r и перейти к шагу 1.
Данный алгоритм состоит из конечного множества команд и имеет вход и выход. Но можно ли команду выполнять механически с фиксирован-
ными затратами времени и памяти?
Строго говоря, нет. Величины p и q могут быть очень большими, и,
следовательно, затраты на деление будут пропорциональны p и q.
Можно заменить шаг 1 на последовательность шагов, которые вычис-
ляют остаток от деления p на q, причем количество ресурсов, необходимых для выполнения одного такого шага, фиксировано и не зависит от p и q.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Таким образом, мы допускаем, что шаг частичного алгоритма может сам быть частичным алгоритмом.
1.5.2 ВСЮДУ ОПРЕДЕЛЕННЫЕ АЛГОРИТМЫ
Частичный алгоритм останавливается на данном входе, если существу-
ет такое натуральное число t, что после выполнения t элементарных команд этого алгоритма либо не окажется ни одной команды этого алгоритма, кото-
рую нужно выполнять, либо последней выполненной командой будет «оста-
новиться». Частичный алгоритм, который останавливается на всех входах,
т.е. на всех значениях входных данных, называется всюду определенным ал-
горитмом либо просто алгоритмом.
· · · · · · · · · · · · · · · · · · · · · · · · |
|
Пример · · · · · · · · · · · · · · · · · · · · · · · |
|
|
|
Рассмотрим предыдущий частичный алгоритм: после шага 1 выполня-
ется шаг 2. После шага 2 либо выполняется шаг 1, либо следующий шаг не-
24
возможен, т.е. алгоритм остановлен. Можно доказать, что для каждого входа p и q алгоритм останавливается не более чем через 2q шагов, и, значит, этот частичный алгоритм является просто алгоритмом.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
· · · · · · · · · · · · · · · · · · · · · · · · |
|
Пример · · · · · · · · · · · · · · · · · · · · · · · |
|
|
|
Дан следующий алгоритм:
Шаг 1. Если x = 0, то перейти к шагу 1, в противном случае остановить-
ся.
Для x = 0 этот частичный алгоритм никогда не остановится.
·· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Сточки зрения рассматриваемого нами предмета нас будут интересо-
вать две проблемы:
–корректность алгоритмов;
–оценка их сложности.
При этом следует оценивать два критерия сложности:
–число выполненных элементарных механических операций как функция от величины входа (временная сложность);
–объем памяти, требующийся для хранения промежуточных резуль-
татов, возникающих в ходе вычисления, как функция от величины входа (емкостная сложность).
· · · · · · · · · · · · · · · · · · · · · · · · |
|
Пример · · · · · · · · · · · · · · · · · · · · · · · |
|
|
|
Для алгоритма Евклида число шагов для (p, q) – 2q.
Объем используемой памяти – 3 ячейки p, q, r.
Объем используемой памяти зависит от длины бинарного представле-
ния числа ~log2n, где n – наибольшее из чисел p, q.
25
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
1.5.3 РЕКУРСИВНЫЕ АЛГОРИТМЫ
Частичный алгоритм определяет некоторое отображение множества всех входов во множество выходов. Отображение, определяемое частичным алгоритмом, называется частично рекурсивной функцией либо рекурсивной функцией. Если алгоритм всюду определен, то отображение называется об-
щерекурсивной функцией. С помощью частичного алгоритма можно опреде-
лить и язык.
Возьмем алгоритм, которому можно предъявлять произвольную цепоч-
ку x. После некоторого вычисления алгоритм выдает «да», если цепочка при-
надлежит языку. Если x не принадлежит языку, алгоритм останавливается и выдает «нет». Такой алгоритм определяет язык L как множество входных це-
почек, для которых он выдает «да». Если мы определили язык с помощью всюду определенного алгоритма, то последний остановится на всех входах. 
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
Множество, определяемое частичным алгоритмом, назы-
вается рекурсивно перечисленным. Множество, определяемое всюду определенным алгоритмом, называется рекурсивным.
· · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · · ·
1.5.4 ЗАДАНИЕ АЛГОРИТМОВ
Мы занимались неформальным описанием алгоритмов. Можно дать строгие определения терминов, используя различные формализмы:
–машины Тьюринга;
–грамматики Хомского типа 0;
–алгоритмы Маркова;
–лямбда-исчисления;
–системы Поста;