Проверка правильности алгоритмов
Цель создания любого алгоритма – выполнение некоторых вычислений. При этом требуется, чтобы алгоритм при допустимых значениях входных параметров вычислял верные значения на выходе. Как убедиться, что результат будет правильным при любых допустимых входных значениях? Вопрос о правильности алгоритмов – один из основных вопросов программирования как науки о составлении алгоритмов.
Актуальность вопроса можно проиллюстрировать на таком примере: пусть вероятность того, что алгоритм, занимающий 1 страницу текста, верен, равна 0.9 (из 10 операторов 1 неверный, для начинающих программистов правильнее было бы 9 из 10). Для алгоритма, занимающего 2 страницы – 0.92=0.81, 3 страницы – 0.93 и т.д. Для современных ЭВМ часто длина программы ≈ 100 страниц. Вероятность правильной работы при этом 0.9100=0.000027 – ничтожно мала.
Говорят, что ошибки в программах появились раньше, чем сами машины. Можно выделить три источника ошибок.
· “Описки”, то есть ошибки, появившиеся из-за невнимательности и незначительных нарушений синтаксиса языка.
· Алгоритмические ошибки. Возникают из-за неправильного понимания сути алгоритма или неправильного выражения мыслей. Это более серьезные ошибки.
· Ошибки, возникающие при работе с такими значениями данных, на которые не рассчитана программа. То есть ошибки из-за неправильных данных. Например, 20! – слишком большое число, 1/(20!) – слишком маленькое. Такие ошибки нужно предвидеть.
|
|
|
Методы борьбы с различными группами ошибок различны.
Большая часть “описок” обнаруживается на этапе перевода (автоматического) нашего алгоритма в команды ЭВМ – на так называемом этапе трансляции.
Другая часть «описок», а также некоторые алгоритмические ошибки, может быть найдена путем тестирования. Исторически первым методом проверки правильности алгоритма (программы) явилось тестирование: программа вводится в ЭВМ с заранее подобранными входными данными, и полученные результаты сравнивают с заранее известными правильными результатами (подсчитанными для этих входных данных вручную). Это – тест (проверяющая задача): алгоритм + данные + контрольный пример. Такое тестирование желательно повторить несколько раз.
Если результат совпадает с известным, это дает некоторые основания считать программу верной. Даже при хорошем тестировании в программе могут остаться ошибки. Для того, чтобы рассеять все сомнения, нужно выполнить все возможные варианты (то есть провести расчет со всеми возможными входными данными).
На основе подобных рассуждений Э. Дейкстра (голландский профессор, классик современного программирования) сформулировал такой закон (закон Дейкстры): тестированием можно обнаружить ошибки в программе, но никогда нельзя доказать их отсутствие.
|
|
|
Чтобы убедиться в правильности программы, отсутствии в ней алгоритмических ошибок, нужно уметь проверять правильность структуры алгоритма. Такая аналитическая проверка называется верификацией алгоритма. При использовании этого метода нужно для каждого алгоритма и каждой фразы в нем абстрагироваться от индивидуальных значений переменных и сформулировать условия, которым они должны удовлетворять до и после выполнения алгоритма. Для любого алгоритма можно определить, каким условиям должны удовлетворять входные данные и результат. Это условия подобные тем, которые задаются в операторах IF и WHILE.
Условие на входе называется предусловием, на выходе – постусловием.
Задача состоит в том, чтобы доказать, что входное предусловие алгоритм за конечное число шагов переводит в постусловие.
Наиболее распространенными методами доказательства являются:
· перечисление (перебор вариантов) – для IF-THEN-ELSE и последовательных алгоритмов;
· математическая индукция – для WHILE-DO.
Проиллюстрируем использование метода перебора вариантов на примере алгоритма дихотомии. Входные данные: C, D, EPS. (функция f – фиксирована и не относится к входным данным).
|
|
|
Предусловие:
(D>0) AND (EPS>0) AND (f (C-D)*f (C+D) ≤ 0). (*)
Постусловие:
(D <= EPS) AND (EPS >0) AND (D>0) AND (f (C-D)*f (C+D) ≤ 0). (**)
Требуется доказать, что алгоритм, имеющий на входе условие (*) на выходе получит условие (**).
Алгоритм:
while d>eps do
Begin
if f (c)*f(c+d) >0
then c:=c-d/2
else c:=c+d/2;
d:=d/2
end;
Пусть выполняется условие
f (C)*f (C+D) >0. (2)
Тогда в результате одного выполнения цикла получим новые значения Cнов и Dнов:
Cнов = C - D/2,
Dнов = D/2.
Проверим постусловие:
f (Cнов- Dнов)*f (Cнов+ Dнов) = f (C-D/2-D/2)* f (C-D/2+D/2) =
=f (C-D)*f (C)≤0 (из (*) и (1)). (3)
Таким образом мы доказали, что внутри цикла действует предусловие
(f (C-D)*f (C+D)≤0) AND (D>0)
и такое же постусловие. Доказательство провели методом перебора вариантов.
Выберите второй вариант условия f (C) *f (C-D) ≤0 и докажите то же самое.
Доказательство по методу математической индукции строится на переборе вариантов, зависящих от некоторого натурального числа n, где n=n0, n0+1, n0+2,…,∞.
Пусть P(n) – некоторое проверяемое условие.
Схема метода математической индукции:
· непосредственной подстановкой проверяем, что P(n0) выполняется;
· предполагаем, что P верно для некоторого n=k, k≥n0;
|
|
|
· доказываем, что из предположения п.2) следует, что P будет верно для n=k+1.
Пример.
Докажем, что вычисление по рекуррентной последовательности f (0) = 1,
f (n) = f (n-1)*n,
где n>0, даст в результате значение f(n)=n!.
f (0) =1 0! = 1 - выполняется.
предполагаем, что f (k) = k!
убедимся, что из п.2 следует f (k+1) = (k+1)!
Действительно, f (k+1) = f (k)*(k+1) = k!*(k+1) = (k+1)!, что и требовалось доказать.
Для циклических алгоритмов под величиной n обычно понимают количество повторений цикла. В частном случае оно может быть равно нулю.
Ценность методов верификации состоит в том, что мы получаем доказательство правильности для всего комплекса допустимых значений данных. При этом успех методов зависит от того, насколько правильно и полно мы задали пред- и постусловия.
Для доказательства правильности больших алгоритмов разбиваем их на части и для каждой части формулируем пред- и постусловия. Постусловие для одной части является предусловием для следующей. Доказываем правильность алгоритма в целом, затем - отдельно для каждого внутреннего алгоритма.
Ошибки из-за неправильных данных представляют собой совокупность таких входных данных, при которых программа неработоспособна. Для избежания таких ошибок целесообразен следующий подход.
На входе программы делаются специальные проверки на правильность данных. Затем либо выдаётся сообщение о том, что данные неверны, либо проводятся вычисления. Схема такой проверки выглядит следующим образом.
IF данные верны THEN выполнить алгоритм ELSE выдать сообщение о неправильности данных.
В этом состоит суть метода программной защиты от неправильных данных. Данные могут быть неверны и из-за ошибок при вводе. Поэтому чем больше входных данных, тем жестче должна быть их проверка.
Далее приведен пример решения задачи проверки правильности программы.
Задача. Придумать тесты для отладки приведенной ниже программы для нахождения наибольшего общего делителя двух натуральных чисел.
{вычисление НОД двух натуральных чисел}
Var a,b:integer; {исходные натуральные числа}
х,у:integer; {переменные, используемые для поиска НОД}
begin
write('Введите два натуральных числа');
readln(a,b);
х:=а; y:=b; {A}
while х<>у do {В}
if x>y {С}
then х:=х-у {D}
else y:=y-x; {E}
write(x); {F}
end.
Решение. Для тестирования построим столько тестов, чтобы можно было пройти по каждой ветви программы хотя бы по разу. В ней имеются пять ветвей:
первая - А, В;
вторая - В , С;
третья - В, F;
четвертая - С, D, В;
пятая - С,Е,В.
Путей здесь много. Примерами путей являются последовательности из следующих ветвей:
первый- 1,3;
второй- 1,2,4,3;
третий - 1,2,5,3;
четвертый - 1,2 4,2,5,3;
пятый- 1,2,4,2,4,2,4,3;
шестой - 1, 2, 5, 2, 5, 2, 4, 3 и т.д.
Среди указанных путей есть такие, в которых используются не все ветви (это пути 1, 2, 3, 5), но есть и такие, в которых проходится каждая ветвь программы хотя бы по одному разу (это пути 4, 6).
Для построения теста выбранного пути построим сначала предикат пути, который будет принимать значение «истина», если в процессе исполнения программы реализуется данный путь, и «ложно» — при реализации других путей.
Для построения предиката пути проходим путь в обратном направлении и выписываем конъюнкцию всех условий, которые встречаются на этом пути. Если при обратном проходе пути осуществляется переход через оператор присваивания (переменная: =выражение), то в предикат пути вместо всех вхождений переменной из левой части оператора присваивания подставляется выражение из его правой части. Предикаты пути, построенные так, как описано выше, всегда выражаются в терминах констант и входных переменных. Чтобы пройти заданный путь во время исполнения программы, необходимо найти такие значения исходных данных, которые делают предикат пути истинным.
Рассмотрим процесс построения предиката для четвертого пути приведенной выше программы.
Вначале проходим ветвь 3 от F к В. При исполнении программы в блок F попадаем в случае ложности условия В, поэтому предикат этой ветви имеет вид Р: X=Y.
Движемся дальше от В к С через Е. При переходе оператора присваивания Y:=Y-X в предикате Р все вхождения переменной Y заменим на выражение Y-X. Получаем Р: X=Y-X или Р: 2*X=Y. Поскольку Е выполняется в случае ложности условия С, присоединяем его отрицание через конъюнкцию к Р. Р: (2*X=Y) and (X<=Y) .
Движемся от С к В и присоединяем к Р через конъюнкцию условие В (здесь оно должно быть истинным). Р: (2*X=Y) and (X<=Y) and (X<>Y). В полученном предикате из первого члена конъюнкции 2*X=Y следует третий: Х, не равный Y, поэтому третий член конъюнкции можно отбросить. Получим Р: (2*X=Y) and (X<=Y).
Движемся от В к С через D. При переходе через оператор присваивания (X: =X-Y) все вхождения X заменяем выражением X-Y и присоединяем через конъюнкцию условие С (здесь оно истинно). Р: (2*(X-Y)=Y) and (X-Y<=Y) или (2*X=3*Y) and (X<=2*Y).
Присоединяем условие С (здесь оно истинно). Р: (2*Х=3*у) and (x<=2*y) and (x<y). Анализируя полученный предикат, замечаем, что если истинен предпоследний член конъюнкции, то истинен и последний. Таким образом, последний член на истинность предиката не влияет, поэтому его можно отбросить. Р: (2*X=3*Y) and (X<=2*Y) .
Проходим ветвь 2 от С к В и к предикату через конъюнкцию присоединяем условие В (здесь оно истинно). Получаем Р: (2*X=3*Y) and (X<=2*Y) and (X<>Y).
В полученном предикате вновь из первого члена конъюнкции следует третий, поэтому его можно отбросить. Получаем Р: (2*X=3*Y) and (X<=2*Y).
Проходим ветвь 1 от В к А, при этом предикат пути не изменяется. Окончательно получаем Р: (2*X=3*Y) and (X<=2*Y).
Для построения теста осталось подобрать значения X и Y так, чтобы предикат стал истинным. Это возможно, например, при
Х=3, Y=2 получим ответ 1;
Х=9, Y=4 получим ответ 2;
Х=9, Y=6 получим ответ 3 ;
Х=12, Y=8 получим ответ 4 и т.д.
Контрольные вопросы
1. Что такое структурное программирование? Почему оно относится к декларативному программированию?
2. Опишите этапы создания структурной программы.
3. Чем отладка отличается от тестирования?
4. Что должно быть главным критерием качественной программы?
5. Что такое процедурная декомпозиция?
6. Кратко опишите правила программирования.
7. Что такое документирование программы?
8. Опишите три источника ошибок в программах и методы борьбы с ними.
Задачи и упражнения
1. В результате компиляции программы
programm z1;
const a=l, b=2, c=l;
var xl, x2, d:real;
begin
d:=b*b-4*a*c
x1: = (-b+sqrt(d))/(2*a);
x2=(-b-sqrt(d))/(2*a);
writeln('xl=',xl:5:3, ' x2=',x2:5:3);
end.
получены сообщения об ошибках:
• одно сообщение —Error 36: BEGIN expected;
• четыре сообщения — Error 85: ";" expected;
• одно сообщение —Error 91:":=" expected. Определить характер ошибок и исправить их.
2. В результате компиляции программы
program z2;
var a, b, х, с, е:real;
begin
real(a, b); {входной поток имеет вид: 2 1}
х:=а-b;
с:=а+b;
е:=cqr(х+с);
e:=cqrt(10*a-e)/ (е+4);
writeln(х,с,е,'конец решения);
end.
получены сообщения об ошибках:
• одно сообщение —Error 89:")" expected;
• два сообщения —Error 3:Unknown identifier;
• одно сообщение —Error 8: String constant exceeds line.
Определить характер ошибок и исправить их.
3. В результате компиляции программы
program z3;
const a:=2; b:=2.0;
var x:integer;
if a>=b then do
x:=b-l;
else
x:=a+l;
writeln(x);
end.
получены сообщения об ошибках:
• одно сообщение —Error 26: Type mismatch;
• одно сообщение —Error 36: BEGIN expected;
• одно сообщение —Error 85: ";" expected;
• одно сообщение —Error 113: Error in statement.
Определить характер ошибок и исправить их.
4. В результате компиляции программы
program z64;
var i:integer;
begin
k:=2;
for i:=l to 5 do
k:k+i;
end;
writeln('k=' ,k) ;
end.
получены сообщения об ошибках:
• одно сообщение —Error 3:Unknown identifier;
• одно сообщение — Error 94: "." expected;
• одно сообщение —Error 91: ":=" expected.
Определить характер ошибок и исправить их.
Дата добавления: 2018-09-22; просмотров: 2999; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!