Проверка правильности работы алгоритма.

1) Метод преобразования предикатов.( Пособие «Методы программирования», Коренева, Корсакова, Преснякова, Фильчаков). Весь метод построен на логике высказываний.

2) Верификация. Аналитическое доказательство правильности работы алгоритмов.

Метод табличной верификации. Задача: поменять значения двух переменных местами.

№	Операции	xi	yi
	x = x + y	x1 = x0 + y0	y1 = y0
	y = x - y	x2 = x1	y2 = x1 – y1
	x = x – y	x3 = x2 – y2	y3 = y2

x3 = x2 - y2 = x1 – (x1-y1) = y1 = y0

т.е. x3 = y0

y3 = y2 = x1-y1 = x0 +y0 – y0 = x0

т.е. y3 = x0

3) Метод ручного тестирования. Расчет значений выходных данных на фиксированном наборе исходных.

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

Пример: сортировка методом стандартного обмена

Упорядочим массив по возрастанию

Суть метода состоит в следующем:

Начиная с первых двух элементов массива сравниваются последовательно и по парно все элементы этого массива. Если последующий больше предыдущего, то перестановка не требуется, а если меньше, то их следует поменять местами. В итоге МАХ-элемент, «как пузырёк», выталкивается в конец массива. Но одного просмотра массива мало, надо ещё (n-1) просмотреть все элементы с первого по n-ынй, а лучше по (n-i)-ый, где I - число уже сделанных просмотров. То, что цикл по i заканчивается не при n-1, а при n-i, увеличивает эффективность алгоритма по край не мере в два раза.

Рис. 1

Рис. 2

Таблица трассировки для одного прохождения по массиву (как на Рис. 2)

№	i	j	A(j)	A(j+1)	s	A
						5,4,1,2,3
						4,5,1,2,3
						4,1,5,2,3
						4,1,2,5,3
						4,1,2,3,5

Рис. 3

Оценка эффективности работы алгоритмов.

Дата добавления: 2015-11-30