Информатика • 11 класс

Задачи анализа алгоритмов. Доказательство верности алгоритма

Проверка правильности алгоритма часто заменяется проверкой правильности программы, то есть прогонкой её на различных тестах. Однако этот метод редко исключает все сомнения. Может существовать случай, в котором программа не сработает.
Идея математического доказательства корректности программ (верификации) обычно сводится к доказательству того факта, что программа (подпрограмма) является корректной относительно её входной и выходной спецификации.
Пример. Алгоритм описан в виде последовательности шагов: от шага 1 до шага n.
Методика правильности алгоритма:
1. предложить обоснование правомерности каждого шага (выделение инварианта);
2. провести доказательство конечности алгоритма, при этом будут проверены все подходящие входные данные и получены все подходящие выходные.

Было полезно?