"Информатика", Горячев А.В., Суворова Н.И.
Алгоритм — это точное описание действий, которое помогает решить задачу и получить нужный результат. Его выполняет человек или устройство, следуя командам, понятным именно этому исполнителю. Хороший алгоритм не оставляет исполнителю выбора там, где требуется конкретное действие, заканчивается за конечное число шагов и подходит для всех предусмотренных исходных данных. На примерах разберём, как составлять и проверять алгоритмы.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Алгоритм — точное описание последовательности действий, ведущих к решению задачи. Это не просто совет вроде «сделай аккуратно»: такой совет не объясняет, что именно делать. В алгоритме действия должны быть указаны так, чтобы исполнитель мог следовать им и прийти к цели.
Исполнитель алгоритма — человек или устройство, способные выполнять заданные команды. Исполнителем может быть, например, ученик, компьютер или бытовой прибор. Это понятие помогает понять, для кого составлены действия и какие возможности нужно учитывать.
Команда — отдельное указание исполнителю выполнить действие. Команда должна быть понятна именно этому исполнителю: человек может понять «открой окно», а компьютер — только предусмотренное для него указание. Если исполнитель не знает, что делать, команда не поможет решить задачу.
Система команд исполнителя — набор всех команд, которые данный исполнитель умеет выполнять. У разных исполнителей такие наборы могут различаться. Это понятие нужно, чтобы проверить, выполним ли алгоритм: в нём нельзя поручать действия, которых исполнитель не умеет совершать.
Сначала задачу формулируют: что известно и какой результат требуется получить. Затем ищут действия, которые могут привести от исходных данных к цели, и располагают их в нужном порядке. Так появляется алгоритм, который можно поручить исполнителю, а не просто общее пожелание.
Алгоритм составляют с учётом исполнителя, потому что один и тот же текст не обязательно подходит человеку и устройству. Компьютер, например, не догадается, что значит «посчитай как-нибудь», и не сможет выполнить команду, которой нет среди доступных ему. Поэтому каждое действие должно быть понятным исполнителю и входить в его систему команд.
Точность означает, что каждое указание задаёт определённое действие, а порядок команд не оставляет сомнений. Если написано «возьми подходящее число», исполнитель может выбрать разные числа и получить разные ответы. Чтобы избежать этого, нужно уточнить, откуда взять число и что делать с ним на каждом шаге.
Алгоритм должен быть конечным: выполнение не может продолжаться бесконечно, если требуется решить задачу. Кроме того, оно должно завершиться результатом, ради которого алгоритм составляли. Если исполнитель повторяет действия без остановки или заканчивает работу, так и не получив ответ, алгоритм не решает задачу.
Один алгоритм может решать не одну задачу с заранее известными числами, а целый класс похожих задач. Для этого в нём предусматривают исходные данные — значения, которые могут меняться от запуска к запуску. Например, алгоритм сложения принимает два числа, складывает их и выдаёт сумму; те же действия подходят для разных пар чисел.
Свойства из таблицы помогают проверить, можно ли поручить алгоритм выбранному исполнителю и приведёт ли он к цели. Для проверки пройдите по командам на конкретном примере, а затем попробуйте другие исходные данные. Если какой-то тест не пройден, уточните команды или добавьте недостающие действия.
| Свойство | Что означает | Как проверить на примере |
|---|---|---|
| Понятность | Команды известны исполнителю и доступны ему. | Проверьте, знает ли исполнитель, как выполнить каждую команду. |
| Точность | Действия и порядок команд заданы однозначно. | Убедитесь, что на каждом шаге ясно, что делать дальше. |
| Конечность | Выполнение завершается за конечное число шагов. | Проследите, что команды не заставляют повторять действия бесконечно. |
| Результативность | После выполнения получается результат задачи. | Сравните полученный ответ с тем, который требовалось найти. |
| Массовость | Алгоритм подходит для целого класса задач с разными данными. | Проверьте его на нескольких допустимых наборах исходных данных. |
Условие. Нужно составить порядок действий, который поможет включить компьютер и войти в свою учётную запись. Точные названия кнопок и вид экрана зависят от устройства. Поэтому команды должны описывать понятные действия, а пользователь должен учитывать подсказки на экране.
Ответ. Алгоритм состоит из проверки питания, включения компьютера, выбора учётной записи и подтверждения входа. Его команды понятны человеку, а проверка рабочего стола показывает, достигнута ли цель. При составлении алгоритма нужно учитывать особенности конкретного устройства.
Условие. Требуется найти сумму двух чисел, которые пользователь вводит перед запуском вычисления. Нужно предусмотреть и получение исходных данных, и действие с ними. Если пропустить ввод, алгоритм не будет знать, какие числа складывать.
Ответ. Алгоритм: ввести a и b, вычислить s = a + b, вывести s. Он подходит для разных пар чисел, потому что значения вводятся при каждом запуске. Это пример алгоритма для целого класса задач.
Условие. Нужно сравнить два введённых числа и определить большее. При составлении алгоритма важно не предполагать, что числа обязательно разные. Поэтому следует проверить и случай равенства, иначе для части данных ответ может оказаться неполным.
Ответ. Алгоритм сравнивает числа и выдаёт одно из трёх сообщений: первое больше, второе больше или числа равны. Проверка на равных числах подтверждает, что учтён важный особый случай. Для любых введённых чисел алгоритм выбирает подходящую ветвь и завершается.
Считать алгоритмом любое описание задачи — ошибка, потому что одних слов о цели недостаточно. Её допускают, когда принимают общий совет за готовый порядок действий. Проверьте себя: сможет ли исполнитель выполнить описание без догадок и приведут ли указанные действия к нужному результату?
Использовать команду, которой нет в системе команд исполнителя, — значит поручить ему невыполнимое действие. Такое случается, если составитель думает о своих возможностях, а не о возможностях исполнителя. Проверьте каждую команду отдельно: умеет ли именно выбранный исполнитель её выполнять?
Пропуск важного шага или неоднозначная команда могут привести к разным действиям и неверному ответу. Часто кажется, что очевидный для автора шаг будет очевиден и другому, но исполнитель не обязан догадываться. Пройдите алгоритм по порядку и уточните все места, где возможен выбор без правила.
Если не проверять завершение и разные исходные данные, алгоритм может зациклиться или не сработать в отдельном случае. Обычно тестируют только самый простой пример и не замечают особых ситуаций, например равенства чисел. Проверьте, что выполнение останавливается, а результат верен на нескольких допустимых наборах данных.
Чтобы составлять алгоритмы, нужно уметь разбирать задачу: выделять её условие, исходные данные и требуемый результат. Исходные данные сообщают, с чем предстоит работать, а результат показывает, когда задача решена. Такое представление помогает не пропустить нужный шаг между началом и целью.
Понятие исполнителя связано с устройствами компьютера: каждое устройство выполняет только определённые команды. Алгоритмы станут основой для дальнейшего изучения программирования и способов записи действий. Программа позволяет представить алгоритм в форме, которую может выполнять компьютер.
Чем алгоритм отличается от обычной инструкции?
Не всякая инструкция является алгоритмом: расплывчатый совет может не подсказать, что именно делать. Алгоритм задаёт понятные и однозначные действия в определённом порядке, которые приводят к результату.
Может ли один и тот же алгоритм подходить разным исполнителям?
Да, если каждый исполнитель понимает все команды алгоритма и умеет их выполнять. Например, последовательность действий может быть доступна разным людям, но компьютер не выполнит команду, предназначенную только для человека.
Что значит, что команда понятна исполнителю?
Это значит, что исполнитель знает, какое действие нужно выполнить, и способен его выполнить. Если команда ему неизвестна или допускает разные действия, рассчитывать на правильный результат нельзя.
Почему алгоритм должен заканчиваться?
Алгоритм нужен, чтобы получить результат, а бесконечное выполнение не приводит к завершению задачи. Поэтому после конечного числа шагов исполнитель должен остановиться.
Как проверить, подходит ли алгоритм для разных исходных данных?
Проверьте его на нескольких допустимых наборах данных, в том числе на особых случаях, например на равных числах. Проследите, что каждый набор приводит к правильному результату и алгоритм завершается.
§ 1. Алгоритм
