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

Понятие алгоритма

Первоначально понятие алгоритма отождествлялось с понятием метода вычислений. С точки зрения современной практики алгоритм – программа, критерием алгоритмичности процесса является возможность его запрограммировать. Именно благодаря этой реальности алгоритма, а также благодаря тому, что подход инженера к математическим методам всегда был конструктивным, понятие алгоритма в технике за короткий срок стал необычайно популярным.

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

Определение 1. Алгоритм (алгорифм) – точное предписание, которое задает вычислительный процесс, начинающийся с произвольного исходного данногои направленный на получение полностью определенного этим исходным данным результата. (Математическая энециклопедия)

Другое определение понятия алгоритма может выглядеть следующим образом

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

Или

Определение 3.Алгоритм есть предписание, однозначно определяющее ход некоторых конструктивных процессов.

Данные определения недостаточны для введения четкого и однозначного задания исследуемого объекта. Необходимы уточнения.

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

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

3. Алгоритм состоит из отдельных элементарных шагов (действий). Множество шагов алгоритма конечно.

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

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

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

· описание алгоритма (инструкцию или программу);

· механизм реализации алгоритма (устройство, например, ЭВМ), включающий средства пуска, остановки, управления ходом вычислений и т.д.);

· процесс реализации алгоритма (алгоритмический процесс).

Сформулированные требования несколько уточняют понятие алгоритма, но не вносят полной ясности, поскольку используют нечеткие понятия. Поэтому при исследовании понятия алгоритма используют более строгие алгоритмические модели, например, машина Тьюринга, частично-рекурсивные функции, машина Колмогорова, нормальные алгорифмы Маркова, канонические системы Поста и т.д.

Лекция 2