Анализ и тестирование алгоритмов

Результаты труда программиста

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

А что является итогом труда программиста? Предположим, в результате действия программы Робот выполнил какую-то полезную работу. Можно ли считать, что ее сделал программист? Нет, ее выполнил Робот. Может быть, программист управлял Роботом? Нет, этим занимался компьютер. Получается, что, хотя без программиста работа была бы невозможна, непосредственного участия в ней он вроде бы не принимает.

Результат работы программиста — это текст написанной им программы (алгоритма).

Что такое правильный алгоритм

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

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

Однако значительно чаще бывает так, что задано только общее описание начальных условий, а точная ситуация неизвестна. С такими задачами мы встречались в §10—11. Правильно составленный алгоритм должен работать в любой ситуации, соответствующей условию.

Как проверить такой алгоритм? Конечно, для конкретной ситуации его можно исполнить и убедиться, что он работает (или не работает, тогда нужно искать ошибку). Но разных ситуаций может быть очень много, перебрать их все просто невозможно. Даже в простейшей задаче о движении Робота до стены (§10) количество ситуаций теоретически бесконечно — ведь расстояние до стены может быть любым.

Такая ситуация возникает не только с алгоритмами. Невозможно, например, перебрать все существующие треугольники, но доказав, что сумма углов треугольника всегда равна 180°, мы будем использовать это свойство для любого треугольника без дополнительной проверки. Такой прием очень распространен в математике: если какое-то свойство удается доказать, то потом его используют без дополнительных проверок.

Точно так же можно поступать и с алгоритмами. Если доказать, что алгоритм правильный, то нет необходимости проверять его отдельно для каждой ситуации.

А что такое правильный алгоритм? Интуитивно мы понимаем это, но для доказательства нужны четкие формулировки.

Правильность алгоритма означает, что для любой допустимой (соответствующей условию дано) начальной ситуации:

1) при выполнении алгоритма не может возникнуть отказ;

2) при выполнении алгоритма не может возникнуть зацикливание;

3) после завершения алгоритма будет достигнут правильный (соответствующий условию надо) результат.

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

 

Пример рассуждения, подтверждающего правильность алгоритма

алг вправо до стены

дано | где-то справа от Робота на расстоянии есть стена

надо справа стена | Робот подошел к стене

нач

нц пока справа свободно

| вправо

Кц

Кон

Докажем правильность этого алгоритма (для краткости мы будем пользоваться словом «докажем», не оговаривая каждый раз, что доказательство не является математически строгим).

1) При выполнении этого алгоритма невозможен отказ.

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

2) При выполнении этого алгоритма невозможно зацикливание.

По условию стена справа от Робота есть. При каждом выполнении цикла Робот делает один шаг вправо, в результате расстояние до стены уменьшается на 1. Когда-нибудь это расстояние станет равным 0 и цикл, а вместе с ним и алгоритм, завершится.

3) После завершения алгоритма условие в надо обязательно выполняется.

Это следует из свойства цикла пока: после завершения цикла его условие не может быть верным.

Тестирование алгоритмов

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

Чтобы проверить алгоритм, его надо исполнить и сравнить результат с тем, который требуется получить. При этом несовпа­дение результатов означает, что в алгоритме есть ошибки, а вот совпадение... Совпадение не значит ничего! Ведь алгоритм должен давать правильный результат для любой начальной ситуации, поэтому нельзя делать выводы после одной проверки.

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

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

Пример 1. Где-то справа от Робота есть стена. Крайний случай — Робот уже у стены.

Пример 2. Робот где-то в коридоре. Крайние случаи — Робот в крайней левой клетке коридора; Робот в крайней правой клетке коридора; Робот в коридоре из одной клетки.

Пример 3. Некоторые клетки коридора закрашены. Крайние случаи — закрашенных клеток нет; закрашена ровно одна клетка; закрашены все клетки коридора.

Задача 1. Дан фрагмент алгоритма:

нцпока справа свободно

вправо

если клетка закрашена

то влево

иначе вверх

Все

кц

Придумайте ситуации, в которых при выполнении этого фрагмента:

а) произойдет отказ;

б) произойдет зацикливание;

в) компьютер не даст Роботу ни одной команды-приказа;

г) компьютер даст Роботу ровно одну команду-приказ;

д) компьютер даст Роботу ровно две команды-приказа.

■ Решение, а) Из всех команд данного фрагмента отказ возможен только при выполнении команд движения Робота. Этих команд во фрагменте три.

