Анализ правильности алгоритмов
На практике часто приходится встречаться с программами, содержащими ошибки. Например, в самой последней операционной системе Windows специалистами обнаружено много ошибок, которые время от времени выявляются на ЭВМ.
Программа содержит ошибки, если ее выполнение на ЭВМ приводит к получению сбоев, отказов или неправильных результатов. Программу в таком состоянии нельзя использовать для решения практических задач.
Проявления ошибок:
Программа
¯
данные ® ЭВМ ® { отказ | сбой | ошибка }
Отказ - это ситуация, когда выполнение программы прекращается вообще. Программы, содержащие такого рода ошибки считаются неработоспособными, и от их использования следует отказываться.
Сбой - это потеря части данных либо получение непредусмотренных данных. Такого рода ошибки говорят о их частичной неработоспособности программ либо об их недостаточной надежности.
Результат неправильный, если он не соответствует требованиям, предъявляемым к работе программ. Программы, содержащие такие ошибки, считаются работоспособными, но их применение может приводить к получению ошибочных результатов.
Оценка программ:
Задача
 |
 |
данные ® программа ® результаты
О правильности программ нельзя утверждать
ничего если неизвестны предъявляемые к ним требования. Только при наличии строгих, четких спецификаций можно судить о правильности работы программ.
В качестве примера рассмотрим решение квадратного уравнения:
х2 + 3×х + 2 = 0.
Исходные данные - коэффициенты – а = 1, b = 3, с = 2. Требуемые результаты - пара чисел х1
и x2, являющихся корнями уравнения. Посмотрим, будут ли корнями уравнения пары чисел:
а) х1 = 2, x2
= 3; б) x1 = -2, x2 = -3.
Решением уравнений являются числа, подстановка которых превращает уравнение в тождество. В первом случае подстановка чисел х1 = 2, х2 = 3 в уравнение дает:
22
+ 3×2 + 2 = 12 ¹
0 - неправильно,
32
+3×3+2 = 20 ¹
0 - неправильно.
Следовательно, числа х1 = 2, х2 = 3 не являются правильными результатами.
Подстановка в уравнение чисел х1 = -2, х2 = -3:
(-2)2
+ 3×(-2) +2 = 0- правильно;
(-3)2
+ 3×(-3) +2 = 0- правильно.
Следовательно, числа х1 = -2, х2=
-3 являются правильными результатами.
Приведем формальную постановку задачи решения квадратных уравнений.
Постановка задачи
Решение квадратного уравнения
а×х2
+ b×x + с = 0.
Дано: a, b, с - коэффициенты.
Треб.: х1, х2 - корни.
Где: а×х12
+ b×х1
+ с = 0.
а×х22 + b×х2 + с = 0.
При: а ¹ 0.
Наличие точной постановки задач позволяет говорить о правильности не только конечных результатов, но и различных способов и методов их решения.
Способ правильный, если он дает правильные результаты. Способ неправильный, если он дает неправильные результаты или не дает результатов вообще.
Метод неправильный, если существуют допустимые данные, для которых он дает неправильные результаты либо не дает результатов вообще.
Метод правильный, если он дает правильные результаты для любой задачи данного класса. Использование правильных методов служит основой для составления алгоритмов и программ, не содержащих ошибок.
В рассматриваемом примере решения квадратных уравнений общим методом является вычисление корней с помощью дискриминанта.
Метод решения
x2 = (-b -
где
{ D = b2 - 4×а×с.
Правильность общих методов проверяется подстановкой расчетных формул в исходное уравнение. Получение тождеств в результате подстановок говорит о правильности выбранных расчетных формул.
Для первого корня х1 = (-b +
а×х12 + b×х1 + с = а×[(-b +
= (-b +
= (-b2 + D)/(4×a) + с = (-b2 + b2 - 4×а×с)/(4×а) + с = -4×а×с/(4×а) + с = 0.
Аналогичные результаты получаются и при подстановке формулы второго корня
х2
= (-b -
Однако саму постановку задачи необходимо дополнить условием: b2
- 4×а×с ³ 0. При нарушении этого условия не только уравнение не имеет решений, но и метод решения также не дает результатов из-за необходимости вычисления корней от отрицательного дискриминанта: D < 0.
В силу выбранного метода решения и принятой постановки алгоритм решения квадратных уравнений приобретает следующий вид:
алг «квадратное уравнение» Результаты вычислений
нач
D: = b*b - 4*а*с D = b2 - 4×а×с
х1:
= (-b +
х2:
= (-b -
все
х 1: = -c/b xl = -c/b
все
кон
Результаты выполнения алгоритма приведены справа. Можно заметить, что результаты выполнения совпадают с описанием выбранного метода решения с помощью дискриминанта. Это позволяет утверждать, что алгоритм - правильный.
Алгоритм содержит ошибки, если можно указать допустимые исходные данные, при которых либо будут получены неправильные результаты, либо результаты не будут получены вовсе.
Использование алгоритмов, содержащих ошибки, приводит к созданию программ, также содержащих ошибки.
Алгоритм считается правильным, если он дает правильные результаты для любых допустимых исходных данных. Правильность алгоритмов решения прикладных задач и наличие в них ошибок можно проверять двумя основными способами.
Первый способ - проверка основных этапов построения алгоритма:
задача ® постановка ® метод ® алгоритм
Второй способ - анализ результатов выполнения алгоритмов и их сравнение с выбранными методами решения и постановкой задачи:
задача ¬ постановка ¬ метод ¬ алгоритм
Приведем пример построения алгоритма с одновременным анализом его правильности.
Задача: Определить периметр треугольника, заданного на плоскости координатами вершин.
XС,УС
 |
Постановка задачи
Определение периметра треугольника, заданного на плоскости.
В = (ХВ, УВ) - координаты вершин треугольника
С = (XС,УС)
Треб.: Р - периметр
Метод решения
LАВ =
LВС =
LСА =
Где: Р = L(A,B) + L(B,C) + L(C,A);
здесь L[(x,y),(u,v)] =
Приведем алгоритм, полученный из описания метода упорядочением операций вычисления длин сторон треугольника с завершающим вычислением периметра. Результаты выполнения алгоритма приведены справа.
алг «периметр треугольника»
нач
LAB: =
LBC : =
LCA
: =
Р := LAB + LBC + LCA
кон
Р = LAB + LBC + LCA
Сравнение результатов выполнения алгоритма с описанием метода решения показывает, что это одна и та же система формул, что подтверждает правильность алгоритма.
Систематические методы анализа правильности алгоритмов и программ опираются на сопоставление тех же самых описаний, которые используются при их систематическом составлении.
Анализ правильности:
задача ¬ способ
¯ ¯
постановка ¬ методы
¯ ¯
сценарий ¬ алгоритмы
¯ ¯
ЭВМ ® программа
Основные типы алгоритмических ошибок в программах:
· ошибки в выбранных методах решения;
· ошибки в постановке решаемых задач;
· дефекты в сценариях диалога с ЭВМ;
· ошибки организации ввода данных;
· неправильная реализация методов решения.
Исчерпывающий анализ правильности алгоритмов и устранение из программ ошибок всех перечисленных типов возможны только при наличии соответствующих спецификаций: постановок задач, описаний методов решения и спецификаций ввода-вывода данных.
Будем считать, что программа правильная,
если она дает правильные результаты для любых допустимых исходных данных. Такого рода программы вполне можно использовать для решения прикладных задач.
Программа считается надежной, если она не дает сбоев и отказов ни при каких исходных данных. Надежность - обязательное условие для всех программ, которые используются людьми для решения практических задач на ЭВМ.
В качестве иллюстрации приведем пример систематического составления алгоритма и программы задачи определения суммарного веса учеников по данным из таблицы:
фамилия рост вес
|
Иванов |
185 |
85 |
|
Петрова |
165 |
65 |
|
Сидоров |
170 |
80 |
Рассмотрим постановку задачи и метод вычисления суммарного веса.
Постановка задачи
Определение суммарного веса.
Дано: Метод вычисления
(D1,.., DN) - данные об учениках, S0 = 0
= Sk-1 + vk
Fam - фамилия, R - рост, V - вес. [k = (1 ...
N)]
Треб.: Vsum - суммарный вес. Vsum = SN
Vsum = v1
+ v2 + ... + vN
При:
N > 0.
Правильность метода вычислений можно доказать по индукции. Рассмотрим результаты вычислений на 1-м, 2-м и k-м шагах. Отметим, что начальное значение S0 = 0.
На первом шаге при k = 1 результат вычисления
S1
= S0 +v1 = v1
На следующем втором шаге при k = 2 результат
S2 = S1 + v2 = v1 + v2.
На третьем шаге при k = 3 результат
S3= S2 + v3 = v1
+ v2 + v3.
В общем случае можно предположить, что к k-му шагу результат вычисления
Sk-1=v1+...+vk-1.
Тогда результат вычислений после k-го шага (исходя из описания метода)
Sk =
Sk-1 +vk = v1
+ … + vk-1
+ vk.
В силу принципа математической индукции утверждение верно для всех k = 1, 2,.... N. Следовательно, на последнем шаге при k = N конечный результат:
SN
= v1 + ... + vN.
Что и требовалось. Следовательно, метод правильный.
Приведем сценарий диалога решения поставленной задачи на ЭВМ. Для представления данных в программе примем последовательность операторов
data.
Сценарий Представление данных
Данные об учениках
фамилия вес рост
<Fam1> <V1> <R1> data «Иванов», 185, 85
… … … data «Петрова», 165, 65
<FamN>
<VN> <RN> data «Сидоров», 170, 80
суммарный вес = <Vsum>
Алгоритм обработки данных и программа, соответствующие выбранному сценарию и методу вычисления:
Алгоритм Программа
алг «суммарный вес» '
суммарный вес
нач cls
вывод («Данные об учениках») ? «Данные об учениках»
вывод («фамилия вес рост») ? «фамилия вес рост»
s := 0 s = 0
цикл do
чтение famS, r, v read fam$, r, v
при fam$=«» выход if fam$=«» then exit do
вывод (fam$, v, r) ? fam$; v; r
s := s + v s = s + v
кцикл loop
vsum
= s vsum = s
вывод («суммарный вec=»,vsum) ? «суммарный вес=»; vsum
кон end
Правильность приведенного алгоритма можно увидеть из описания результатов его выполнения.
Алгоритм Результаты выполнения
алг «суммарный вес» на экране и в памяти ЭВМ
нач
вывод («Данные об учениках») Данные об учениках
вывод («фамилия вес рост») фамилия вес рост
цикл
чтение fam$, r, v
при fam$=«» выход
вывод (fam$, v, r) <famk> <vk> <rk>
s:
= s + v sk = sk-1
+ vk
кцикл [k = (1...n)]
vsum
= s vsum = sn
вывод («суммарный вec=»,vsum) суммарный вес= <vsum>
кон
Сопоставление описания результатов выполнения с описаниями сценария и выбранного метода говорит об их полном соответствии. Следовательно, составленные алгоритм и программа правильные.
В о п р о с ы
1. Когда программы содержат ошибки?
2. Что такое правильный способ решения?
3. Когда способ решения неправильный?
4. Что такое правильный метод решения?
5. Когда метод решения неправильный?
6. Что такое правильный алгоритм?
7. Когда алгоритм содержит ошибки?
8. Каковы основные типы ошибок в программах?
З а д а ч и
1. Приведите постановку задачи, сценарий, алгоритм и программу решения линейного уравнения а×х + b = 0, с помощью формулы х = -b/а (при а ¹ 0).
2. Приведите постановку задачи, сценарий, алгоритм и программу решения квадратного уравнения а×х2 + b×x + с = 0 с помощью формулы дискриминанта.
3. Приведите постановку задачи, сценарий, алгоритм и программу решения системы из двух уравнений с двумя неизвестными:
с×х + d×y = f.
Примените для этой задачи вычисление корней с помощью определителей:
y = Dy/D.
Определители D, Dx и Dy вычисляются по формулам:
Dx = e×d - f×b,
Dy = a×f - c×e.
4. Приведите постановку, сценарии, алгоритм и программу решения следующих задач:
а) определение площади треугольника по длине сторон а, Ь, с по формуле Герона:
р = (а + b + с)/2.
б) определение площади треугольника, заданного на плоскости координатами своих вершин: (х1, у1), (х2, у2), (х3, у3); для вычисления длин сторон треугольника воспользуйтесь формулой определения длин отрезков на плоскости, задаваемых координатами концов:
l =
5. Приведите постановку, метод, сценарий, алгоритм и программу решения следующих задач:
а) определение времени встречи пешеходов, двигающихся навстречу друг другу;
б) определение времени, которое требуется пешеходу, чтобы догнать другого пешехода;
в) определение времени движения парохода по течению и против течения реки;
г) определение времени движения пешеходов навстречу друг другу, если один из них движется с замедлением;
д) определение времени падения тела с заданной высоты;
е) определение времени полета тела, брошенного вверх;
ж) определение расстояния, на которое улетит мяч, брошенный под углом к горизонту.
6. Дана прямоугольная матрица АNM - прямоугольная числовая таблица размера N ´ М. Приведите постановку, метод решения, сценарий, алгоритм и программу для решения следующих задач:
а) подсчет сумм элементов матрицы по столбцам,
б) подсчет сумм элементов матрицы по строкам,
в) нахождение минимального значения в каждом столбце,
г) нахождение минимального значения в каждой строке,
д) нахождение максимального значения в каждом столбце,
е) нахождение максимального значения в каждой строке,
ж) нахождение наибольшего из минимальных значений в столбцах,
з) нахождение наименьшего из максимальных значений в строках.
