пользователей: 26587
предметов: 11603
вопросов: 211632
Конспект-online
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


Свойства алгоритмов

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

1) Конечность (финитность) – любой алгоритм должен заканчиваться за конечное число шагов. Например, алгоритм поиска НОД удовлетворяет этому условию. Ш1 значение остатка r ≤ n, и если r≠0, то к следующему выполнению Ш1 значение n уменьшается т.о. получается убывающая последовательность целых “+” n, который заканчивается, когда r=0, т.е. за конечное число раз.

2) Определенность – каждый шаг алгоритма должен быть точно определен. Действия, которые необходимо выполнить, должны быть строго и недвусмысленно заданы в каждом возможном случае.

3) Ввод исходных данных – любой алгоритм имеет некоторое число входных данных, которые задаются ему до начала работы. Эти данные берутся из конкретного допустимого множества. Например, для алгоритма поиска НОД входных величины m и n выбираются из множества натуральных чисел.

4) Вывод результата (результатов) – любой алгоритм всегда имеет 1 и несколько выходных величин, которые имеют определенное отношение к исходным данным, и получаются в результате их анализа и обработки в ходе выполнения алгоритма.

5) Эффективность – в общем случае это обозначает, все операции, которые выполняются в алгоритме, должны быть достаточно простыми и выполнятся за допустимое конечное время. Если существует несколько алгоритмов решения этой задачи, необходимо выбрать более эффективный алгоритм. Это означает, что для заданного алгоритма нужно найти его рабочие характеристики:

  • Это время выполнения работы алгоритма, в зависимости от объема входных данных;
  • объем памяти необходимый для проведения вычислений.

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

Теоретически доказать правильность работы любого алгоритма можно с помощью метода МАТИНДУКЦИИ.


27.08.2014; 14:30
хиты: 202
рейтинг:0
для добавления комментариев необходимо авторизироваться.
  Copyright © 2013-2017. All Rights Reserved. помощь