Корректность алгоритма
Корректность алгоритма — это соответствие результата работы алгоритма поставленной задаче для всех допустимых входных данных. Алгоритм может быть быстрым и удобным, но некорректным, если хотя бы на одном допустимом входе выдаёт неправильный результат или не завершается.
Что именно проверяют
У алгоритма есть входные данные, условие их допустимости и требуемый результат. Алгоритм корректен, если при любом входе, удовлетворяющем условию, он завершает работу и выдаёт именно такой результат. Проверка одного или нескольких примеров не доказывает корректность для всех входов: она только помогает обнаружить ошибки.
Здесь \(D\) — множество допустимых входных данных, \(A(x)\) — результат работы алгоритма, а \(R(x)\) — правильный результат задачи. Если алгоритм должен только определить возможность действия, результатом может быть, например, значение «да» или «нет».
Задача: вывести большее из двух чисел. Алгоритм сравнивает \(a\) и \(b\): если \(a>b\), выводит \(a\), иначе выводит \(b\). Он корректен для любых двух чисел, потому что при \(a>b\) больше \(a\), а при \(a\le b\) больше либо равно \(b\). В частности, случай \(a=b\) также обработан.
Тестирование алгоритмов запускает алгоритм на выбранных примерах и может найти ошибку, но не доказывает правильность для всех допустимых входов. Проверка алгоритма — более общее рассуждение о соответствии алгоритма условию; оно может включать доказательство, анализ инварианта или разбор всех случаев.
Алгоритм правильно решает задачу на 100 выбранных тестах. Можно ли утверждать, что он корректен для всех допустимых данных?
Главное
- Корректный алгоритм для каждого допустимого входа выдаёт требуемый результат и завершает работу.
- Корректность относится ко всем допустимым данным, а не только к проверенным примерам.
- Тестирование помогает находить ошибки, но само по себе не доказывает корректность.