Основные требования к алгоритмам

Введение.

Курс теория алгоритмов.

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

С алгоритмами или эффективными процедурами, однозначно приводящими к результату, уже приходилось сталкиваться в других математических дисциплинах. Методы умножения чисел и многочленов, метод исключения неизвестных при решении систем линейных уравнений, метод проверки функциональной полноты систем булевых функций - все это алгоритмы. До последнего времени термин “алгоритм” встречался в математике лишь в связи с построением конкретных алгоритмов, когда утверждение о существовании алгоритма для задач определенного типа сопровождалось его описанием. При таких обстоятельствах достаточно интуитивного представления об алгоритме и вопрос о точном его определении не возникает. Однако в ходе развития математики накапливались факты, которые коренным образом изменили ситуацию. Приведем один пример. Пусть p(x₁,…,x_n) - многочлен от переменных x₁,…,x_n с целыми коэффициентами. Тогда уравнение p(x₁,…,x_n)=0, для которого ищутся только целые решения, называется диофантовым. Знаменитая десятая проблема Гильберта, сформулированная им в 1900 году, состоит в том, чтобы установить, существует ли эффективная процедура, с помощью которой можно определить, имеет ли решение любое наперед заданное диофантово уравнение.

В 1970 году Ю.Матиясевич доказал, что такой процедуры не существует. Данный результат, а также многие другие факты, связанные с доказательством несуществования алгоритмического решения математических проблем, невозможны без точного понятия алгоритма.

В технику термин “алгоритм” пришел вместе с кибернетикой. При этом также возникла потребность точно определить, что значит эффективно заданная последовательность управляющих действий (сигналов). Использование ЭВМ послужило стимулом не только к уточнению понятия алгоритма и изучению алгоритмических моделей, но и к самостоятельному исследованию алгоритмов с целью их сравнения по рабочим характеристикам (числу действий, расходу памяти), а также оптимизации. Рассмотрим неформально, что именно в интуитивном понятии алгоритма нуждается в уточнении.

1. Каждый алгоритм имеет дело с данными - входными, промежуточными, выходными. Для того, чтобы уточнить понятие данных, фиксируется конечный алфавит исходных символов (цифры, буквы и т.п.) и указываются правила построения алгоритмических объектов. Типичным используемым средством является индуктивное построение. Например, определение идентификатора в АЛГОЛЕ: идентификатор - это либо буква, либо идентификатор, к которому справа приписана либо буква, либо цифра. Слова конечной длины в конечных алфавитах - наиболее обычный тип алгоритмических данных, а число символов в слове - естественная мера объема данных.

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

3. Алгоритм состоит из отдельных элементарных шагов, причем множество различных шагов, из которых составлен алгоритм, конечно. Типичный пример множества элементарных шагов - система команд ЭВМ.

4. Последовательность шагов алгоритма детерминирована, т.е. после каждого шага указывается, какой шаг следует выполнять дальше, либо указывается, когда следует остановиться.

5. Алгоритм обладает результативностью, т.е. останавливается после конечного числа шагов (зависящего от исходных данных) с выдачей результата.

6. Алгоритм предполагает наличие механизма реализации алгоритма, который по описанию алгоритма порождает процесс реализации на основе исходных данных.

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

Данная модель была предложена в 30-х годах А.Тьюрингом и оказала влияние на разработку ЭВМ. В данном подходе “алгоритм” - это программа некоторой конкретной ЭВМ, а функция алгоритмически вычислима, если можно запрограммировать ее вычисление.

Дата добавления: 2014-12-08