Кроме того, что алгоритм это свод конечного числа правил, задающих последовательность выполнения действий при решении задачи, он должен обладать следующими свойствами:
1) Конечность (финитность) – любой алгоритм должен заканчиваться за конечное число шагов. Например, алгоритм поиска НОД удовлетворяет этому условию. Ш1 значение остатка r ≤ n, и если r≠0, то к следующему выполнению Ш1 значение n уменьшается т.о. получается убывающая последовательность целых “+” n, который заканчивается, когда r=0, т.е. за конечное число раз.
2) Определенность – каждый шаг алгоритма должен быть точно определен. Действия, которые необходимо выполнить, должны быть строго и недвусмысленно заданы в каждом возможном случае.
3) Ввод исходных данных – любой алгоритм имеет некоторое число входных данных, которые задаются ему до начала работы. Эти данные берутся из конкретного допустимого множества. Например, для алгоритма поиска НОД входных величины m и n выбираются из множества натуральных чисел.
4) Вывод результата (результатов) – любой алгоритм всегда имеет 1 и несколько выходных величин, которые имеют определенное отношение к исходным данным, и получаются в результате их анализа и обработки в ходе выполнения алгоритма.
5) Эффективность – в общем случае это обозначает, все операции, которые выполняются в алгоритме, должны быть достаточно простыми и выполнятся за допустимое конечное время. Если существует несколько алгоритмов решения этой задачи, необходимо выбрать более эффективный алгоритм. Это означает, что для заданного алгоритма нужно найти его рабочие характеристики:
- Это время выполнения работы алгоритма, в зависимости от объема входных данных;
- объем памяти необходимый для проведения вычислений.
6) Правильность алгоритма - это способность алгоритма дать правильные результаты решения поставленной задачи. Практически правильность алгоритма подтверждается в результате проведения большого кол-ва испытания в которых проверяются все возможные случаи и состояния, учитываемые в реализации данного алгоритма.
Теоретически доказать правильность работы любого алгоритма можно с помощью метода МАТИНДУКЦИИ.