Команда вправо выполняется только при соблюдении условия цикла "справа свободно", значит, при ее выполнении отказ невозможен.

Команда влево выполняется сразу после команды вправо. Если Робот смог пройти вправо, он сможет и вернуться обратно. Значит, и здесь отказ невозможен.

А вот команда вверх никак не защищена, при ее выполнении отказ действительно может случиться. Это произойдет, если, шагнув вправо, Робот попадет на чистую клетку, выше которой расположена стена (рис. 33, а).

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

в) Робот не получит команд-приказов, если условие цикла с самого начала не будет выполнено, т. е. в начальном положении справа от Робота будет находиться стена (рис. 33, в).

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

д) Приказов будет ровно два, если цикл будет выполнен один раз. Соответствующая ситуация изображена на рисунке 33, г.

 

Рис. 33

 

Задача 2. Что можно сказать о правильности такого фрагмента:

нцпока клетка закрашена

если справа свободно

| то вправо;закрасить

Все

кц

■ Решение. На первый взгляд задание бессмысленно: что можно сказать о правильности фрагмента, если неизвестно, какую задачу он должен решать?

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

Посмотрим внимательно на приведенный фрагмент. Если тело цикла будет исполнено хотя бы один раз, то обязательно произойдет зацикливание! В самом деле, если справа от Робота свободно, то он перейдет на новую клетку и закрасит ее, после чего условие цикла "клетка закрашена" будет заведомо верным. Если же справа от Робота стена, он останется в той же клетке.

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

ЗАДАЧИ И УПРАЖНЕНИЯ

1. Дан фрагмент алгоритма:

если клетка чистая

то

нц пока справа свободно

I закрасить; вправо

кц

иначе влево

Все

Придумайте ситуации, в которых при выполнении этого алгоритма:

а) произойдет отказ;.

б) произойдет зацикливание;

в) Работ не получит ни одного приказа;

г) Робот получит ровно два вопроса;

д) Робот получит нечетное число приказов.

2. Составьте набор тестов для проверки решения задач 7 и 9 из § 10.

3. Составьте набор тестов для проверки решения задач 4 - 6 из § 11.

4. Робот находится внутри прямоугольника, с четырех сторон огороженного стенами. Внутри прямоугольника стен нет. В левой вертикали закрашены некоторые клетки. Закрасить соответствующие им клетки в правой вертикали.

5. Робот находится внутри прямоугольника, с четырех сторон огороженного стенами. Внутри прямоугольника стен нет. Некоторые клетки в прямоугольнике закрашены. Закрасить горизонтальные ряды, в которых:

а) закрашена левая клетка;

б) закрашены левая и правая клетки;

в) закрашены левая и правая клетки и еще хотя бы одна;

г) закрашены левая и правая клетки и еще ровно одна;

д) есть хотя бы одна закрашенная клетка;

е) есть ровно одна закрашенная клетка;

ж) есть хотя бы две закрашенные клетки;

з) есть ровно две закрашенные клетки;

и) четное число закрашенных клеток;

к) нечетное число закрашенных клеток.

6. Робот находится внутри прямоугольника, с четырех сторон огороженного стенами. Внутри прямоугольника стен нет. Одна клетка в прямоугольнике закрашена.

а) Составить алгоритм, приводящий Робота в закрашенную клетку.

б) Закрасить горизонталь и вертикаль, на пересечении которых расположена эта клетка.

7. Робот находится внутри прямоугольника, с четырех сторон огороженного стенами. Внутри прямоугольника нет стен и закрашенных клеток. Закрасить часть клеток так, чтобы оставшиеся образовали квадрат максимально возможных размеров (рис. 34).

8. Робот стоит на поле без стен.

а) На поле две закрашенные клетки — одна где-то правее Робота, другая — где-то выше Робота. Закрасить прямоугольник с вершинами в этих клетках (рис. 35).

б) Где-то правее Робота есть закрашенная клетка. Закрасить квадрат с вершинами в этой клетке и в клетке начального положения Робота (рис. 36).

9. Робот находится внутри прямоугольника, с четырех сторон огороженного стенами. Внутри прямоугольника стен нет. Закрасить клетки прямоугольника в шахматном порядке.

10. Робот помещен внутрь прямоугольника, с четырех сторон огороженного стенами. Внутри прямоугольника стен нет, некоторые клетки закрашены. Закрасить горизонтали и вертикали всех закрашенных клеток.

 

Рис. 34 Рис. 35 Рис. 36