Тестирование показывает, что программа работает на проверенных примерах; доказательство — что на всех допустимых данных. Глава учит второму: предусловие, инвариант цикла, лимитирующая функция.
Что нужно знать
- Предусловие описывает допустимые входные данные, постусловие — требуемый результат.
- Алгоритм применим к данным, если на них он завершается и выдаёт результат. Зацикливание означает неприменимость.
- Инвариант — условие, истинное перед каждым повторением цикла. Для суммы первых элементов: «s равна сумме уже просмотренных».
- Лимитирующая функция убывает при каждом повторении и ограничена снизу; её существование доказывает, что цикл завершится.
- Порядок доказательства: инвариант верен до цикла, сохраняется шагом, вместе с условием выхода даёт постусловие; отдельно — конечность.
- Переменная, уменьшающаяся вдвое от 64 до 1, проходит 6 повторений.
- Несколько удачных примеров не доказывают правильности: ошибка может сидеть в непроверенном случае.
Где чаще всего ошибаются
- Считают прохождение тестов доказательством.
- Берут инвариантом условие, верное только в конце.
- Насчитывают 7 повторений, считая исходное значение шагом.
- Забывают доказать конечность цикла.
Проверить себя
По этой же главе есть проверочная работа из 11 заданий на 25 минут. Проверка автоматическая, результат виден сразу — и по работе целиком, и по каждой теме.
Информатика · 11 класс · Гейн, 2023 · Глава 10 · Исследование алгоритмов математическими методами