§ 48. Как доказывают применимость алгоритма

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

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

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

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

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

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

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

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

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

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

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

Что требуется обосновать при проверке применимости алгоритма

Таблица помогает последовательно проверить основные стороны работы алгоритма. Сначала сопоставьте входы с ограничениями задачи, затем разберите действия и результат. В последнюю очередь задайте вопрос о том, почему выполнение обязательно остановится.

Разбор задач

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

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

1. Обозначим входные числа a и b, где a и b — целые числа.
2. Алгоритм выполняет одно действие: складывает a и b. Оно допустимо для заданных входов и даёт целое число a + b.
3. По определению суммы a + b является числом, которое требуется получить при сложении a и b.

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

Поиск наибольшего общего делителя вычитанием

Условие. Даны два положительных целых числа. Алгоритм вычитает меньшее из большего, пока числа не станут равны. Нужно доказать, что общее значение равно наибольшему общему делителю (НОД) исходных чисел и что алгоритм завершится. Здесь надо отдельно обосновать сохранение ответа и остановку процесса.

1. Пусть на очередном шаге числа x и y положительны. Если x больше y, заменяем x на x − y; иначе, если числа не равны, заменяем y на y − x.
2. При x > y общие делители x и y совпадают с общими делителями x − y и y: делимость разности следует из делимости обоих исходных чисел, а x можно получить как (x − y) + y. Значит, НОД не меняется; аналогично рассуждаем при y > x.
3. На каждом шаге сумма x + y уменьшается, оставаясь положительным целым числом. Она не может уменьшаться бесконечно, поэтому числа в конце станут равны.
4. Когда x = y, это число делит оба текущих числа, а все их общие делители сохранились от исходных. Следовательно, равные числа и есть НОД исходных чисел.

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

Поиск максимума массива

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

1. Первым просмотренным элементом объявим текущий максимум. После первого шага он действительно является максимумом среди первых элементов.
2. Предположим, что после просмотра k элементов текущая величина равна их максимуму. При просмотре элемента с номером k + 1 алгоритм сравнивает его с текущей величиной и сохраняет большее.
3. Значит, после этого сравнения сохранён максимум среди первых k + 1 элементов. Это свойство является инвариантом цикла: оно верно в начале и сохраняется после каждого шага.
4. Массив содержит конечное число элементов, и на каждой итерации просматривается следующий. После последнего элемента цикл завершается, а инвариант утверждает, что сохранён максимум всего массива.

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

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

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

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

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

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

• Применимость доказывают для всех входных данных из заданной области.
• Корректность означает, что алгоритм выдаёт результат, соответствующий условию задачи.
• Завершение означает выполнение за конечное число шагов.
• Проверка отдельных примеров не заменяет доказательство.
• Для циклов полезно установить инвариант и показать, что он сохраняется.
• Условия задачи определяют, для каких данных алгоритм применим.