Теория алгоритмов

Классическая теория алгоритмов

Теория асимптотического анализа алгоритма

Теория практического анализа алгоритмов

Методы создания эффективных алгоритмов алгоритма

Классическая теория алгоритмов: формулировка задач в терминах формальных языков; понятие задачи разрешения; описание сложных классов задач. Авторы теории: Эдмондс, Бен-Ор, Янов, Котов и др.

Теория асимптотического анализа алгоритмов: понятие сложности и трудоемкости алгоритма; критерии оценки алгоритмов; методы получения асимптотических оценок, в частности, для рекурсивных алгоритмов. В развитие этой теории существенный вклад внесли Кнут, Ахо, Хопкрофт, Ульман, Карп, Мошков, Кудрявцев и др.

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

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

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

1. формализация понятия «алгоритм» и исследование формальных алгоритмических систем (моделей вычислений);

2. доказательство алгоритмической неразрешимости задач;

3. формальное доказательство правильности и эквивалентности алгоритмов;

4. классификация задач, определение и исследование сложности классов;

5. получение методов разработки эффективных алгоритмов;

6. исследование и анализ рекурсивных алгоритмов;

7. получение явных функций трудоемкости алгоритмов;

8. разработка классификаций алгоритмов;

9. исследование емкостной (по ресурсу памяти) сложности задач и алгоритмов;

10. разработка критериев сравнительной оценки ресурсной эффективности алгоритмов и методов их сравнительного анализа.