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

Алгоритмы и языки

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

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

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

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

Когда мы имеем дело с алгоритмом, неявно подразумевается, что существует субъект, который, во-первых, формулирует цель, которую надо достичь, то есть ставит задачу, во-вторых, составляет последовательность действий, направленных на решение этой задачи. Этот субъект является автором алгоритма. Если автор алгоритма выполняет эти действия сам, то особых проблем не возникает. Однако основное применение алгоритмов связано с тем, что последовательность действий выполняет не автор алгоритма, а некоторый другой субъект, которого будем называть исполнителем.

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

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

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

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

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

Рассмотрим проблемы, связанные с понятием алгоритма.

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

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

Кроме самого алгоритма, исполнителю необходимо сообщить, с какими объектами он будет иметь дело в процессе выполнения алгоритма. Фактически выполнение алгоритма сводится либо к переводу некоторого объекта из начального состояния в конечное, либо к конструированию нового объекта из некоторой совокупности исходных объектов по правилу, описываемому алгоритмом. Начальное состояние преобразуемого объекта или совокупность исходных объектов называются исходными данными алгоритма.

Каждый алгоритм предполагает наличие некоторых исходных данных. Например, для медицинского рецепта (алгоритма) исходными данными являются медикаменты, а результатом – флакон с готовым лекарством. Для алгоритма сложения исходными данными являются пара слагаемых, а результатом – их сумма. Для каждого алгоритма существует класс объектов, допустимых в качестве исходных данных. Иногда исходными данными являются материальные объекты, а иногда – числа или тексты.

Алгоритм – это сообщение, передаваемое исполнителю, следовательно, оно должно быть сформулировано на некотором языке.

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

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

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

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

Свойства алгоритмов

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

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

2. Точность, или детерминированность. Запись алгоритма должна быть такой, чтобы, выполнив очередную команду, исполнитель точно знал, какую команду надо выполнять следующей. Это приводит к тому, что алгоритм всегда выдаёт один и тот же результат для одних и тех же исходных данных.

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

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

5. Массовость. С помощью одного и того же алгоритма можно решать однотипные задачи и делать это неоднократно. Алгоритм должен быть применим к разным наборам исходных данных, допустимым в решаемой задаче. Свойство массовости значительно увеличивает практическую ценность алгоритмов.