Основы теории алгоритмов

Основы теории алгоритмов

Все алгоритмы могут быть разделены на 2 группы:

- Численные алгоритмы, в которых присутствуют операции над числами и которые дают числовой результат.

- Логические алгоритмы позволяют выполнять процедуры над объектами любой природы и результат может быть не численным. Например, поиск пути в лабиринте, где лабиринт задается графом в виде матрицы сложности, а путь в виде последовательности ребер графа.

Общие свойства алгоритмов

1. Дискретность алгоритма:

Любой алгоритм представляет собой процесс последовательных процедур, выполняемых в дискретном времени.

Множество процедур, составляющих алгоритм, представляют собой программу.

Отдельные процедуры - операторы.

Каждая процедура преобразует некоторые исходные множества объектов в некоторое конечное для этой процедуры множество.

Эти множества представляют собой состояния алгоритмической системы в рассматриваемые моменты (такты) дискретного времени.

Конечное состояние предыдущей процедуры выступает в качестве исходного состояния последующей процедуры.

Состояние алгоритмических систем существует в промежутках между процедурами. Процедуры представляют собой переходы между состояниями.

Можно выделить начальное и конечное состояние для алгоритма в целом.

Начальные – исходные данные

Конечные – результат

2. Детерминированность алгоритмов

Совокупность величин, получаемых в какой-то (не начальный) момент времени, однозначно определяет совокупность величин, полученных в предшествующие моменты времени.

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

3. Направленность алгоритма

Алгоритм через конечное число тактов времени должен привести к остановке, которая свидетельствует о достижении требуемого результата. Если же могут быть преобразования, заданные в алгоритме, не приводящие к результату, в алгоритме должны быть предусмотрены процедуры, либо прекращающие на работу, либо определяющие новый требуемый результат алгоритма.

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

4. Массовость алгоритма

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

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

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

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

5. Элементарность шагов алгоритма

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

Независимые процедуры могут быть объединены в один общий блок и могут рассматриваться как процедуры, соответствующие одному такту алгоритма.

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

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