- Проверка правильности алгоритма часто заменяется проверкой правильности программы, то есть прогонкой её на различных тестах. Однако этот метод редко исключает все сомнения. Может существовать случай, в котором программа не сработает.
- Идея математического доказательства корректности программ (верификации) обычно сводится к доказательству того факта, что программа (подпрограмма) является корректной относительно её входной и выходной спецификации.
- Пример. Алгоритм описан в виде последовательности шагов: от шага 1 до шага
n . - Методика правильности алгоритма:
- предложить обоснование правомерности каждого шага (выделение инварианта);
- провести доказательство конечности алгоритма, при этом будут проверены все подходящие входные данные и получены все подходящие выходные.
Информатика • 11 класс
544
Задачи анализа алгоритмов. Доказательство верности алгоритма
Было полезно?
Рекомендуем
Вы учитель или ученик?
Познакомьтесь с нашим образовательным онлайн-сервисом с тысячами интерактивных работ
Учителю
Удобно проводить уроки в классе, назначать работы на дом и анализировать результаты всего класса или конкретных учеников
Ученику
Самостоятельно изучать новые и повторять пройденные темы, готовиться по индивидуальной траектории и оценивать результаты на наглядных графиках