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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм, исполнитель и команды

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

Разбор задач

Задача 1. Запишите алгоритм перехода улицы по пешеходному переходу и укажите исполнителя. Нужно не ограничиваться советом «перейти дорогу», а разбить его на безопасные действия. Команды должны подходить человеку и идти в таком порядке, чтобы переход начинался только при безопасных условиях.

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

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

Задача 2. Робот находится в клетке A1, а предмет — в A4. Ему доступны команды «вверх» и «взять». Нужно понять, сколько перемещений отделяет начальную клетку от цели, и не использовать команды, которых у робота нет.

1. Сравнить адреса клеток: при движении вверх ряд меняется от A1 к A2, затем к A3 и A4. Значит, до предмета нужно выполнить три перемещения.
2. Записать команды «вверх», «вверх», «вверх». Порядок важен: робот должен оказаться в A4 прежде, чем сможет взять находящийся там предмет.
3. Добавить команду «взять» и проверить, что все команды входят в систему команд исполнителя. После трёх перемещений робот находится в нужной клетке.

Ответ: «вверх», «вверх», «вверх», «взять». Алгоритм заканчивается выполнением заданного действия — предмет взят в клетке A4.

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

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

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

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

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

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

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

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

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

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

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

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