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

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

Разные понятия алгоритма:

1. Колмогоров: Алгоритм - это всякая система вычислений, выполняемых по строго определенным правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи.

2. Марков: Алгоритм - это точное предписание, определяющее вычислительный процесс, идущий от варьируемых исходных данных к искомому результату.

Основные задачи:

• ·Формализация понятия и исследования нормальных алгоритмических систем;
• ·Доказательство алгоритмической неразрешимости задачи;
• ·Формальное доказательство правильности и эквивалентности алгоритмов;
• ·Определение и исследование сложностных классов;
• ·Доказательство теоретических оценок сложности задач;
• ·Получение методов разработки эффективных алгоритмов;
• ·Асимптотический анализ сложности итерационных алгоритмов;
• ·Анализ рекурсивных алгоритмов;
• ·Получение явных функций трудоемкости;
• ·Исследование емкостной сложности алгоритмов;
• ·разработка классификаций алгоритмов;
• ·разработка критериев сравнительной оценки ресурсной эффективности алгоритмов и методов их сравнительного анализа.

Требования к алгоритмам:

1. Алгоритм должен содержать конечное кол-во элементарно выполнимых предписаний;
2. Алгоритм должен выполнять конечное кол-во шагов при решении задачи, т.е. удовлетворять требованию конечности действий;
3. Алгоритм должен быть единым для всех допустимых исходных данных, т.е. удовлетворять требованию универсальности;
4. Алгоритм должен приводить к правильному по отношению к поставленной задаче решению, т.е. удовлетворять требованию правильности.

В настоящее время оформились следующие разделы в теории алгоритмов:

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

- теория асимптотического анализа алгоритмов рассматривает методы получения асимптотических оценок ресурсоемкости или времени выполнения алгоритмов, в частности, для рекурсивных алгоритмов. Асимптотический анализ позволяет оценить рост потребности алгоритма в ресурсах (например, времени выполнения) с увеличением объема входных данных. Важную роль в развитии асимптотического анализа алгоритмов сыграли A. Ахо, Дж. Ульман, Дж. Хопкрофт;

- теория практического анализа вычислительных алгоритмов решает задачи получения явных функции трудоёмкости, интервального анализа функций, поиска практических критериев качества алгоритмов, разработки методики выбора рациональных алгоритмов. Основополагающей работой в этом направлении следует считать фундаментальный труд Д. Кнута «Искусство программирования для ЭВМ».

К теории алгоритмов тесно примыкают исследования, связанные с разработкой методов создания эффективных алгоритмов (динамическое программирование, метод ветвей и границ, метод декомпозиции, «жадные» алгоритмы, специальные структуры данных и т. д.).