Практическое применение результатов теории алгоритмов

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

Теоретический аспект: при исследовании некоторой задачи результаты теории алгоритмов позволяют ответить на вопрос: является ли эта задача в принципе алгоритмически разрешимой. Для алгоритмически неразрешимых задач: возможно ли их сведение к задаче останова машины Тьюринга. В случае алгоритмической разрешимости задачи возникает следующий важный теоретический вопрос: о принадлежности этой задачи к классу NP–полных задач*. При утвердительном ответе на вопрос о принадлежности к классу NP–полных задач можно говорить о существенных временных затратах для получения точного решения для больших размерностей исходных данных.

Практический аспект: методы и методики теории алгоритмов позволяют осуществить:

· рациональный выбор из известного множества алгоритмов решения данной задачи с учетом особенностей их применения (например, при ограничениях на размерность исходных данных или объема дополнительной памяти);

· получение временных оценок решения сложных задач;

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

· разработку и совершенствование эффективных алгоритмов решения задач в области обработки информации на основе практического анализа.