пользователей: 21276
предметов: 10469
вопросов: 178036
Конспект-online
зарегистрируйся или войди через vk.com чтобы оставить конспект.
РЕГИСТРАЦИЯ ЭКСКУРСИЯ


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

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

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

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

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

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

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

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

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

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


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