Сценарий

I I

Нач

Задача

Программа

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

Cls read n, m

Нач

Si ^ Si ЛГ

[ к = (1... N)]

Матрица <N>x<M> <ац>... <а_ш>

< ам1 >... < aMN >

Суммы элементов:

<Sl>... <S^>

Представление данных ' матрица Anm: data 3, 4 data I, 2, 3, 4 data 0, 1, 2, 3 data 0, 0, 1, 2

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

АлгоритмПрограмма

алг «сумма строк матрицы» ' сумма строк матрицы

чтение (п, т). если п > 0 и т > 0 то массив А[1:п,1:т] массив S[1:n] ввод-вывод_матрицы суммирование_строк от k = 1 до п цикл

выв (s[k]) кцикл все кон

if N > 0 and М > 0 then dim A (N,M) dim S(n)

gosub vvod 'ввод-матрицы gosub sum 'суммирование for k= 1 to n? s[k] next k end if end

алг «суммирование строк» нач

от k = 1 до N цикл

s[k]:= 0 от l = 1 до М цикл

s[k]:= s[k] + A[k,l] кцикл кцикл кон

sum: 'суммирование строк ' нач for k = 1 to n

s[k] = 0 for I = 1 to m

s[k] = s[k] + a[k,l] next I next k return

алг «ввод-вывод_матрицы» нач

вывод («Матрица», N, «х», М) от k = 1 до N цикл от I = 1 до М цикл чтение (A [k,l]) вывод (A [k,l]) кцикл нов_строка кцикл кон

vvod: 'ввод-вывод_матрицы ' нач

? «Матрица»; m; «х»; m for k = 1 to n for l = 1 to m read A (k,l)? A (k,l) next 1? next k return

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

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

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

i

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

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

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

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

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

/ \

исходное требуемое данные —> программа —> результаты

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

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

х² + 3-х + 2 = 0.

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

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

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

2² + 3-2 + 2 = 12 Ф О - неправильно,

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

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

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

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

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

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

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

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

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

а-х² + Ь-х + с = 0.

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

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

Где: а-хi² + b - х i + с = 0. а-х₂² + Ь- х₂ + с = 0.

При: а^0.

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

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

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

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

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

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

Г xi = (-b + 4d)/(2-а),

lx₂ = (-b - 415)1(2-ъ),

где

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

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

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

а-хi² + b-хi + с = а-[(-b +4d)/(2-а)]² + b- (-b +y[D)/(2-a) + с =

= (-b + 4d)²/(4-а) + b- (-b + 4d)/(2-a) + с = (b + V/)) • (-b + V/))/(4-а) + с =

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

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

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

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

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

алг «квадратное уравнение»

если а^О то D: = Ъ * Ъ - 4*а*с если D > = 0 то

хl: = (-b +y[ D )/(2*a)

х2: = (-b - y[ D )/(2*a) все инее а = 0 то если Ъ ^ 0

х 1: = - с / Ъ все кон

Результаты вычислений

при а Ф 0 D = b² - 4-а-с приБ >= 0

хl = (-b + y[D)/(2-a) х2 = (-b - V/))/(2-a)

при а = 0

Г при b Ф 0 1x1 = -с/Ь

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

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

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

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

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

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

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

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

шин.

Задача: Определить периметр треугольника, заданного на плоскости координатами вер-

X_С,У_С

Х_а,Уа

XвУв

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

Определение периметра треугольника, заданного на плоскости.

Дано: А = (Х_А, У_А)^

В = (ХВ, У_В) }■ - координаты вершин треугольника

С = (Х_С,У_С) Треб.: Р - периметр" Метод решения f Р = L_АВ +L_ВС+L_СА

L_АВ = V К^Ха ~ Х_в f + (Уа ~ УВ У. L_ВС = V К^ХВ ~ ^ХС У + (УВ ~ У С У \

L_СА = V l(XС ~ ^ХА У + (УС ~ УА У

Где: Р = L(A,B) + ЦВ,С) + ЦС,А);

здесь L[(x,y),(u,v)] = д/ (х - и)² + (у - v)

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

алг «периметр треугольника» нач

LAB: = д/ (Х_А - Х_в)² + (У_А - У_В)²

LBC: = д/ (Х _В - Х_С У + (У _В - У _С У

LCA: = yj (Х _С -Х _А)² + (У_С - У_А)²

Р:= LAB + LBC + LCA кон

Результаты

V[(x _A -x _B)²+(У_А - У_В)²

<

V[(x _В -x _С)²+(У_В - У_С)²]

V[(x _С -x _А)²+(У_С - У_А)²]

^ Р = LAB + LBC + LCA

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

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

задача <- способ

постановка ← методы

↓ алгоритмы ↓

↓

<-

программа

↓ ЭВМ

—»

Основные типы алгоритмических ошибок в программах:

• ошибки в выбранных методах решения;

• ошибки в постановке решаемых задач;

• дефекты в сценариях диалога с ЭВМ;

• ошибки организации ввода данных;

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

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

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

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

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

фамилия Иванов	рост 185	вес 85
Петрова
Сидоров

Рассмотрим постановку задачи и метод вычисления суммарного веса.

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

Определение суммарного веса.

Дано:Метод вычисления

(Pi,.., D_N) - данные об учениках, S₀ = О

где D = [Fam,R,V] - состав данных, Г Sk = Sk-i + V k

Fam - фамилия, R - рост, V - вес. I [k = (1... N)]

Треб.: V_sum - суммарный вес. V_sum = S_N

V_sum = Vi + V 2 +... + V n

При: N > 0.

Правильность метода вычислений можно доказать по индукции. Рассмотрим результаты вычислений на 1-м, 2-м и k-м шагах. Отметим, что начальное значение S₀ = 0. На первом шаге при k = 1 результат вычисления

S₁ = S₀ +v₁ = v₁

На следующем втором шаге при k = 2 результат

S₂ = S₁ + v₂ = v₁ + v₂. На третьем шаге при k = 3 результат

S₃= S₂ + v₃ = v₁ + v₂ + v₃. В общем случае можно предположить, что к k-му шагу результат вычисления

S_k-1=v₁+...+v_k-1. Тогда результат вычислений после k-го шага (исходя из описания метода)

S_k = S_k-1 +v_k = v₁ + … + v_k-1 + v_k.

В силу принципа математической индукции утверждение верно для всех k = 1, 2,.... N. Сле-довательно, на последнем шаге при k = N конечный результат:

S_N = v₁ +... + v_N. Что и требовалось. Следовательно, метод правильный.

Приведем сценарий диалога решения поставленной задачи на ЭВМ. Для представления данных в программе примем последовательность операторов data.

СценарийПредставление данных

dano:'данные учеников data «Иванов», 185, 85 data «Петрова», 165, 65 data «Сидоров», 170, 80 data «», 0, 0

Алгоритм обработки данных и программа, соответствующие выбранному сценарию и ме­тоду вычисления:

Алгоритм алг «суммарный вес» нач вывод («Данные об учениках») вывод («фамилия вес рост») s:= 0	Программа ' суммарный вес els? «Данные об учениках»? «фамилия вес рост» s = 0
цикл чтение famS, r, v при fam$=«» выход вывод (fam$, v, r)		do read fam$, r, v if fam$=«» then exit do ? fam$; v; r
s:= s + v		S = S + V
кцикл vsum = s		loop vsum = s
вывод («суммарный кон	вec=»,vsum)	? «суммарный вес=»; vsum end

Правильность приведенного алгоритма можно увидеть из описания результатов его выпол-

нения.

Алгоритм

алг «суммарный вес»