§ 47. Еще раз о понятии «алгоритм»

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

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

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

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

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

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

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

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

Определённость означает, что на каждом шаге исполнитель не выбирает способ действия самостоятельно. Если написано «возьми немного сахара», разные исполнители могут взять разное количество, и ход решения изменится. Точная команда, например «добавь 10 г сахара», устраняет такой выбор; условие тоже должно иметь ясный результат проверки — истина или ложь.

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

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

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

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

Разбор задач

1. Описание приготовления блюда

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

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

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

2. Условие и повторение в алгоритме

Условие. Выполним алгоритм для чисел 8, 5, 3: присвоить A значение 8, B значение 5; пока B не равно 0, найти остаток R от деления A на B, затем присвоить A значение B, а B значение R. Записываем значения переменных после каждого шага, чтобы увидеть работу условия и цикла. Такой алгоритм использует правило Евклида для поиска наибольшего общего делителя.

1. Начальные значения: A = 8, B = 5. Проверяем условие B ≠ 0: оно истинно.
2. Первый проход: R = 8 mod 5 = 3; затем A = 5, B = 3. Условие снова истинно.
3. Второй проход: R = 5 mod 3 = 2; затем A = 3, B = 2. Условие по-прежнему истинно.
4. Третий проход: R = 3 mod 2 = 1; затем A = 2, B = 1. Условие истинно, поэтому цикл выполняется ещё раз.
5. Четвёртый проход: R = 2 mod 1 = 0; затем A = 1, B = 0. Условие ложно, цикл прекращается.

Ответ. Алгоритм завершился, и A = 1 — НОД чисел 8 и 5. Трассировка показывает, какая ветвь выполняется: пока B не равно нулю, действия повторяются, а при B = 0 происходит остановка. Запись промежуточных значений помогает обнаружить ошибки в порядке присваиваний.

3. Нахождение НОД

Условие. Составим алгоритм для нахождения наибольшего общего делителя двух натуральных чисел a и b. Используем алгоритм Евклида: заменяем пару чисел на меньшее и остаток от деления большего на меньшее. Требуется обосновать не только ответ, но и то, что вычисление завершится и будет правильным.

1. Пока b ≠ 0, вычисляем r = a mod b — остаток от деления a на b.
2. Затем присваиваем a значение b, а b значение r; повторяем проверку условия.
3. Когда b = 0, выдаём a и останавливаемся.
4. Обосновываем правильность: НОД(a, b) = НОД(b, r), поскольку a можно представить как a = qb + r, а общий делитель a и b делит и r, и наоборот.
5. Обосновываем завершение: остаток r — целое число от 0 до b − 1. Значит, ненулевое значение b на каждом проходе строго уменьшается и в конце концов становится нулём.

Ответ. Алгоритм Евклида возвращает НОД исходных чисел: на каждом шаге НОД сохраняется, а остаток уменьшается до нуля. Это одновременно объясняет правильность результата и конечность выполнения. Для любого допустимого набора натуральных чисел с b ≠ 0 шаги определены, поэтому алгоритм массовый.

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

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

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

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

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

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

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

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

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