Контрпример к алгоритму
Контрпример к алгоритму — это такие входные данные, на которых алгоритм выдаёт неверный результат, нарушает условие задачи или не может выполнить команду. Один найденный контрпример достаточно, чтобы опровергнуть утверждение о правильности алгоритма.
Чтобы доказать, что алгоритм не всегда правильный, достаточно предъявить один контрпример и объяснить, каким должен быть правильный результат. Если алгоритм состоит из команд для исполнителя, ошибкой может быть не только неправильный ответ, но и команда, которую исполнитель не может выполнить в данной среде исполнителя.
Как распознать контрпример
Сначала выбирают допустимые входные данные, затем пошагово выполняют алгоритм и сравнивают полученный результат с правильным. Полезно проверять маленькие числа, нулевые значения, одинаковые элементы и случаи, в которых меняется поведение условия. Такой тестовый пример становится контрпримером только тогда, когда обнаружена ошибка.
Алгоритм должен найти наибольшее из двух чисел, но записан так: если \(a>b\), вывести \(a\), иначе вывести \(b\). Для входа \(a=5\), \(b=3\) результат верен. Для входа \(a=3\), \(b=5\) также выводится \(5\). Если же алгоритм использует условие «если \(a\ge b\), вывести \(a\), иначе вывести \(b\)», он всё ещё работает. А алгоритм «всегда вывести \(a\)» имеет контрпример \(a=3\), \(b=5\): правильный ответ — \(5\), алгоритм выдаёт \(3\).
Граничный случай — это вход на границе допустимых значений, например \(x=0\) или \(x=1\). Он может оказаться контрпримером, но не обязан им быть. Контрпример определяется ошибкой алгоритма, а не особым положением входных данных.
Алгоритм правильно сортирует все списки, кроме списка \([2,1]\). Что это такое?
Главное
- Контрпример — допустимые входные данные, на которых алгоритм ошибается или нарушает условие.
- Для опровержения утверждения «алгоритм всегда правильный» достаточно одного контрпримера.
- Граничный случай может быть контрпримером, но сам по себе им не является.