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

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

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

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

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

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

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

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

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

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

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

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

Этапы доказательства применимости алгоритма

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

Разбор задач

Задача 1. Для алгоритма вычисления суммы 1 + 2 + … + n докажите правильность результата и завершение цикла при натуральном n. Пусть переменная s сначала равна 0, а цикл по очереди прибавляет к ней числа от 1 до n. Нужно понять, что хранит s в ходе работы, и почему цикл не может повторяться бесконечно.

1. Выберем инвариант: после обработки числа k переменная s равна 1 + 2 + … + k. Перед первой итерацией обработанных чисел нет, поэтому s = 0 — сумма пустого набора, и начальное состояние подходит.
2. Если после k шагов в s записана сумма до k, то следующая итерация прибавляет k + 1. Получается сумма 1 + 2 + … + (k + 1), поэтому инвариант сохраняется.
3. Число необработанных значений n − k убывает на единицу и ограничено снизу нулём. Значит, цикл останавливается после обработки n чисел; тогда инвариант даёт s = 1 + 2 + … + n.

Ответ: алгоритм завершится и выдаст сумму, заданную условием. Доказаны и завершение, и корректность.

Задача 2. Докажите применимость алгоритма Евклида для нахождения НОД двух натуральных чисел a и b. Алгоритм заменяет пару (a, b) на (b, a mod b), пока второе число не станет равным нулю. Нужно обосновать, почему замена не меняет искомый НОД и почему повторения закончатся.

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

Ответ: алгоритм Евклида останавливается и возвращает НОД исходных чисел.

Задача 3. Докажите корректность и завершение двоичного поиска элемента в упорядоченном массиве. На каждом шаге сравнивают искомое значение со средним элементом и оставляют половину, в которой оно может находиться. Если совпадения нет, отрезок поиска сужают до пустого.

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

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

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

• Считать несколько удачных запусков доказательством. Примеры проверяют отдельные случаи, но не все допустимые входы; ошибку допускают, потому что много тестов создают ощущение надёжности. Проверьте себя: обосновали ли вы работу для произвольных входных данных, а не только для выбранных?
• Доказывать только правильность результата. Цикл может сохранять верный инвариант, но работать бесконечно; обычно забывают, что правильный ответ ещё нужно успеть получить. Проверьте отдельно, есть ли величина с ограниченным строгим изменением.
• Выбирать инвариант, не связанный с условием задачи. Даже истинное утверждение не поможет доказать нужный ответ, если оно описывает посторонний факт. Спросите себя, можно ли из него и условия выхода вывести результат задачи.
• Пропускать начальный случай или окончание цикла. Без проверки начала индукция не запускается, а без анализа выхода неизвестно, что означает конечное состояние. Убедитесь, что инвариант верен до первой итерации и даёт ответ вместе с условием остановки.

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

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

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

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