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

На практике часто приходится встречаться с программами, со­держащими ошибки. Например, в самой последней операционной системе Windows специалистами обнаружено много ошибок, кото­рые время от времени выявляются на ЭВМ.

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

Проявления ошибок:

Программа

¯

данные ® ЭВМ ® { отказ | сбой | ошибка }

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

Сбой - это потеря части данных либо получение непредусмот­ренных данных. Такого рода ошибки говорят о их частичной нера­ботоспособности программ либо об их недостаточной надежности.

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

Оценка программ:

Задача

исходное требуемое

данные ® программа ® результаты

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

В качестве примера рассмотрим решение квадратного уравнения:

х² + 3×х + 2 = 0.

Исходные данные - коэффициенты – а = 1, b = 3, с = 2. Требу­емые результаты - пара чисел х₁ и x₂, являющихся корнями уравне­ния. Посмотрим, будут ли корнями уравнения пары чисел:

а) х₁ = 2, x₂ = 3;б) x₁ = -2, x₂ = -3.

Решением уравнений являются числа, подстановка которых пре­вращает уравнение в тождество. В первом случае подстановка чисел х₁ = 2, х₂ = 3 в уравнение дает:

2² + 3×2 + 2 = 12 ¹ 0 - неправильно,

3² +3×3+2 = 20 ¹ 0 - неправильно.

Следовательно, числа х₁ = 2, х₂ = 3 не являются правильными результатами.

Подстановка в уравнение чисел х₁ = -2, х₂ = -3:

(-2)² + 3×(-2) +2 = 0- правильно;

(-3)² + 3×(-3) +2 = 0- правильно.

Следовательно, числа х₁ = -2, х₂= -3 являются правильными результатами.

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

Постановка задачи

Решение квадратного уравнения

а×х² + b×x + с = 0.

Дано: a, b, с - коэффициенты.

Треб.: х₁, х₂ - корни.

Где: а×х₁² + b×х₁ + с = 0.

а×х₂² + b×х₂ + с =0.

При: а ¹ 0.

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

Способ правильный, если он дает правильные результаты. Способ неправильный, если он дает неправильные результаты или не дает результатов вообще.

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

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

В рассматриваемом примере решения квадратных уравнений об­щим методом является вычисление корней с помощью дискрими­нанта.

Метод решения

x₁ = (-b + )/(2×а),

x₂ = (-b - )/(2×a),

где

{ D = b² - 4×а×с.

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

Для первого корня х₁ = (-b + )/(2×a) подстановка и тождест­венные преобразования формул дадут:

а×х₁² + b×х₁ + с = а×[(-b + )/(2×а)]² + b× (-b + )/(2×a) + с =

= (-b + )²/(4×а) + b× (-b + )/(2×a) + с = (b + ) × (-b + )/(4×а) + с =

= (-b² + D)/(4×a) + с = (-b² + b² - 4×а×с)/(4×а) + с = -4×а×с/(4×а) + с = 0.

Аналогичные результаты получаются и при подстановке формулы второго корня

х₂ = (-b - )/(2×a). После выполнения анало­гичных преобразований будет получено такое же тождество. И на основании этих проверок можно сделать заключение, что рассмот­ренный метод дает правильные результаты для любык допустимых данных.

Однако саму постановку задачи необходимо дополнить условием: b² - 4×а×с ³ 0. При нарушении этого условия не только уравнение не имеет решений, но и метод решения также не дает результатов из-за необходимости вычисления корней от отрицательного дискриминан­та: D < 0.

В силу выбранного метода решения и принятой постановки алго­ритм решения квадратных уравнений приобретает следующий вид:

алг «квадратное уравнение» Результаты вычислений

Нач

если а ¹ О топри а ¹ 0

D: = b*b - 4*а*с D = b² - 4×а×с

если D > = 0 то при D >= 0

х1: = (-b + )/(2*a) х1 = (-b + )/(2×a)

х2: = (-b - )/(2*a) х2 = (-b - )/(2×a)

Все

инеc а = 0 то при а = 0

если b ¹ 0при b ¹ 0

х 1: = -c/b xl = -c/b

Все

Кон

Результаты выполнения алгоритма приведены справа. Можно заметить, что результаты выполнения совпадают с описанием вы­бранного метода решения с помощью дискриминанта. Это позволяет утверждать, что алгоритм - правильный.

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

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

Первый способ - проверка основных этапов построения алго­ритма:

задача ® постановка ® метод ® алгоритм

Второй способ - анализ результатов выполнения алгоритмов и их сравнение с выбранными методами решения и постановкой задачи: