§ 29. Алгоритмы и исполнители

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

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

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

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

Допустимая команда — команда из системы команд исполнителя, которую можно выполнить в текущей ситуации. Неизвестная команда исполнителю непонятна, а известная может оказаться невыполнимой, например из-за препятствия. Проверка допустимости помогает заметить такой шаг до того, как он нарушит выполнение алгоритма.

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

Алгоритм описывает не только цель, но и порядок действий, потому что исполнитель должен понимать, что делать сначала и что — потом. Если написать лишь «получи ответ», исполнитель не узнает, какие операции нужны. Каждый шаг должен быть сформулирован так, чтобы его можно было выполнить без догадок.

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

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

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

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

Исполнители, их среды и системы команд

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

Разбор задач

Сумма двух введённых чисел

Условие. Нужно составить последовательность действий, чтобы найти сумму двух введённых чисел. Сначала определим, какие данные нужны: два числа, которые вводит пользователь. Результатом будет одно число — их сумма.

1. Ввести первое число и сохранить его, например, в переменной a.
2. Ввести второе число и сохранить его в переменной b.
3. Вычислить сумму: s = a + b.
4. Вывести значение s.

Порядок важен: пока числа не введены, складывать нечего, а вывести результат можно только после вычисления. Запись «найти сумму» была бы целью, а не готовым алгоритмом, потому что в ней не указаны нужные действия. Ответ: ввод a, ввод b, вычисление s = a + b, вывод s.

Робот обходит препятствие

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

1. Проверить, куда направлен робот, и определить свободный обходной путь.
2. Повернуть робота в сторону, где можно обойти препятствие.
3. Пройти одну клетку, затем повернуть в направлении цели.
4. Пройти до клетки, расположенной за препятствием, и повернуть к цели.
5. Дойти до отмеченной клетки, проверяя после каждого движения, что впереди свободно.

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

Неизвестная команда

Условие. В алгоритме для исполнителя встречается команда, которой нет в его системе команд. Нужно определить, сможет ли он выполнить алгоритм, и исправить запись. Для примера пусть робот знает команды «вперёд» и «поверни», но в алгоритме ему велено «перепрыгни препятствие».

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

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

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

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

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

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

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

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

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

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

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