Алгоритмы, их свойства и средства описания

Алгоритм - четкая система правил, которые задают последовательность действий над некоторыми объектами и после конечного числа шагов приводят к достижению поставленной цели. Всякий алгоритм рассчитан на определенного исполнителя (организация, человек, автомат, компьютер). Выполнимый алгоритм должен представлять собой последовательность предписаний для конкретного исполнителя.

Любой алгоритм должен обладать следующими свойствами:

- дискретность - пошаговый характер определяемого алгоритмом процесса.

- определенность - неизбежность получения одного и того же результата при многократном применении алгоритма к одним и тем же исходным данным.

- результативность - возможность получения результата через конечное число шагов.

- массовость - возможность применения алгоритма для решения класса задач, отличающихся лишь исходными данными.

Существуют следующие способы описания алгоритмов:

- запись на естественном языке;

- запись на алгоритмическом языке;

- изображение в виде блок-схем алгоритмов;

- запись на языке конкретной системы программирования.

Основные понятия теории алгоритмов. Теория алгоритмов - раздел математики, изучающий общие свойства алгоритмов. Понятие «алгоритма» сформировалось в математике в 20-х годах ХХ века. Началом систематической разработки теории алгоритмов можно считать 1936 г. (работа А. Черча).

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

Результатами теоретических исследований явились три основных класса арифметических моделей:

- первый класс – основан на арифметизации алгоритмов, предполагается, что любые данные можно закодировать числами, и как следствие - всякое их преобразование становится в этом случае арифметическим вычислением, алгоритмом в таких моделях есть вычисление значения некоторой числовой функции, а его элементарные шаги - арифметические операции. Последовательность шагов определяется двумя способами. Первый способ - суперпозиция, т.е. подстановка функции в функцию, а второй - рекурсия, т.е. определение значения функции через «ранее» вычисленные значения;

- второй класс – для того, чтобы алгоритм понимался однозначно, а его каждый шаг считался элементарным и выполнимым, он должен быть представлен так, чтобы его могла выполнять машина, к которой предъявляются требования простоты и универсальности. Одной из таких машин явилась абстрактная машина Тьюринга;

- третий класс – для алгоритма в этой модели задаются алфавит, над которым он работает, конечное множество допустимых подстановок и порядок их применения. Такие алгоритмы называются - нормальные алгоритмы Маркова.