Свойства и параметры алгоритма:

Из неформального определения понятия «алгоритм» следуют его характеристические свойства:

• дискретность (каждый конструктивный объект получается из предыдущих по определенному правилу конструктивного процесса)

• направленность(все конструктивные объекты, как множества, упорядочены)

• детерминированность (однозначность выбора правил построения конструктивных объектов)

• Элементарность шагов (отсутствует необходимость уточнения правил конструктивного процесса)

• массовость (инвариантность относительно входных данных; уточнения понятия решения задачи в общем виде)

• результативность (получение требуемого конструктивного объекта по окончанию конструктивного процесса)

Очевидно, что характеристикой алгоритма является совокупность тех его свойств, которые определяют его возможности: быстродействие, производительность и т.д.

Замечание:

1. Алгоритм S_f не применим к исходному данному, если конструктивный процесс не заканчивается или заканчивается безрезультатно

2. Следует различать:

• Описание алгоритма как инструкции (программы),

• Система реализации алгоритма,

• Процесс реализации алгоритма (конструктивный процесс),

• Сходимость процесса реализации алгоритма (результативная остановка после конечного числа шагов алгоритма),

• Строение алгоритмического процесса (наличием или отсутствием промежуточных результатов).

В свете изложенного 7 параметров однозначно характеризуют данный алгоритм:

• совокупность возможных исходных данных,

• совокупность возможных результатов,

• совокупность возможных промежуточных результатов,

• правило начала,

• правила конструктивного процесса.

• правило окончания.

• правило извлечения результата.

Основная гипотеза теории алгоритмов.

Любая практическая задача, приводящая к необходимости создания эффективного вычислительного метода (алгоритма), может быть поставлена в точных математических терминах.

Эта парадигма (гипотеза, принцип) применительно к уточнению понятия алгоритм, как абстрактной машины известно, в виде тезиса Тьюринга: «Для всякого алгоритма S_f в каком-либо алфавите может быть построен тьюриноговский алгоритм, дающий при одинаковых исходных данных, те же самые результаты, что и алгоритм S_f».

Принятие тезиса Тьюринга равносильно принятию тезиса Черча (для частично-рекурсивных функции) или принцип нормализации (для нормальных алгорифмов).

В настоящее время широко используется в теории алгоритмов тезис Черча-Тьюринга: «Любая теоретически разрешимая вычислительная задача может быть решена при помощи машины Тьюринга».

Формальные модели, уточнение понятия алгоритм.

Приведенное выше «наивное» (интуитивное) понятие алгоритма как первичное (исходное) понятие математики не допускает его определения в терминах более простых понятий. Возможные уточнения понятия алгоритма приводят, строго говоря, к известному сужению этого понятия. Каждое такое уточнение состоит в том, что для каждого из семи параметров алгоритма точно описывается некоторый класс, в пределах которого этот параметр может меняться.

Поскольку семь параметров однозначно определяют некоторый алгоритм, то выбор семи классов изменения этих параметров определяет некоторый класс алгоритма, то выбор семи классов изменения этих параметров определяет некоторый класс модели алгоритма, или алгоритмической системы (модели):

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

Эти алгоритмические модели, сводимые друг к другу, позволяют заменить неточные утверждения о существовании эффективных процедур (алгоритмов) точными утверждениями о существовании соответствующей алгоритмической системы (например, машины Тьюринга). С другой стороны, утверждения о невозможности построения алгоритмической системы для решения поставленной задачи следует истолковывать как утверждение о несуществовании алгоритма вообще.