§ 16. Алгоритм и его свойства

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

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

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

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

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

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

Представим задачу: найти сумму двух чисел. Для исполнителя-компьютера можно задать команды: ввести первое число a, ввести второе число b, вычислить s = a + b и вывести s. Если введены 4 и 7, компьютер выполняет заданные действия и выводит 11. Исходная задача превращается в набор команд, доступных этому исполнителю.

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

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

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

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

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

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

Разбор задач

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

Условие. Дан алгоритм: ввести a и b, вычислить s = a + b, вывести s. Требуется определить исполнителя, его систему команд и результат при a = 8, b = 5. Проследим выполнение по порядку.

1. Исполнитель — компьютер, если он умеет вводить значения, складывать числа и выводить результат.
2. Его нужная система команд включает ввод данных, сложение и вывод. Команды алгоритма входят в эту систему, поэтому исполнитель способен их выполнить.
3. Компьютер присваивает s значение 8 + 5 = 13 и выводит его. Каждый шаг приводит к следующему, а после вывода выполнение заканчивается.

Ответ. Исполнитель — компьютер; используются команды ввода, сложения и вывода. Результат выполнения — 13.

Точное количество сахара

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

1. Слово «немного» не задаёт точного количества, поэтому разные исполнители могут добавить разное количество сахара.
2. Указание «одну чайную ложку» задаёт конкретную меру и уменьшает число возможных толкований.
3. Алгоритм стал определённее; если исполнитель понимает такую единицу измерения и умеет отмерить сахар, команда стала для него понятнее и выполнимее.

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

Поиск наибольшего из трёх чисел

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

1. Обозначим числа a, b и c. Сначала можно выбрать большее из a и b, затем сравнить его с c и вывести наибольшее.
2. Если для одного исхода сравнения ветвь не содержит команды, исполнитель не знает, что делать дальше. Значит, предписание в этой ситуации неполно и не задаёт однозначного перехода.
3. Если из-за пропуска алгоритм не доходит до вывода, результат не гарантирован. Нужно дописать действие в пропущенную ветвь и повторно проверить все возможные случаи.

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

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

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

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

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

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

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

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

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

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