Костюк - Основы программирования

21

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

Пример 1.6. Пусть проводится бумажное тестирование для алгоритма (1.7) на те­ сте № 1 из табл. 1.1. Для отслеживания изменений переменных построим табл. 1.5.

Таблица 1.5

Отрицательное число под квадратным корнем фиксирует ошибку.

Конец примера.

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

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

Все эти средства позволяют локализовать ошибку, но не могут ответить на во­ прос, в чем ее причина. А вот поиск истинной причины ошибки бывает непростым делом, нередко для этого требуется полностью переосмыслить алгоритм. Как раз здесь больше всего сказывается квалификация и опыт программиста: бывает, то, на что у начинающего программиста уходит несколько дней, у профессионала занимает несколько минут. При устранении ошибки также сказывается квалификация програм­ миста, так как иногда для этого приходится полностью переписывать весь алгоритм. И это еще не все: после внесения любых исправлений в программу нет никакой га­ рантии, что в ней не появились другие (новые!) ошибки. Поэтому необходимо прове­ сти повторное тестирование программы даже на тех тестах, которые ранее давали правильные результаты.

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

Тем не менее, полной гарантии, что в отлаженной программе отсутствуют ошиб­ ки, нет: закон Э.Дейкстры верен!

22

Вопросы и задания

1.Какими свойствами должен обладать алгоритм? В чем смысл этих свойств?

2.Для чего необходим специальный язык программирования?

3.Что такое синтаксическая и что такое семантическая ошибка в алгоритме? Как и когда они обнаруживаются?

4.Почему невозможно, как правило, исчерпывающее тестирование?

5.В чем состоит цель тестирования?

6.Почему тестированием нельзя доказать отсутствие ошибок в программе?

7.Что такое множество входов, множество выходов, область входов и область выходов в ал­ горитме?

8.Как область входов и область выходов делятся на подобласти эквивалентности?

9.Как тестировать алгоритм по методу черного ящика для данных большой размерности?

10.Как выбирать тесты по методу белого ящика для последовательного, ветвящегося и цик­ лического алгоритма?

11.Как выбрать тесты по методу белого ящика для алгоритма, состоящего из последователь­ ности k ветвящихся алгоритмов (if-then-else)?

12.Как выбрать тесты по методу белого ящика для алгоритма, состоящего из последователь­ ности k циклических алгоритмов (while-do)?

13.В чем состоит задача отладки?

14.Как выполнять пошаговое тестирование?

15.Что делать, если ошибка в выходных данных обнаружена при работе алгоритма на тесте очень большой размерности?

16.Алгоритм вычисляет максимальное значение среди массива целых чисел. Разработать те­ сты по методу черного ящика.

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

18.Алгоритм возводит целое число n в целую степень m и выдает результат, присваивае­ мый переменной типа integer. Разработать тесты по методу черного ящика. Каков бу­ дет результат при n = 8 и m = 5?

19. Написать алгоритм, возводящий целое число n в целую степень m. Разработать тесты по методу белого ящика.

20.Написать алгоритм, который вводит три вещественных числа, проверяет, может ли суще­ ствовать треугольник со сторонами, равными этим числам. Если не может, то выдает со­ общение об этом и просит ввести данные повторно. Если может, то вычисляет и выводит площадь треугольника. Оформить алгоритм в виде программы на Паскале. Разработать те­ сты по методу черного ящика и по методу белого ящика, протестировать программу на объединенных тестах.

21.Написать программу, которая вводит размер n массива X, (n≤10000) генерирует слу­ чайные целочисленные значения в массиве X, после чего выполняет алгоритм (1.8) (упо­

Глава 2 Доказательство правильности алгоритмов

2.1 Принципы аналитического доказательства

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

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

Доказательство правильности содержит два этапа:

1)доказательство завершимости алгоритма, т.е. доказательство того, что при любых значениях переменных на входе алгоритма он когда-нибудь обязательно за­ кончит свое выполнение;

2)доказательство истинности постусловия после завершения алгоритма при предположении истинности предусловия перед исполнением алгоритма.

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

Доказательство завершимости нередко бывает очевидным, если, например, алго­ ритм состоит из последовательности присваиваний или из цикла for. Если же пере­

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

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

25

1)последовательное перечисление выполняемых действий, применяется для по­ следовательных алгоритмов, когда по ходу исполнения операторов отслеживают из­ менение логических соотношений;

2)перечисление вариантов, применяется для ветвящихся алгоритмов, когда вся область значений переменных, входящих в предусловие, разбивается на подобласти,

идля каждой подобласти доказательство проводится отдельно;

3)метод математической индукции, применяется для циклической структуры алгоритма, этот метод является стандартным для математических доказательств;

4)инвариант, также применяется для циклической структуры алгоритма, когда из предусловия и постусловия выделяется общая, неизменяемая часть;

5)метод эквивалентов используют, когда есть два разных алгоритма с одина­ ковыми пред- и постусловиями, и для доказательства правильности второго алгорит­ ма доказывают правильность первого алгоритма и эквивалентность первого и второ­ го алгоритмов;

