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

Определения и обозначения

Алгоритм — точное и понятное исполнителю описание последовательности действий, приводящей к решению задачи. Это не просто рассказ о цели: в нём должно быть указано, что и в каком порядке делать. Благодаря этому исполнитель может выполнить задачу без догадок.

Исполнитель алгоритма — человек или устройство, способное выполнять команды алгоритма. У каждого исполнителя есть свои возможности: человек может понимать сложные инструкции, а устройство действует по заданным правилам. Поэтому при составлении алгоритма нужно учитывать, кому он предназначен.

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

Алгоритмический язык — формальный язык для записи алгоритмов с определёнными правилами и командами. Формальность означает, что запись строится по установленным правилам, а не произвольно. Такой язык позволяет одинаково понимать последовательность действий человеку и компьютеру.

Как это устроено

Описание становится алгоритмом не потому, что в нём просто упомянуто решение, а потому, что оно задаёт исполнимые действия. Указание «найти ответ удобным способом» оставляет выбор самому исполнителю и не объясняет, как действовать. Точные команды уменьшают неопределённость и позволяют проверить, приводит ли выполнение к цели.

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

Определённость, или детерминированность, требует, чтобы следующий шаг задавался однозначно при одинаковых исходных данных и состоянии исполнителя. Если в инструкции сказано «выбери подходящее число», исполнитель может выбрать по-разному, и ход решения разойдётся. Чёткие условия и команды дают предсказуемое выполнение.

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

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

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

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

Разбор задач

Задача 1. Составить алгоритм для вычисления периметра прямоугольника по заданным длинам сторон a и b. Нужно получить последовательность команд, подходящую для любых допустимых значений сторон. Периметр равен удвоенной сумме длин двух соседних сторон.

1. Ввести значения a и b.
2. Вычислить P = 2(a + b).
3. Вывести P.

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

Задача 2. Дан алгоритм: ввести число n; присвоить s значение 0; повторять n раз: увеличить s на 1; вывести s. Определить результат при n = 4 и оценить алгоритм. Чтобы проверить его, проследим, как меняется значение s после каждого повторения цикла.

1. После присваивания получаем s = 0.
2. Первое, второе, третье и четвёртое увеличение дают соответственно s = 1, 2, 3 и 4.
3. После четырёх повторений цикл заканчивается, алгоритм выводит s.

Ответ: при n = 4 выводится 4. Команды выполняются отдельными шагами, а цикл имеет конечное число повторений, поэтому в этом случае алгоритм завершается. Для неотрицательного целого n он выводит n; область допустимых значений нужно учитывать при вводе.

Задача 3. Разработать алгоритм поиска наибольшего из трёх введённых чисел, учитывая равные значения. Удобно сначала принять первое число за текущий максимум, а затем сравнить с ним оставшиеся числа. Такая схема не требует отдельного случая, когда два или три значения равны.

1. Ввести a, b и c; присвоить max значение a.
2. Если b > max, присвоить max значение b.
3. Если c > max, присвоить max значение c.
4. Вывести max.

Ответ: алгоритм выдаёт наибольшее из трёх чисел. Если значения равны, строгие сравнения не заменят максимум на равное ему число, поэтому результат останется правильным. Все введённые числа проверяются, а последовательность команд заканчивается выводом.

Типичные ошибки

Считать алгоритмом любое описание решения — ошибка: фраза «найти удобный способ» не задаёт исполнителю точных действий. Так думают, потому что в обычном разговоре намёка на цель часто достаточно, а алгоритму нужны исполнимые команды. Проверь себя: сможет ли исполнитель начать и пройти решение, не выбирая способ самостоятельно?

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

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

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

Связь с другими темами

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

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

Что запомнить

• Алгоритм задаёт точную последовательность действий для исполнителя.
• Команды алгоритма должны быть понятны исполнителю и входить в его систему команд.
• Дискретность означает выполнение по отдельным шагам.
• Определённость означает однозначность следующего действия.
• Результативный алгоритм заканчивается за конечное число шагов и даёт результат.
• Массовый алгоритм решает класс однотипных задач.