Читайте также:
|
Несмотря на усилия исследователей, отсутствует одно исчерпывающе строгое определение понятия алгоритм, в теории алгоритмов были введены различные формальные определения алгоритма и удивительным научным результатом является доказательство эквивалентности этих формальных определений в смысле их равномощности.
Определение алгоритма дается на основе алгоритмической модели одного из перечисленных типов.
Тип 1. Алгоритм трактуется как некоторое детерминированное устройство, способное выполнять в каждый момент лишь строго фиксированное множество операций.
Основной теоретической моделью такого типа является машина Тьюринга, предложенная им в 30-х годах и оказавшая существенное влияние на понимание логической природы разрабатываемых ЭВМ. Другой теоретической моделью данного типа является машина произвольного доступа (МПД), введенная достаточно недавно (в 70-х годах) с целью моделирования реальных вычислительных машин и получения оценок сложности вычислений.
Определение 1. Алгоритм – формальное описание конечной последовательности точно определенных действий, которые приводят к решению поставленной задачи и переводят совокупность исходных данных в конечный результат, полностью определяемый этими данными.
Определение 2. Алгоритм – это система вычислений, выполненных по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи(А.Н. Колмогоров).
Тип 2. Понятие алгоритма связывается с процедурами вычисления значений числовых функций.
Основной теоретической моделью этого типа являются рекурсивные функции – исторически первая формализация понятия алгоритма.
Определение 3. Алгоритм – однозначно трактуемая процедура решения задачи. Процедура – конечная последовательность точно определенных шагов или операций, для выполнения каждой из которых для любых допустимых входных данных требуется конечное время и конечный объем машинной памяти.
Тип 3. Алгоритмическая модель – это преобразования слов в произвольных алфавитах, в которых операциями являются замены кусков слов другим словом.
Основной теоретической моделью этого типа являются нормальные алгоритмы Маркова.
Определение 4. Алгоритм – точное предписание, которое задает алгоритмический процесс, начинающийся с произвольного исходного данного (из некоторой совокупности возможных для данного алгоритма исходных данных) и направленный на получение полностью определенного этим исходным данным результата (А.А. Марков). Алгоритмический процесс – процесс последовательного преобразования конструктивных объектов (слов, чисел, пар слов, пар чисел, предложений и т.п.)., происходящий дискретными «шагами». Каждый шаг состоит в смене одного конструктивного объекта другим.
Поскольку алгоритмы могут применяться к произвольным объектам (числам, буквам, словам, графам, логическим выражениям и т.д.), в определении алгоритма используется специальный термин – «конструктивный объект», объединяющий в себе все эти возможные случаи.
Алгоритм Евклида для нахождения наибольшего общего делителя пары натуральных чисел (т, п).
Дата добавления: 2015-04-11; просмотров: 30 | Поможем написать вашу работу | Нарушение авторских прав |