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