6)абстракция, применяется при доказательстве сложных алгоритмов, когда не­ возможно провести доказательство сразу для всего алгоритма.

Применение различных методов доказательства рассмотрим на нескольких про­ стых примерах.

Пример 2.1.

Пусть для числовых переменных x,y выполнено предусловие x=a, y=b, где a, b – некоторые числовые значения. В записи условия запятая подразумевает логи­ ческую связку "и". Требуется доказать, что после выполнения алгоритма (2.1):

будет справедливым постусловие x=b, y=a.

Доказательство. Завершимость алгоритма очевидна. Доказательство истинности постусловия проведем последовательным перечислением выполняемых действий. После первого присваивания текущее условие: x=a, y=b, z=b, после второго: x=a, y=a, z=b, после третьего: x=b, y=a, z=b, что и требовалось доказать.

Конец примера.

Пример 2.2. Пусть для числовых переменных x,y выполнено предусловие x=a, y=b, где a, b – некоторые числовые значения. Требуется доказать, что после выполнения алгоритма (2.2)

26

будет справедливым постусловие x≥y.

Доказательство. Завершимость алгоритма очевидна. Доказательство проведем перечислением двух вариантов:

1)x≥y; условие оператора if будет ложным, поэтому больше никаких дей­ ствий в алгоритме выполняться не будет; из этого условия и предусловия следует справедливость постусловия;

2)x<y; условие оператора if будет истинным, поэтому в алгоритме будут вы­

полнены присваивания, в результате которых, как доказано в примере 2.1, перемен­ ные x и y обменяются своими значениями, что приведет к смене условия x<y на противоположное, т.е. на x≥y.

Конец примера.

Доказательство правильности – мощное средство для обнаружения ошибок в ал­ горитме. Предположим, что алгоритм (2.1) записан в виде двух присваиваний: x:=y; y:=x. Тогда после первого присваивания: x=b, y=b, после второго ниче­ го не изменилось: x=b, y=b. Последнее условие не совпадает с требуемым посту­ словием, т.е. в алгоритме ошибка!

А теперь рассмотрим метод математической индукции. Метод позволяет доказы­ вать утверждение, зависящее от параметра индукции – некоторой целочисленной переменной. Утверждение доказывается для всех значений параметра, бóльших или равных некоторому начальному значению.

Доказательство методом математической индукции содержит три этапа: 1) базис, 2) предположение, 3) индуктивный вывод.

На этапе базиса проверяют, что доказываемое утверждение P(n) относительно параметра индукции n справедливо при n = n0.

На втором этапе делается предположение, что утверждение P(n) справедливо для всех значений n, не бóльших, чем некоторое k, k ≥ n ≥ n0.

Наконец, на этапе индуктивного вывода доказывается, что P(n) будет спра­ ведливо при n = k + 1 > n0. Из этого следует, что утверждение P(n) справедливо для

любого n ≥ n0.

Покажем это для n = M, таком, что M > n0. Вначале положим k = n0. Согласно третьему этапу доказательства утверждение будет справедливо при n = n0 + 1. При­ менив еще раз третий этап доказательства при n = n0 + 1, получим справедливость утверждения P(n) при n = n0 + 2 и т.д., пока не дойдем до n = M.

Метод математической индукции широко используется в математике для доказа­ тельства самых разных логических утверждений. Рассмотрим несколько различных примеров его применения.

Пример 2.3. Докажем, что для вычисления суммы квадратов чисел от 1 до n: S = 12 + 22 + … + n2

27

справедлива формула

Доказательство.

Базис. При n = 0 сумма Sn = 0, с другой стороны, при n = 0 формула (2.1) вер­

на.

Предположение. Пусть при n ≥ 0 формула (2.1) верна. Вывод. При n + 1 по формуле (2.1) получаем:

Конец примера.

Проиллюстрируем применение метода математической индукции на примере ал­ горитма вычисления факториала.

Пример 2.4. Пусть выполнено предусловие n=M, M≥1. Требуется доказать, что после выполнения алгоритма (2.3) будет справедливо постусловие:

f=1*2*...*M.

перед выполнением цикла присваивается 2, а при каждом исполнении цикла она уве­ личивается на 1. Поэтому через n-1 исполнение цикла переменная i будет равна n+1, и условие в заголовке цикла станет ложным. Справедливость постусловия до­

кажем методом математической индукции.

Базис. Если M=1, то переменная f будет равна 1, так как цикл ни разу не будет

выполняться. Таким образом, базис справедлив.

Предположение. Предполагаем, что при M=k, k≥1 справедливо постусловие

f=1*2*...*k.

