Алгоритм. Свойства алгоритмов
Алгоритм – строго определенная последовательность действий, выполнение которых приводит к решению поставленной задачи за конечное число шагов.
Алгоритмизация – процесс разработки алгоритма (плана действий) для решения задачи.
Появление алгоритмов связывают с зарождением математики. Более 1000 лет назад (в 825 году) ученый из города Хорезма Абдулла (или Абу Джафар) Мухаммед бен Муса аль-Хорезми создал книгу по математике, в которой описал способы выполнения арифметических действий над многозначными числами. Само слово «алгоритм» возникло в Европе после перевода на латынь книги этого среднеазиатского математика, в которой его имя писалось как «Алгоритми».
Человеку в жизни и практической деятельности приходится решать множество различных задач. Решение каждой из них описывается своим алгоритмом, разнообразие этих алгоритмов очень велико. Можно выделить три основных вида алгоритмов:
1. линейной структуры,
2. разветвляющейся структуры,
3. циклической структуры.
Для краткости их называют просто: линейные, разветвляющиеся и циклические алгоритмы. Разнообразие же алгоритмов определяется тем, что любой алгоритм распадается на части, фрагменты и каждый фрагмент представляет собой алгоритм одного из трех указанных видов. Поэтому важно знать структуру каждого из алгоритмов.
В алгоритмах линейной структуры действия выполняются последовательно одно за другим:
В алгоритмах разветвленной структуры в зависимости от выполнения или невыполнения какого-либо условия производятся различные последовательности действий. Каждая такая последовательность действий называется ветвью алгоритма.
В алгоритмах циклической структуры в зависимости от выполнения или невыполнения какого-либо условия выполняется повторяющаяся последовательность действий, называющаяся телом цикла. Вложенным называется цикл, находящийся внутри тела другого цикла.
Различают циклы с предусловием (ПОКА) и постусловием (ДО):
Итерационным называется цикл, число повторений которого не задается, а определяется в ходе выполнения цикла. В этом случае одно повторение цикла называется итерацией.
4. Вспомогательный алгоритм – алгоритм, который можно использовать в других алгоритмах, указав только его имя. Например: вы в детстве учились суммировать единицы, затем десятки, чтобы суммировать двузначные числа содержащие единицы вы не учились новому методу суммирования, а воспользовались старыми методами.
Свойства алгоритмов
Понятность – каждая команда должна входить в систему команд исполнителя.
Дискретность – это разбиение алгоритма на ряд отдельных законченных команд (шагов), каждая из которых должна быть выполнена прежде, чем исполнитель перейдет к выполнению следующей.
Детерминированность (точность, определенность) – команда алгоритма исполнителем должна пониматься однозначно. Не должно быть двоякого толкования команды.
Результативность и конечность – за конечное число шагов алгоритм либо должен приводить к решению задачи, либо после конечного числа шагов останавливаться из-за невозможности получить решение с выдачей соответствующего сообщения, либо неограниченно продолжаться в течение времени, отведенного для исполнения алгоритма, с выдачей промежуточных результатов.
Массовость – алгоритм решения задачи разрабатывается в общем виде – он должен быть применим для некоторого класса задач, различающихся лишь исходными данными. (Исходные данные могут выбираться из некоторой области, которая называется областью применимости алгоритма.)
Рассмотрим свойства алгоритмов на примерах:
Пример. алгоритм выполнения открывания двери.
Достать ключ из кармана.
Вставить ключ в замочную скважину.
Повернуть ключ два раза против часовой стрелки.
Вынуть ключ.
Вас пригласили в гости и подробно объяснили, как добраться:
Выйти из дома.
Повернуть направо.
Пройти два квартала до остановки.
Сесть в автобус № 5, идущий к центру города.
Проехать три остановки.
Выйти из автобуса.
Найти по указанному адресу дом и квартиру.
Понятность – каждая команда должна входить в систему команд исполнителя.
Дискретность (от лат. discretus — разделенный, прерывистый) – это разбиение алгоритма на ряд отдельных законченных действий (шагов). В приведенных выше алгоритмах общим является необходимость строгого соблюдения последовательности выполнения действий. Попробуем переставить в первом примере второе и третье действия. Вы, конечно, сможете выполнить и этот алгоритм, но дверь вряд ли откроется. А если поменять местами, предположим, пятое и второе действия во втором примере, алгоритм станет невыполнимым.
Детерминированность (от лат. determinate — определенность, точность) – любое действие алгоритма должно быть строго и недвусмысленно определено в каждом случае. Например, если к остановке подходят автобусы разных маршрутов, то в алгоритме должен быть указан конкретный номер маршрута — 5. Кроме того, необходимо указать точное количество остановок, которое надо проехать, — скажем, три.
Конечность – каждое действие в отдельности и алгоритм в целом должны иметь возможность завершения. В приведенных примерах каждое описанное действие реально и может быть выполнено. Поэтому и алгоритм имеет предел, то есть конечен.
Результативность. В алгоритме должны быть предусмотрены все возможные пути решения, в том числе альтернативные. Пример: алгоритм нахождения большего из двух заданных чисел А и В: