Алгоритм и его свойства

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

• Дискретность. Алгоритм разбивается на отдельные действия (шаги). Выполнение очередного действия возможно только после завершения предыдущего. При этом набор промежуточных данных конечен и получается по определенным правилам из данных предыдущего действия. Команда является специальным указанием для исполнителя, предписывающим ему произвести каждое отдельное действие. Команды, которые относят к системе команд исполнителя, называют простыми; другие команды могут быть определены через простые.

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

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

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

• Конечность. Реализуемый по заданному алгоритму процесс должен остановиться через конечное число шагов и выдать искомый результат. Это свойство тесно связано со свойством результативности. 

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

Пример 1.1. Алгоритм "Решето Эратосфена" позволяет получить простые числа, не превосходящие N.

1. Прокомментируйте основные свойства алгоритма для решета Эратосфена.

2. Аль-Хорезми составил алгоритмы арифметических действий еще в IX в. Составьте алгоритмы выполнения арифметических действий в столбик. Проверьте для составленных алгоритмов основные свойства.

3.    Приведите примеры алгоритмов, обладающих указанными признаками.

   1. Используется только алгоритмическая конструкция следование.

   2. Присутствует алгоритмическая конструкция ветвление.

   3. Присутствует алгоритмическая конструкция цикл.

   4. Используются подпрограммы.

4.    Опишите последовательность действий для решения задачи «Волк, коза и капуста».

Однажды крестьянину понадобилось перевезти через реку волка, козу и капусту. У крестьянина есть лодка, в которой может поместиться, кроме самого крестьянина, только один объект — или волк, или коза, или капуста. Если крестьянин оставит без присмотра волка с козой, то волк съест козу; если крестьянин оставит без присмотра козу с капустой, коза съест капусту. Как крестьянину перевезти на другой берег и волка, и козу, и капусту в целости и сохранности?

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

5.  Есть двое песочных часов на 3 мин и на 8 мин. Как с их помощью отмерить 7 мин? Определите систему команд исполнителя, который может решать эту задачу, и составьте для него последовательность действий, приводящую к ответу. Какие алгоритмические конструкции были использованы при реализации? Можно ли считать полученную последовательность действий алгоритмом? Какое свойство алгоритма не выполняется? Возможно ли переформулировать задачу так, чтобы аналогичная последовательность действий стала алгоритмом?