Алгоритм — это упорядоченный набор однозначных выполнимых шагов.
Обратите внимание на то, что это определение утверждает, что набор шагов должен быть упорядочен. Это означает, что шаги в алгоритме должны быть структурированы, то есть должны выполняться в определенном порядке. Это не значит, что сначала должен выполняться первый шаг, затем второй и т. д. Например, некоторые алгоритмы, которые называются параллельными, содержат несколько последовательностей шагов, каждая из которых выполняется одним процессором многопроцессорной машины. В таких случаях полный алгоритм не содержит единственную цепочку шагов, которая соответствовала бы сценарию, когда сначала выполняется первый шаг, затем второй и т.д. Вместо этого структура алгоритма включает в себя несколько цепочек, которые ветвятся и снова соединяются по мере того, как разные процессоры выполняют разные части задачи.
Следующее утверждение, присутствующее в определении алгоритм; говорит о том, что алгоритм должен состоять из выполнимых шагов. Для того чтобы понять это условие, рассмотрим команду: Вывести список всех положительных целых чисел. Выполнить эту команду невозможно, поскольку существует бесконечное множество положительных целых чисел. Поэтому любой набор команд, включающий такое указание, не является алгоритмом.
Другое условие, содержащееся в определении алгоритма, гласит, что шаги алгоритма должны быть однозначными, то есть во время выполнения должно быть достаточно информации для однозначного и полного определения действий, выполнения которых требует шаг. Другими словами, для выполнения каждого шага должно требоваться не наличие творческих способностей, а только способность следовать указаниям.
Определение алгоритма также подразумевает, что алгоритм определяет конечный процесс, то есть выполнение алгоритма должно когда-нибудь закончиться. Это требование происходит из области теоретической вычислительной техники, цель которой состоит в том, чтобы ответить на такие вопросы, как «каковы предельные возможности алгоритмов и машин?». Здесь вычислительная техника проводит границу между задачами, которые можно решить с помощью алгоритмов, и задачами, которые не имеют алгоритмического решения. В нашем случае различается процесс, который завершается ответом, и процесс, который продолжается бесконечно, не порождая никакого результата.
Однако бесконечные процессы применяются на практике. Например, контроль состояния пациента в больнице или определение высоты, на которой находится самолет во время полета. Некоторые возразят, что в таких системах происходит просто повторение одного алгоритма, выполнение которого завершается, а затем автоматически повторяется. Другие посчитаю, что такие аргументы являются просто попыткой сохранить чрезмерно ограничивающее формальное определение. В любом случае, термин «алгоритм» часто используется в нестрогом прикладном смысле, но отношению к набору шагов, которые не обязательно определяют конечный процесс. Примером может служить алгоритм деления в столбик, который не определяет конечный процесс в случае деления, например, 1 на 3. Формально, в таких случаях термин «алгоритм» употребляется неправильно. [1]
Основные свойства алгоритмов:
1) понятность для исполнителя;
2) дискретность (процесс решения задачи представляется как последовательность выполнения простых шагов);
3) определенность (однозначность);
4) конечность (должен приводить к решению задачи за конечное число шагов);
5) универсальность (должен быть применим для некоторого класса задач, область применения алгоритма).
Алгоритм является абстракцией, которая может иметь множество различных представлений (формула, словесное описание, электронная схема и т.п.) Различие между алгоритмом и его представлением является существенным, когда мы пытаемся передать алгоритм. Представление может быть более и менее подробным в зависимости от того, кому оно предназначено. Неоднозначность понимания алгоритма обычно заключается в представлении алгоритма, а не в нем самом.
Дата добавления: 2017-01-29; просмотров: 1125;