Свойства алгоритма

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

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

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

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

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

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

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

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

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

Результативность означает, что выполнение должно закончиться и привести к результату. Это важно потому, что алгоритм нужен для решения задачи, а бесконечное повторение команд не даёт получить ответ. Завершение должно происходить за конечное число шагов; это число при этом может зависеть от исходных данных. Значит, проверять нужно не только наличие ответа в одном примере, но и то, предусмотрено ли завершение в ходе выполнения.

Массовость показывает, что алгоритм решает не одну задачу с уже заданными данными, а целый класс похожих задач. Это свойство делает алгоритм полезным повторно: достаточно подставить новые допустимые значения и выполнить те же правила. Например, алгоритм сложения подходит для разных пар чисел, а запись «сложи 3 и 5» описывает только один случай. Для массового алгоритма важно, чтобы его правила подходили ко всем данным из рассматриваемого класса.

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

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

Разбор задач

1. Проверяем рецепт, расплывчатую инструкцию и бесконечное повторение

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

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

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

2. Находим ошибку в команде для робота

Условие: исполнитель умеет перемещаться на одну клетку, поворачиваться на 90 градусов и закрашивать клетку. В алгоритме есть команда «перейти в удобное место»; нужно найти ошибку. Сопоставим команду с известными действиями робота и выясним, сможет ли он выбрать единственный способ её выполнить.

1. Выпишем доступные команды: шаг на одну клетку, поворот на 90 градусов и закрашивание клетки.
2. Сравним с ними спорное указание. «Перейти в удобное место» не сообщает, куда двигаться, сколько клеток пройти и как понять, что место удобное.
3. Сделаем команду точной, заменив её последовательностью допустимых действий, например: «повернуться направо, затем переместиться на одну клетку». Если требуется другое место, путь нужно описать дополнительными шагами.

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

3. Составляем алгоритм нахождения большего числа

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

1. Ввести числа a и b.
2. Сравнить a и b. Если a больше b, присвоить m значение a; иначе присвоить m значение b.
3. Вывести m и завершить выполнение.

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

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

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

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

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

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

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

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

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

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