 |
Основные требования к алгоритмам.
|
|
|
|
1. Каждый алгоритм имеет дело с данными – входными, промежуточными, выходными. Для того, чтобы уточнить понятие данных, фиксируется конечный алфавит исходных символов (цифры, буквы и т.п.) и указываются правила построения алгоритмических объектов. Типичным используемым средством является индуктивное построение. Например, определение идентификатора в АЛГОЛЕ: идентификатор – это либо буква, либо идентификатор, к которому приписана справа либо буква, либо цифра. Слова конечной длины в конечных алфавитах - наиболее обычный тип алгоритмических данных, а число символов в слове - естественная мера объема данных. Другой случай алгоритмических объектов - формулы. Примером могут служить формулы алгебры предикатов и алгебры высказываний. В этом случае не каждое слово в алфавите будет формулой.
2. Алгоритм для размещения данных требует памяти. Память обычно считается однородной и дискретной, т.е. она состоит из одинаковых ячеек, причем каждая ячейка может содержать один символ данных, что позволяет согласовать единицы измерения объема данных и памяти.
3. Алгоритм состоит из отдельных элементарных шаго в, причем множество различных шагов, из которых составлен алгоритм, конечно. Типичный пример множества элементарных шагов – система команд ЭВМ.
4. Последовательность шагов алгоритма детерминирована, т.е. после каждого шага указывается, какой шаг следует выполнять дальше, либо указывается, когда следует работу алгоритма считать законченной.
5. Алгоритм должен обладать результативностью, т.е. останавливаться после конечного числа шагов (зависящего от исходных данных) с выдачей результата. Данное свойство иногда называют сходимостью алгоритма.
|
|
|
6. Алгоритм предполагает наличие механизма реализации, который по описанию алгоритма порождает процесс вычисления на основе исходных данных. Предполагается, что описание алгоритма и механизм его реализации конечны.
Можно заметить аналогию с вычислительными машинами. Требование 1 соответствует цифровой природе ЭВМ, требование 2 - памяти ЭВМ, требование 3 – программе машины, требование 4 – ее логической природе, требования 5, 6 – вычислительному устройству и его возможностям.
Имеются также некоторые черты неформального понятия алгоритма, относительно которых не достигнуто окончательного соглашения. Эти черты сформулируем в виде вопросов и ответов.
· Следует ли фиксировать конечную границу для размера входных данных?
· Следует ли фиксировать конечную границу для числа элементарных шагов?
· Следует ли фиксировать конечную границу для размера памяти?
· Следует ли ограничить число шагов вычисления?
На все эти вопросы далее принимается ответ “НЕТ”, хотя возможны и другие варианты ответов, поскольку у физически существующих ЭВМ соответствующие размеры ограничены. Однако теория, изучающая алгоритмические вычисления, осуществимые в принципе, не должна считаться с такого рода ограничениями, поскольку они преодолимы по крайней мере в принципе (например, вообще говоря, любой фиксированный размер памяти всегда можно увеличить на одну ячейку).
Таким образом, уточнение понятия алгоритма связано с уточнением алфавита данных и формы их представления, памяти и размещения в ней данных, элементарных шагов алгоритма и механизма реализации алгоритма. Однако эти понятия сами нуждаются в уточнении. Ясно, что их словесные определения потребуют введения новых понятий, для которых в свою очередь, снова потребуются уточнения и т.д. Поэтому в теории алгоритмов принят другой подход, основанный на конкретной алгоритмической модели, в которой все сформулированные требования выполняются очевидным образом. При этом используемые алгоритмические модели универсальны, т.е. моделируют любые другие разумные алгоритмические модели, что позволяет снять возможное возражение против такого подхода: не приводит ли жесткая фиксация алгоритмической модели к потере общности формализации алгоритма? Поэтому данные алгоритмические модели отождествляются с формальным понятием алгоритма. В дальнейшем будут рассмотрены основные типы алгоритмических моделей, различающиеся исходными трактовками, что такое алгоритм.
|
|
|
Первый тип трактует алгоритм как некоторое детерминированное устройство, способное выполнять в каждый момент лишь строго фиксированное множество операций. Основной теоретической моделью такого типа является машина Тьюринга, предложенная им в 30-х годах и оказавшая существенное влияние на понимание логической природы разрабатываемых ЭВМ. Другой теоретической моделью данного типа является машина произвольного доступа (МПД) – введенная достаточно недавно (в 70-х годах) с целью моделирования реальных вычислительных машин и получения оценок сложности вычислений.
Второй тип связывает понятие алгоритма с традиционным представлением – процедурами вычисления значений числовых функций. Основной теоретической моделью этого типа являются рекурсивные функции – исторически первая формализация понятия алгоритма.
Третий тип алгоритмических моделей – это преобразования слов в произвольных алфавитах, в которых операциями являются замены кусков слов другим словом. Основной теоретической моделью этого типа являются нормальные алгоритмы Маркова.
Машина Тьюринга
Определение 3. Машина Тьюринга - это математическая модель идеализированного вычислительного устройства. Она имеет 1) ленту, разбитую на конечное число ячеек, в каждой ячейке ленты в определенный момент времени записан один из символов а0,а1,а2,...,аN. Совокупность этих символов называется входным алфавитом; 2) конечное управление, которое может находиться в каждый момент времени в каком-то одном состоянии q0, q1, q2,...,qM; 3) управляющую головку, которая может перемещаться вдоль ленты, считывать или записывать символы.
|
|
|
Концепция такого рода машины сложилась в середине 30-х гг. 20 в. у А. М. Тьюринга в результате произведённого им анализа действий человека, выполняющего в соответствии с заранее разработанным планом те или иные вычисления, то есть последовательные преобразования знаковых комплексов.
Машину Тьюринга удобно представлять в виде некоторого автоматически действующего устройства, способного находиться в конечном числе внутренних состояний и снабженного бесконечной внешней памятью — лентой. Среди состояний имеются два выделенных — начальное и заключительное. Лента разделена на клетки (ячейки) и не ограничена влево и вправо. В каждой клетке ленты может быть записан любой из символов, входящих в некоторый заранее заданный перечень (ради единообразия считают, что в пустой клетке записана «пустая буква»). В каждый момент времени Машина Тьюринга находится в одном из своих состояний и, рассматривая (посредством специального устройства) одну из клеток своей ленты, воспринимает записанный в ней символ. Если в текущий момент времени Машина Тьюринга находится в не заключительном состоянии, то в следующий за ним момент: 1) она переходит в новое состояние, быть может совпадающее со старым, или заключительное; 2) в рассматриваемой клетке старый символ заменяется новым, быть может пустым или совпадающим со старым; 3) лента машины сдвигается на одну клетку влево или вправо либо остаётся на месте. Этот шаг Машина Тьюринга вполне определяется её текущим состоянием и текущим воспринимаемым символом. Таблица, содержащая полное перечисление возможных шагов данной Машины Тьюринга, называется программой этой машины.
Текущее полное описание Машины Тьюринга. даётся её конфигурацией, которая состоит из указания для данного момента следующей информации: 1) конкретного заполнения клеток ленты символами, 2) клетки, находящейся в поле зрения машины, 3) состояния, в котором машина находится.
Если у данной Машины Тьюринга взять в качестве исходной какую-либо конфигурацию с не заключительным состоянием, то работа этой машины будет заключаться в последовательном, шаг за шагом, преобразовании исходной конфигурации в соответствии с программой машины до тех пор, пока не будет достигнута конфигурация с заключительным состоянием. Эта последняя, если она существует, и считается результатом работы данной Машины Тьюринга над исходной конфигурацией.
|
|
|
Имеются серьёзные основания считать, что понятие Машина Тьюринга доставляет адекватное уточнение общего представления об алгоритме, то есть что всякий алгоритм может быть промоделирован подходящей Машиной Тьюринга. (тезис Тьюринга). Теория Машин Тьюринга даёт удобный рабочий аппарат для многих исследований, требующих точного понятия алгоритма. В частности, ввиду естественности совершаемых ими шагов, Машины Тьюринга стали объектом пристального внимания в теории сложности алгоритмических вычислений. В ходе развития теории Машин Тьюринга рассматривались различные их обобщения: например, Машины Тьюринга с более общим типом лент, с несколькими лентами, а также недетерминированные.
Формальное определение базовой модели машины Тьюринга:
T= (K,S, Г, d, q0, F);
K - конечное множество внутренних состояний;
S - входной алфавит;
Г - ленточный алфавит: S: Г-{$}, $-пробел;
d - команды, частичное отображение
d: KхГ->Kx (Г-{$})x{L,R}, где L,R -движение влево и вправо головки;
q0- начальное состояние, с него машина начинает обработку, q0cK;
F - множество конечных состояний, в которых машина переходит в представляющее состояние.
Структура машины Тьюринга
1. Машина Тьюринга (рис.1) имеет конечное число знаков si, образующих внешний алфави т, в котором кодируются сведения, подаваемые в МТ, а также вырабатываемые в ней. Среди знаков имеется пустой знак (s1), посылка которого в какую-либо ячейку стирает находившийся в ней знак и оставляет ее пустой 
.
Рисунок 1. Структура машины Тьюринга
В зависимости от поданной начальной информации (содержащихся на ленте внешней памяти знаков) возможны два случая:
o после конечного числа тактов машина останавливается (имея информацию β), подавая сигнал об остановке. В этом случае МТ применима к информации 
и перерабатывает ее в информацию β;
o остановка никогда не наступает. В этом случае МТ не применима к начальной информации .
2. В каждый момент обозревается лишь одна ячейка ленты (памяти). Переход может осуществляться лишь к соседней ячейке (R – вправо, L–влево, N– нет перехода (остаться)). Переход к произвольной ячейке производится путем последовательного перебора всех ячеек, разделяющих текущую и необходимую ячейки. На каждом отдельном такте t команда предписывает только замену единственного знака si, хранящегося в обозреваемой ячейке, каким-либо другим знаком sj.
|
|
|
3. Логический блок МТ имеет конечное число состояний {qi} i=1..m.
Знаки R, L, N, q1,..,qmобразуют внутренний алфавит машины.
Переработанный знак sj, записываемый в просматриваемую ячейку, состояние, которое примет машина Тьюринга в следующем такте q(t+1) и выполняемая в данном такте операция перехода к следующей ячейке P(t+1) являются функцией анализируемого в данном такте символа и текущего состояния машины si и q(t):
si(t+1)=f1(si,q(t));
q(t+1)=f2(si,q(t));
P(t+1)=f3(si,q(t)).
Программа для МТ определяется тройкой {si, P, q}t.
Пример записи программы вычисления логической функции "неравнозначность" для машины Тьюринга представлен ниже.
| Символ (si) | Состояние | |||
| q1 | q2 | q3 | q4 | |
| 0, R, q1 | 0, N, q4 | 1, N, q4 | 0, N, q4 | |
| 1, R, q3 | 1, N, q4 | 0, N, q4 | 1, N, q4 |
Перед началом работы машина Тьюринга находится в состоянии q1 считывания первого операнда.
Данная МТ применима к исходной информации. Останов – состояние q4. Значение si в ячейке y не меняется (сохраняется результат).
Если программа для МТ будет определена таблицей переходов
| Символ (si) | Состояние | |||
| q1 | q2 | q3 | q4 | |
| 0, R, q2 | 0, N, q4 | 1, N, q4 | 1, N, q4 | |
| 1, R, q3 | 1, N, q4 | 0, N, q4 | 0, N, q4 |
то данная МТ будет не применима к исходной информации, поскольку в состоянии q4 значение si в ячейке y постоянно меняется на противоположное.
Рекурсивные функции
Теория рекурсивных функций, являясь частью теории алгоритмов представляет собой разветвленную математическую дисциплину с собственной проблематикой и с приложениями в других разделах математики. Понятие «рекурсивной функции» может быть положено в основу конструктивного определения исходных математических понятий. Понятие примитивно рекурсивной функции лежит в основе первоначального доказательства знаменитой теоремы Гёделя о неполноте формальной арифметики, а понятие «рекурсивной функции» в его полном объёме было использовано С. К. Клини для интерпретации интуиционистской арифметики (исследование это составило целую эпоху в области семантики).Аппарат теории рекурсивных функций используется также в теории вычислительных машин и программирования.
Рекурсивные функции были введены в 30-х гг. 20 в. С. К. Клини, в свою очередь основывавшимся на исследованиях К. Гёделя,Ж. Эрбрана и др. математиков. Исследования показали, что все известные уточнения общего понятия алгоритма, в том числе рекурсивные функции, взаимно моделируют друг друга и, следовательно, ведут к одному и тому же понятию вычислимой функции.
Определение 4 Рекурсивные функции (от позднелатинского recursio — возвращение), название, закрепившееся за одним из наиболее распространённых вариантов уточнения общего понятия арифметического алгоритма, т.е. такого алгоритма, допустимые исходные данные которого представляют собой системы натуральных чисел, а возможные результаты применения являются натуральными числами.
Каждая рекурсивная функция задаётся конечной системой равенств точно охарактеризованного типа в том смысле, что её значения вычисляются с помощью этой системы равенств по точно формулируемым правилам, причём таким образом, что в итоге для вычисления значений заданной рекурсивной функции получается алгоритм определённого типа.
Арифметические функции, для вычисления значений которых имеются какие-либо алгоритмы, принято называть вычислимыми. Вычислимые функции играют в математике важную роль. Вместе с тем, если понятию алгоритма здесь не будет придан точный смысл, то и само понятие вычислимой функции окажется несколько расплывчатым. Рекурсивные функции уже в силу самого характера своего определения оказываются вычислимыми. В известном смысле верно и обратное: имеются серьёзные основания считать, что математическое по своему характеру понятие рекурсивности является точным эквивалентом несколько расплывчатого понятия вычислимости. Предложение считать понятие вычислимости совпадающим по объёму с понятием рекурсивности известно в теории рекурсивных функций под названием тезиса Чёрча по имени американского математика А. Чёрча, впервые (в 30-х гг. 20 в.) сформулировавшего и обосновавшего это предложение. Принятие тезиса Чёрча позволяет придать понятию вычислимой арифметической функции точный математический смысл и подвергнуть это понятие изучению при помощи точных методов.
Рекурсивные функции являются частичными функциями, т. е. функциями, не обязательно всюду определёнными. Чтобы подчеркнуть это обстоятельство, часто в качестве синонима используют термин «частично рекурсивные функции». Рекурсивные функции, определённые при любых значениях аргументов, называют общерекурсивными функциями.
Определению рекурсивной функции может быть придана следующая форма. Фиксируется небольшое число чрезвычайно простых исходных функций, вычислимых в упомянутом выше интуитивном смысле (функция, тождественно равная нулю, функция прибавления единицы и функции, выделяющие из системы натуральных чисел член с данным номером); фиксируется небольшое число операций над функциями, переводящих вычислимые функции снова в вычислимые (операторы подстановки, примитивной рекурсии и минимизации). Тогда рекурсивные функции определяются как такие функции, которые можно получить из исходных в результате конечного числа применений упомянутых выше операций.
Оператор подстановки сопоставляет функции f от n переменных и функциям g 1,..., gn от m переменных функцию h от m переменных такую, что для любых натуральных чисел x 1,.., x m
h (x 1,.., x m) @ f (g 1(x 1,.., x m),..., g m(x 1,.., x m))
(здесь и ниже условное равенство @ означает, что оба выражения, связываемые им, осмыслены одновременно и в случае осмысленности имеют одно и то же значение).
Оператор примитивной рекурсии сопоставляет функциям f от n переменных и g от n + 2 переменных функцию h от n + 1 переменных такую, что для любых натуральных чисел x 1,...., x n, y
h (x 1,.., x n,0) @ f (x 1,.., x n),
h (x 1,.., x n, y + 1) @ g (x 1,.., x n, y, h (x 1,.., x n, y)).
Оператор минимизации сопоставляет функции f от n переменных функцию h от n переменных такую, что для любых натуральных чисел x 1,.., x n
h (x 1,.., x n) @ f (x 1,.., x n-1, y)
где у таково, что f (x 1,.., x n-1, y -1) определены и отличны от x n, а f (x 1,.., x n, y)определена и равна x n, если же у с указанными свойствами не существует, то значение h (x 1,.., x n)считается не определённым.
Важную роль в теории рекурсивных функций играют т. н. примитивно рекурсивные функции — рекурсивные функции, получающиеся из исходных функций в результате конечного числа применений одних лишь операторов подстановки и примитивной рекурсии. Они образуют собственную часть класса общерекурсивных функций. В силу известной теоремы Клини о нормальной форме рекурсивные функции могут быть указаны такие конкретные примитивно рекурсивные функции U от одной переменной и T nот n + 2 переменных, что для любой рекурсивной функции j от n переменных и для любых натуральных чисел x 1,..., x n имеет место равенство j(x 1,..., x n) @ U (y), где у есть наименьшее из чисел z таких, что T n(j, x 1,..., x n, z) = 0 (здесь j представляет собой т. н. геделев номер функции j — число, которое эффективно строится по системе равенств, задающей функцию j). Из этой теоремы, в частности, вытекает, что для Рекурсивной функции от п переменных может быть построена универсальная рекурсивная функция от n +1 переменных, т. е. такая рекурсивная функция Фn, что для любой рекурсивной функции j от n переменных и для любых натуральных чисел x 1,..., x n имеет место условное равенство
j(x 1,..., x n) @ Фn(
, x 1,..., x n).
Это — один из центральных результатов общей теории рекурсивных функций.
Контрольные вопросы:
|
|
|