Индуктивный вывод. Все отличие выполнения алгоритма при M=k+1 от выпол­ нения при M=k состоит в том, что вначале алгоритм выполнится в точности так же, как при M=k, а затем цикл будет исполнен еще один раз для i=k+1. Так как по предположению, перед последним выполнением цикла f=1*2*...*k, то после по­ следнего выполнения цикла (после исполнения оператора f:=f*i) переменная f будет равна f=1*2*...*k*(k+1)=1*2*...*M, что и требовалось доказать.

Конец примера.

28

Метод доказательства с помощью инварианта состоит в следующем. Пусть предусловие записано как (P and Q), а постусловие – как (S and Q), т.е. в них имеется общая часть Q, называемая инвариантом. Доказательство состоит в про­ верке истинности инварианта после выполнения алгоритма. Обычно инвариант при­ меняют при доказательстве правильности оператора цикла. При этом требуется дока­ зать, что однократное исполнение цикла сохраняет истинность инварианта. Тогда, с учетом завершимости цикла, будет следовать истинность инварианта после завер­ шения цикла. Вообще говоря, строгое доказательство корректности самого метода инварианта можно провести методом математической индукции, но так как это дока­ зательство тривиально, мы его оставим в качестве упражнения.

Рассмотрим применение инварианта на предыдущем примере.

Пример 2.5. Пусть выполнено предусловие n=M, M≥1. Требуется доказать, что после выполнения алгоритма (2.3) будет справедливым постусловие:

f=1*2*...*M.

Доказательство. Завершимость алгоритма доказана в примере 2.4, отметим лишь, что после окончания выполнения цикла i=n+1.

После выполнения присваиваний в первой строчке алгоритма предусловие для оператора цикла станет таким: n=M, M≥1, i=2, f=1. Последнее равенство запи­ шем в виде: f=1*...*(i-1). Постусловие запишем в виде: n=M, M≥1, i=n+1, f=1*...*(i-1). Первые два равенства в постусловии очевидны (n и M не изменяются), справедливость равенства i=n+1 была доказана. Осталось доказать справедливость последнего равенства f=1*...*(i-1), которое здесь и является

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

Конец примера.

Самое главное в доказательстве методом инварианта – умение формулировать условие в виде инварианта, что требует некоторого навыка. В то же время использо­ вание инварианта обычно упрощает доказательство алгоритма.

Применение метода эквивалентов будет рассмотрено в разделе 2.2, а метода аб­ стракции для доказательства правильности сложных алгоритмов – в разделе 2.3.

На практике аналитическое доказательство не заменяет, а дополняет компьютер­ ное тестирование. Имеется ряд причин, по которым нельзя ограничиться только ана­ литическим доказательством.

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

29

Во-вторых, при выполнении реального алгоритма на компьютере трудно заранее учесть все нюансы взаимодействия алгоритма со стандартными программами и опе­ рационной системой.

В-третьих, в доказательстве могут быть ошибки!

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

2.2 Доказательство правильности простых алгоритмов

Рассмотрим правила построения пред- и постусловий для основных типов струк­ тур алгоритмов и операторов языка программирования. Обозначим через S некото­ рый алгоритм, через P – предусловие, а через R – постусловие для него. Сокращен­ но мы это будем записывать так:

Присваивание. Если имеется некоторое условие P(x), в запись которого входит переменная x, то

где P(w) есть то же самое условие, что и P(x), в котором каждое вхождение пере­ менной x заменено правой частью присваивания w.

Последовательный алгоритм. Если S1 и S2 – операторы, для которых выпол­ няются условия

Циклический алгоритм. Если S – оператор, для которого выполняется условие

Условие P здесь является инвариантом цикла.

Правильность рассмотренных соотношений следует из смысла операторов языка Паскаль. Применение правил (2.2) – (2.10) полезно при выводе пред- и постусловий для рассмотренных операторов.

А теперь рассмотрим применение метода эквивалентов. Для алгоритмов эквива­ лентность можно доказывать относительно некоторых, общих для обоих алгоритмов переменных.

Пример 2.6. Докажем эквивалентность алгоритмов (2.3) и (2.4) относительно

Доказательство. Вначале докажем, что циклы в обоих алгоритмах выполнятся одинаковое число раз. Для алгоритма (2.4) цикл for при границах изменения пара­ метра цикла от 2 до n≥0 исполнится ровно n-1 раз. Для алгоритма (2.3) до выпол­ нения цикла i=2, а при каждом выполнении после всех других действий в конце цикла i увеличивается на единицу. Поэтому цикл закончится после того, как i=n+1, т.е. цикл проработает также n-1 раз.

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

Легко доказать методом математической индукции, что тогда при любом (одинако­ вом для обоих алгоритмов) значении n переменные f также будут иметь одина­

ковые значения.

Конец примера.

Рассмотренный пример является частным случаем эквивалентности операторов цикла while и for. Рассмотрим общие случаи эквивалентности.

Эквивалентность последовательной структуры алгоритма. Если S1 и S2 – алгоритмы, в которых используются различные переменные, то эквивалентны по­ следовательности

Эквивалентность операторов цикла. Если S – оператор, не изменяющий пере­ менную i, то эквивалентны циклы