Свойства алгоритмов. 1. Дискретность. Алгоритм определяет дискретный характер процесса

1. Дискретность. Алгоритм определяет дискретный характер процесса

решения задачи. Поэтому правило, порождающее непрерывный характер

процесса решения задачи, не является алгоритмом.

Примеры:

«Уходя, гасите свет» - примитивный алгоритм.

«Правила пользования междугородним телефоном» - пошаговый

процесс.

«Не курить» - непрерывный процесс, не являющийся алгоритмом.

2. Массовость. Алгоритм должен решать не одну конкретную задачу

(ограниченное множество неизменных исходных данных), а серию

однотипных задач. Т. е. множество различных исходных данных порождает

различные результаты.

Хоты массовость является одним из свойств большинства алгоритмов,

также ценность представляют алгоритмы, имеющие единственный вариант

исходных данных.

Нужно считать, что для каждого алгоритма существует некоторый класс

объектов, допустимых в качестве исходных данных.

Массовость алгоритма – это допустимость всех объектов

соответствующего класса, а не допустимость какого-либо их количества.

3. Детерминированность. Реализация алгоритма является

детерминированным (определенным) процессом. Всякий раз при запуске

алгоритма с одинаковыми исходными данными должен получаться

одинаковый результат, т. е. алгоритм может быть повторен сколько угодно

раз.

4. Потенциальная осуществимость алгоритма. Говорят, что

алгоритм применим к допустимому исходному данному, если с его помощью

можно получить искомый результат. Иначе, хотя исходное данное и

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

Неприменимость алгоритма к допустимому исходному данному

заключается в том, что алгоритмический процесс становится бесконечным,

либо безрезультатно обрывается на каком-либо шаге.

Отвлекаясь от реальной ограниченности времени и ресурсов,

необходимых для выполнения алгоритма, требуют лишь того, чтобы

алгоритмический процесс заканчивался после конечного числа шагов, и чтобы

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

считают, что алгоритм применим к исходному данному и потенциально (а не

реально) осуществим.

Пример1. Бесконечный цикл:

i=0

while i< = 10 do

k=k*2;

Пример 2. Последовательность вычислений:

1. b=2*a

2. b=b+1

3. c=b mod 3 a=6 ® d=6

4. d=a/c a=7 ®алгоритм не применим (ошибка деления на

ноль).

Кроме потенциальной осуществимости алгоритма на практике требуется

и реальная осуществимость.

5. Понятность. Алгоритм понятен для исполнителя, если он знает, как

его выполнять (know how). Возникает вопрос: что именно должен знать

исполнитель?

Свойство понятности можно истолковать как наличие алгоритма,

определяющего процесс выполнения заданного алгоритма. В этом случае

исполнителями могут быть любые объекты. Тогда исполнителю должен быть

известен алгоритм (руководство к действию) для решения всех других

алгоритмов, соответствующих исполнителю. Таким образом, возникает

рекурсивное определение алгоритма, например, любая операционная

система – это алгоритм алгоритмов.

6. Корректность. Алгоритм корректен, если выполняются три условия:

1. Преобразование допустимых входных данных в выходные

результаты выполняется за конечное число шагов (свойство

дискретности).

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

данных.

3. Результат работы алгоритма устойчив к вычислительной

погрешности (свойство обусловленности).

Если хоть одно из этих условий не выполняется, то алгоритм считается

некорректным.

Вычислительная погрешность (машинная точность) возникает из-за

ограниченной разрядной сетки ЭВМ и операций округления.

Обусловленность алгоритма показывает чувствительность результата

работы алгоритма к малым, но неизбежным ошибкам вычислений.

Алгоритм хорошо обусловлен, если малые вычислительные погрешности

приводят к малой относительной погрешности результата.

.

;

() 100% (*)

*

* *

вычислительная погрешность

где число обусловленности алгоритма

y

y

y y y y y

m

a

a m

-

-

= ±D = D × £ ×

e

n

d d n e

Для плохо обусловленного алгоритма > > 1 a n.

Примечание 1. Если задача корректна и хорошо обусловлена, то плохо

обусловленный алгоритм даёт неправильное решение и требует замены.

Примечание 2. Если исходная задача не корректна и плохо обусловлена, то

никакой хороший алгоритм не даст правильного решения.

Пример3: Алгоритм деления двух чисел столбиком не корректен, если не

задан критерий окончания вычислительного процесса.

6, 666666...

5 20

15 = =

Пример4: Рассмотрим задачу нахождения корней квадратного уравнения:

a

x b D

Если D то корни действительные иначе корни комплексные

D b a c

a x b x c

×

= - ±

³

= - × ×

× + × + =

0,,.

1, 2

Пусть точное значение выходного данного x=5, а результат измерений и

ввода в компьютер значений входных данных a, b, c содержит малую

погрешность ±0, 0001.

Тогда для точных значений входных данных существует единственный

действительный корень (D=0), а погрешность входных данных приводит к

появлению комплексных корней, не имеющих физического смысла при

решении задачи.

Пример5: Вычислить значение интеграла

, 1, 2,...

= ò × 1 = I xn e - xdx при n

n

При вычислениях допускать округление результатов до шести знаков

после запятой.

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

1, 1, 71828

1 0 = × - = ò» -

I n I - I e xdx

n n

Будем проводить вычисления начиная со значения I0. Тогда на девятом

шаге получим 9 1 0, 55361 0 9 8 I = × I - = - <, что приводит в дальнейшем к росту

погрешности и неправильному результату. Погрешность вычислений растёт

со скоростью факториала.

Вывод: Алгоритм неустойчив при n ³ 9.

Однако, устойчивость алгоритма зависит от порядка вычислений. Так,

если проводить вычисления в обратном порядке по формуле 1, 1

1 = + ³ - n

n

I In

n,

начиная с конца, например, n=54, то на первом шаге ошибка будет велика

порядка 0, 05, но с каждым шагом она будет уменьшаться со скоростью

факториала, что обеспечивает правильное решение в целом.

Пример 6: Вычислить значение функции (i)

i

i

i y x где x -

=

=Õ = 25

, 10.

А) при объявлении в программе переменной X: real вещественного типа,

для её хранения в памяти компьютера отводится 6 байт, что позволяет

хранить числа в диапазоне {10-38…1038}. Прямой порядок произведения чисел

уже на первом шаге выдает ошибку переполнения в программе:

25 24 49

0 1 x × x =10 × 10 =10.

Б) тоже самое возникает при обратном порядке перемножения чисел:

25 24 49

x 50 × x 49 =1 0 - × 1 0 - =1 0 -.

В) Сгруппируем пары произведений чисел и обеспечим корректность

алгоритма

() ()... () 1 1 1... 1 1 0 50 1 49 1 25 = × × × × × × × = × × × × = y x x x x x x - x k k

Если алгоритм создан для решения определенной задачи (заданного

набора исходных данных), то для любого исходного данного из этого набора

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

правило, не корректны.

В этом смысле иногда используется более простое толкование свойства

корректности. Считают, что алгоритм корректен, если его можно

применить.

7. Эффективность. Данное свойство определяет быстродействие и

связано с понятием вычислительной сложности алгоритма.

Эмпирические алгоритмы, как правило, не являются эффективными.

Теоретические алгоритмы являются корректными и эффективными, но могут

быть реально неосуществимы.