Тестирование алгоритмов
Тестирование алгоритма — это проверка его работы на специально выбранных входных данных. Цель тестов — не только убедиться, что программа даёт правильный ответ на обычных примерах, но и обнаружить ошибки на границах диапазонов, при особых значениях и в необычных сочетаниях условий.
Что проверяет тестирование
Алгоритм считается надёжным, если он правильно обрабатывает все допустимые входные данные. Проверить буквально все варианты обычно невозможно: диапазоны могут быть большими, а количество комбинаций — огромным. Поэтому выбирают небольшое количество показательных тестов, каждый из которых проверяет определённое свойство алгоритма.
Тестовый пример — это конкретный набор входных данных с заранее известным правильным результатом. Тест состоит из входа и эталонного ответа, с которым сравнивают результат работы алгоритма.
Перед составлением тестов нужно внимательно прочитать условие и выписать ограничения: типы данных, минимальные и максимальные значения, возможное наличие нуля, повторяющихся элементов, отрицательных чисел и пустых наборов. Полезно сначала проверить корректность алгоритма на уровне идеи: понять, какой результат он должен получать и почему.
- Понять, какие входные данные допустимы.
- Определить, какой результат должен быть правильным.
- Разделить входы на типичные и особые случаи.
- Для каждого теста заранее вычислить ответ независимо от программы.
- Сравнить фактический и ожидаемый результаты.
Какие тесты выбирать
Хороший набор тестов включает разные группы данных. Один обычный пример почти никогда не доказывает правильность алгоритма: ошибка может проявляться только при нуле, на границе диапазона или при повторении элементов.
| Группа тестов | Что проверяет | Пример для массива |
|---|---|---|
| Обычный случай | Основную логику алгоритма | [3, 1, 4, 2] |
| Минимальный размер | Работу при наименьшем допустимом вводе | [7] |
| Максимальный размер | Циклы, память и время работы | Массив из максимального числа элементов |
| Граничные значения | Правильность сравнений \(<\), \(\le\), \(>\), \(\ge\) | Минимальное и максимальное число |
| Особые значения | Нули, отрицательные числа, одинаковые элементы | [0, -2, 0, -2] |
| Уже обработанный случай | Не возникает ли лишних изменений | [1, 2, 3, 4] |
| Обратный порядок | Не зависит ли решение от направления данных | [4, 3, 2, 1] |
Граничный тест особенно важен, потому что ошибки часто появляются в момент перехода через условие. Например, программа должна выбрать числа \(x \le 10\), но использует \(x < 10\). Значения \(9\), \(10\) и \(11\) позволят проверить границу с обеих сторон.
Граничный случай — входные данные, расположенные на границе допустимого диапазона или на границе изменения поведения алгоритма. Обычно проверяют саму границу и соседние значения.
Как сократить число тестов
Если несколько входов обрабатываются алгоритмом одинаковым способом, их можно объединить в класс эквивалентности. Для каждого такого класса достаточно выбрать один или несколько представителей. Подробнее этот приём описывает тестирование классов эквивалентности.
Например, условие требует вывести «да», если число \(x\) находится в диапазоне от \(1\) до \(100\) включительно. Возникают три класса: \(x<1\), \(1\le x\le100\) и \(x>100\). Минимальный набор представителей — \(0\), \(50\) и \(101\). Но для проверки границ лучше добавить \(1\), \(100\), а также соседние значения \(2\) и \(99\).
Для каждого класса входных данных выберите хотя бы один представитель, а для каждой границы — саму границу и значения по обе стороны от неё. Если результат зависит от нескольких параметров, проверяйте не только каждый параметр отдельно, но и важные их сочетания.
Набор тестов должен быть небольшим, но разнообразным. Случайные данные полезны, когда трудно придумать особые случаи, однако случайное тестирование не заменяет продуманные граничные проверки: случайный тест может никогда не попасть точно в нужную границу.
Алгоритм принимает целое \(n\) от 1 до 100 включительно. Какой набор лучше всего проверяет границы диапазона?
Как найти ошибку контрпримером
Если алгоритм кажется неверным, нужно найти вход, на котором его результат отличается от правильного. Такой вход называется контрпримером к алгоритму. Контрпример должен удовлетворять условию задачи, иначе он не доказывает ошибку в допустимой области.
Рассмотрим алгоритм, который должен найти количество положительных элементов массива. В нём используется условие a[i] >= 0. Подозрение: ноль ошибочно считается положительным.
1count := 0 2for i from 1 to n do 3 if a[i] >= 0 then 4 count := count + 1 5output count
Проверим алгоритм на массиве из одного элемента \([0]\). По определению, положительных элементов нет, поэтому правильный ответ равен \(0\). Алгоритм проверяет условие \(0\ge0\), увеличивает счётчик и выводит \(1\). Значит, найден допустимый контрпример.
Исправление — заменить условие \(a[i]\ge0\) на \(a[i]>0\). После исправления полезно повторить тесты: \([0]\), \([5]\), \([-3]\) и массив, содержащий все три типа значений.
Проверка циклов и промежуточных состояний
Ошибки в циклах часто связаны с начальным значением счётчика, последним индексом, условием продолжения или изменением переменной. Для ручной проверки составляйте таблицу состояний переменных: записывайте номер шага, значение индекса, текущий элемент и накопленный результат.
Особое внимание уделяйте алгоритмам с вложенными циклами. Нужно выяснить, сколько раз выполняется внутренний цикл для каждого значения внешнего счётчика. При анализе границ полезны также правила работы счётчика цикла и инвариант цикла — свойство, сохраняющееся после каждой итерации.
| Вопрос | Что проверить |
|---|---|
| С какого значения начинается индекс? | Не пропущен ли первый элемент |
| До какого значения идёт цикл? | Обработан ли последний элемент |
| Изменяется ли счётчик? | Не возникает ли бесконечный цикл |
| Что происходит при \(n=0\) или \(n=1\)? | Есть ли обращение к несуществующему элементу |
| Есть ли переполнение или слишком долгий перебор? | Соответствует ли решение ограничениям по времени |
Не считайте один успешный пример доказательством правильности. Не забывайте проверять пустой или минимальный ввод, если он разрешён условием. Различайте «неотрицательное» (\(x\ge0\)) и «положительное» (\(x>0\)), а также «неположительное» (\(x\le0\)) и «отрицательное» (\(x<0\)). При индексации с нуля не переносите автоматически границы циклов из решений с индексацией с единицы.
Практический порядок действий
- Выпишите входные параметры и ограничения.
- Разделите область входов на классы: обычные, граничные и особые.
- Составьте небольшие тесты для каждого класса.
- Для каждого теста вычислите правильный ответ вручную или другим способом.
- Запустите алгоритм и сравните ответы.
- Если найдено различие, уменьшайте тест: убирайте лишние элементы и значения, сохраняя ошибку.
- Запишите причину ошибки и измените алгоритм только после понимания этой причины.
Уменьшение найденного теста называют минимизацией контрпримера. Маленький контрпример легче анализировать: в нём обычно остаётся ровно та особенность, которая вызывает ошибку. После исправления выполняют повторное тестирование, включая старый контрпример и набор связанных с ним случаев.
Проверь себя
Главное
- Тестирование сравнивает результат алгоритма с заранее известным правильным ответом.
- Нужно проверять обычные, минимальные, максимальные, граничные и особые входы.
- Для границы \(b\) полезны значения \(b-1\), \(b\) и \(b+1\).
- Контрпример — допустимый вход, на котором алгоритм выдаёт неверный результат.
- Ошибки циклов ищут по индексам, условиям остановки и таблице состояний переменных.
- После исправления алгоритма повторяют старые тесты и добавляют связанные граничные случаи.