§ 14. Алгоритм как форма организации процедурной информации

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

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

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

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

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

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

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

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

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

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

Один и тот же алгоритм можно записать словами, изобразить блок-схемой или выразить программой. Разные формы помогают разным исполнителям: человеку часто удобны слова и схемы, компьютеру — команды языка программирования. Главное, чтобы представление сохраняло общий порядок действий и не меняло смысл условий.

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

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

Разбор задач

Приготовление бутерброда для робота

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

1. Проверяем систему команд и выбираем только доступные роботу действия. Если команды «намазать» в ней нет, нужно описать операцию командами, которые робот понимает, либо признать, что выполнить её он не может.
2. Определяем нужные предметы: ломтик хлеба и сыр. Задаём исходное положение, например, что продукты доступны роботу и лежат на столе.
3. Записываем действия в порядке выполнения: взять хлеб; положить хлеб на тарелку; взять сыр; положить сыр на хлеб. Каждый пункт — отдельная команда, а не общее пожелание.
4. Прослеживаем выполнение и проверяем результат. Робот не должен попытаться положить сыр на хлеб до того, как хлеб окажется на тарелке.

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

Выполнение условия для разных чисел

Условие. Если число больше 10, вычесть 3, иначе прибавить 5; повторить действия для чисел 8, 12 и 20. Слова «повторить действия» здесь означают применить правило отдельно к каждому исходному числу, а не выполнять его снова над полученным результатом. Поэтому сначала проверяем условие для каждого числа.

1. Для 8 проверяем: 8 больше 10? Нет. Выбираем ветвь «иначе» и вычисляем 8 + 5 = 13.
2. Для 12 проверяем: 12 больше 10? Да. Вычитаем 3 и получаем 12 − 3 = 9.
3. Для 20 проверяем: 20 больше 10? Да. Вычитаем 3 и получаем 20 − 3 = 17.
4. Сверяем каждый ответ с выбранной ветвью. Это помогает заметить ошибку, если условие проверили неверно или применили не ту операцию.

Ответ. Для чисел 8, 12 и 20 результаты соответственно равны 13, 9 и 17. Проверка условия каждый раз определяет, какое действие выполнять.

Проверка алгоритма Евклида

Условие. Алгоритм Евклида должен находить НОД двух натуральных чисел — наибольший общий делитель. В повреждённой записи указано: «пока числа не равны, заменить большее числом, равным разности большего и меньшего; вывести НОД». Ошибка находится не в выборе операции вычитания, а в том, что не сказано, какие значения нужно вывести после цикла.

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

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

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

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

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

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

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

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

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

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

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