§ 7. Алгоритмы и их свойства

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

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

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

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

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

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

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

Команды выбирают с учётом исполнителя: его возможности определяются системой команд. Например, робот, умеющий двигаться только по клеткам, не поймёт команду «перепрыгни через препятствие», если такого действия в его наборе нет. Один алгоритм может быть понятен человеку, но непонятен роботу; для другого исполнителя его нужно записать командами, которые тот умеет выполнять.

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

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

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

Основные свойства алгоритма

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

Разбор задач

Задача 1. Определить, является ли алгоритмом описание: «Чтобы вскипятить воду, возьмите чайник, налейте воду и нагревайте её до кипения». Сначала проверим, есть ли исполнитель: предполагается человек, но этот выбор прямо не указан. Затем оценим точность команд и условие остановки, поскольку именно они показывают, можно ли воспроизвести действия одинаково.

1. Выделим команды: взять чайник, налить воду, нагревать.
2. Уточним условия: не сказано, какой чайник использовать и как проверить, что вода закипела.
3. Проверим завершение: условие «до кипения» задаёт цель, но не описывает способ её распознать.

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

Задача 2. Исполнитель перемещается по клетчатому полю командами «вверх», «вниз», «влево», «вправо». Составим путь из клетки A в клетку B, хотя координаты клеток не заданы. Поэтому запишем правило построения: сначала определим, сколько клеток разделяет их по горизонтали и вертикали, затем выберем направление по каждому измерению.

1. Посчитаем горизонтальное смещение от A к B. Если B правее, добавим столько команд «вправо», если левее — «влево».
2. Посчитаем вертикальное смещение. Если B выше, добавим команды «вверх», если ниже — «вниз».
3. Выполним полученную последовательность и проверим, что она заканчивается в B.

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

Задача 3. Составить алгоритм Евклида для нахождения НОД двух натуральных чисел и объяснить его применимость. НОД — наибольший общий делитель чисел. Идея состоит в том, что общие делители пары чисел сохраняются при замене пары на меньшее число и остаток от деления большего на меньшее.

1. Обозначим числа a и b, при необходимости расположив их так, чтобы a ≥ b.
2. Пока b ≠ 0, найдём остаток r от деления a на b и заменим a на b, а b на r.
3. Когда b станет равным 0, остановимся: текущее a и есть НОД исходных чисел.

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

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

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

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

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

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

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

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

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

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

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

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