Определение алгоритма и понятие его исполнителя

Алгоритм – заранее заданное понятное и точное предписание возможному исполнителю совершить определенную последовательность действий для получения решения задачи за конечное число шагов.

Название «алгоритм» произошло от латинской формы имени среднеазиатского математика аль-Хорезми – Algorithmi.

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

Основные свойства алгоритмов следующие:

- Понятность– исполнитель алгоритма должен знать, как надо действовать для выполнения этого алгоритма.

- Дискретность (прерывность, раздельность) – алгоритм должен представлять процесс решения задачи как последовательное выполнение простых (или ранее определенных) шагов (этапов).

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

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

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

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

Исполнитель алгоритма – это некоторая абстрактная или реальная (технически, биологически или биотехническая) система, способная выполнять действия, предписываемые алгоритмом.

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

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

Это – важная особенность алгоритмов. Наличие алгоритма формализует процесс решения задачи, исключает рассуждение исполнителя. Использование алгоритма дает возможность решать задачу формально, механически исполняя команды алгоритма в указанной последовательности. Целесообразность предусматриваемых алгоритмом действий обеспечивается точным анализом со стороны того, кто составляет этот алгоритм.

Исполнителя характеризует:

- среда;

- система команд;

- элементарные действия;

- отказы.

Среда (или обстановка) – это «место обитания» исполнителя, которое характеризуется состоянием среды.

Каждый исполнитель может выполнять команды только из некоторого строго заданного списка – системы командисполнителя. Для каждой команды должны быть заданы условия применимости (в каких состояниях среды может быть выполнена команда) и описаны результаты выполнения команды.

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

Отказы исполнителя возникают, если команда вызывается при недопустимом для нее состоянии среды.

Наиболее распространенными и привычными являются алгоритмы работы с величинами – числовыми, символьными, логическими и т.д., а универсальным исполнителем алгоритмов является компьютер.

КЛАССЫ МОДЕЛЕЙ АЛГОРИТМОВ.

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

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

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

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

Рисунок 1

Лента

Считывающая головка

Управляющее устройство машины

Отсутствие символа в ячейке обозначается специальным «пустым» символом « ». Головка всегда располагается над некоторой ячейкой ленты. Она может читать и писать символы, стирать их и перемещаться вдоль ленты. Число возможных символов конечно, и образуют алфавит машины А = {a₁ ,…, a_m}. Головка в каждый такт работы машины находится в одном из состояний. Множество таких состояний конечно Q = {q₁,…,q _n} и среди них выделяют начальное q₁ и конечное q _z состояние.

Элементарный шаг машины Тьюринга состоит из следующих действий:

- головка считывает символ, записанный в ячейке, над которой она находится;

- считанный символ а _k и текущее состояние головки q _j однозначно определяют новое состояние q _i , новый записываемый символ а₁ и перемещение головки d _p (которое может иметь значение на ячейку влево, на ячейку вправо, остаться на месте).

Устройство управления хранит и выполняет команды машины вида q _j a _k ® q _i a₁ d _p.

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

Третий класс моделей алгоритмов очень близок к предыдущему, но не оперирует конкретными машинными механизмами. Он основан, например, на нормальных алгоритмах Маркова.

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

1) Я ® У

2) Л ® У

3) С ® М

4) В ® б

5) Р ® Т

6) Т ® Р!

7) О ® х

8) Н ® а,

то, используя правила:

- проверить возможность подстановок в порядке возрастания их номеров, и если она возможна (левая часть подстановки обнаружена в исходном слове), произвести подстановку (заменив левую часть на правую);

- если в примененной подстановке имеется символ «!», то преобразования прекращаются, а если нет, то текущее состояние становится исходным и весь процесс начинается заново;

- если ни одна подстановка не применима, то процесс преобразования завершен;

можно обнаружить, что по заданному алгоритму исходное слово «слон» превращается в слово «муха» по следующей цепочке:

«слон» ® «суон» ® «муон» ® «мухн» ® «муха».

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

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

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

Знание основных неразрешимостей теории алгоритмов необходимо для специалиста, чтобы предостеречь его от всеобщей алгоритмизации, как знание основных законов физики предостерегает от попыток создания вечного двигателя.

ФОРМЫ ЗАПИСИ АЛГОРИТМОВ

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

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

- графическая (изображения из графических символов);

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

- программная (тексты на языках программирования).

Словесный способ записи

Словесный способзаписи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.

Описательный алгоритм не имеет широкого распространения, так как такие описания:

- строго не формализуемы;

- страдают многословностью записей;

- допускают неоднозначность толкования отдельных предписаний.