Понятие алгоритма. Основные задачи и направления современной теории алгоритмов.

Алгоритм, от имени учёного аль-Хорезми - точный набор инструкций, описывающих порядок действий исполнителя для достижения результата решения задачи за конечное время. Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:

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

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

- понятность — алгоритм для исполнителя должен включать только те команды, которые ему (исполнителю) доступны, которые входят в его систему команд.

- завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов.

- массовость (универсальность) - алгоритм должен быть применим к разным наборам исходных данных.

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

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

- классическая теория алгоритмов изучает проблемы формулировки задач в терминах формальных языков, вводит понятие задачи разрешения, проводит классификацию задач по классам сложности (P, NP и др.).

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

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

Друзья! Приглашаем вас к обсуждению. Если у вас есть своё мнение, напишите нам в комментарии.