Исследование алгоритмов математическими методами — тест

Программа может пройти сотню тестов и всё равно содержать ошибку. Доказательство правильности отличается от тестирования тем, что охватывает сразу все случаи.

Что проверяется

Уточнение понятия алгоритма: недостаточность интуитивного определения, формальные модели вычислений, исполнитель и система команд, применимость алгоритма к данным. Доказательство применимости алгоритма: что значит «алгоритм применим», как показать, что он завершается на любых допустимых данных, и как построить пример, на котором он не применим. Лимитирующая функция: величина, убывающая при каждом повторении цикла и ограниченная снизу; её роль в доказательстве завершения работы. Инвариант цикла: условие, истинное перед началом цикла и сохраняющееся после каждого повторения; выбор инварианта, проверка сохранения, вывод о результате из инварианта и условия выхода. Предусловие и постусловие программы, схема доказательства правильности: применимость плюс верный результат. Сравнение доказательства и тестирования, оценка числа шагов алгоритма.

Инвариант и лимитирующая функция вместе

Инвариант отвечает за то, что результат верен, лимитирующая функция — за то, что цикл вообще закончится. Ни одного из этих доводов по отдельности недостаточно.

Применимость — не то же, что правильность

Алгоритм может завершаться на всех данных, но давать неверный ответ, и наоборот — давать верный ответ, но зацикливаться на части входов. Проверять нужно оба свойства.

Как устроена работа

Одиннадцать заданий: выбор варианта, соответствие между понятием и его ролью в доказательстве, восстановление пропусков, упорядочивание шагов доказательства правильности цикла и подсчёты числа шагов алгоритма. Разбор к каждому заданию показывает ход рассуждения. Работа рассчитана примерно на двадцать пять минут, отметка выставляется по шкале пятьдесят, семьдесят и восемьдесят пять процентов. Отдельные вопросы посвящены выбору лимитирующей функции и границам тестирования.

Как проходит работа

Тест можно выполнять как за компьютером или ноутбуком, так и со смартфона или планшета — устанавливать ничего не нужно, достаточно браузера. Учитель может задать период, в течение которого доступен тест, поэтому его допустимо выполнять и дома. Встроенная защита от списывания отмечает, когда учащийся уходит со страницы теста в другие окна или программы.