Материалы сайта
Это интересно
Нахождение опорного плана транспортной задачи
5.1 Тестирование программ Тестирование алгоритмов и программ -- одна из наиболее сложных и ответственных задач в процессе их отладки. Времени для тестирования мало, но и спешка в работе недопустима, слишком дорого обходятся неудачные попытки предъявить решение задачи. Проверка корректности алгоритмов, равно как и составление авторами задачи достаточно полного набора корректных тестов -- наборов данных для задачи и ответов к ним -- далеко не всегда представляют собой простую проблему. В задачах на этапе тестирования программ есть много общего -- и те и другие должны обеспечить корректность алгоритмов. Но есть и различия. Автор задачи не ограничен во времени, но должен предусмотреть все возможные огрехи участника. Специфика положения тестирующего, связана с коварством составителя тестов, от которого можно ожидать, например, непредвиденной глубины рекурсии, разрядности, точности вычислений или размерности наборов данных. Поэтому будет неправильно, успешно решив задачу для нарисованного на листочке бумаги примера. Будьте внимательны! Всегда есть опасность получить по существу правильный, но не тот ответ. Кроме того, способ описания ответа может послужить намеком на используемый автором алгоритм решения задачи. Проверка алгоритма на данных максимальной установленной размерности: по количеству перечисленных в условиях задачи объектов, по количеству связей между ними, по разрядности и точности машинного представления числовых параметров и пр. Такая проверка нужна для выявления и отсева неэффективных - медленно работающих или нерационально использующих память программ. Известны случаи, когда, в принципе, правильно работающий алгоритм приводил к ошибочному ответу из-за ошибок переполнения -- в условиях задачи оговаривается диапазон или разрядность исходных данных, но не разрядность промежуточных результатов или ответа. Типичным примером грубой ошибки такого рода может служить нахождение опорного плана транспортной задачи. Проверка работоспособности алгоритма в вырожденных случаях: срабатывание пустого или состоящего из единственного элемента цепного списка, работа программы с графом, не содержащим дуг и т.п. В некоторых случаях, например, при декомпозиции задачи, когда решение задачи сводится к решению задачи меньшей размерности переход от начального i=0 уменьшением на единицу может привести к непредусмотренному эффекту выхода за границы зарезервированной памяти. Результат работы на нижней границе размерности легко просчитывается, иногда он будет получен как и в общем случае, иногда удобней вручную просчитать его и предусмотреть особую ветку программы, но никогда о нем не следует забывать. Следует иметь ввиду, что построение авторами заданий тестов, особенно, значительной размерности представляет собой непростую задачу. Возможно несколько подходов к построению тестов. 1. Составление тестов вручную. Это возможно, когда решение задачи не представляет собой вычислительной сложности (вся сложность -- логическая). Задача "Путь на кубе" раздела "Геометрия" -- пример именно такой задачи. Во всех остальных случаях подобный путь тупиковый. У участников олимпиады иногда выбора нет, но не забывайте проверить случаи вырожденной и максимальной размерности хотя бы в тривиальном варианте (матрица из нулей и единиц не содержит нулей или единиц, в ней единственная строка или единственный столбец, в графе нет дуг, или граф полный). 2. Применение случайных чисел. Такие генераторы тестов удобно конструировать для числовых последовательностей, матриц или графов. Достаточно задать один -- два параметра настройки датчика случайных чисел и в вашем распоряжении замечательные тесты. При построении матрицы из 0-1 таким параметром будет доля единиц среди элементов матрицы, координаты очередной единицы определяются в результате испытания с равномерным распределением среди элементов этой матрицы, при построении графа -- среднее число дуг, выходящих из вершины. ----------------------- Лист Кп-км-п-44-2203-99 Лист Кп-км-п-44-2203-99