Современная теория алгоритмов

Начальной точкой отсчета современной теории алгоритмов можно считать теорему о неполноте символических логик, доказанную немецким математиком Куртом Геделем в 1931 г. В этой работе было показано, что некоторые математиче­ские проблемы не могут быть решены алгоритмами определенного класса.

Общность результата Геделя связана с вопросом о том, совпадает ли использо­ванный им класс алгоритмов с классом всех алгоритмов в интуитивном понимании этого термина. Эта работа дала толчок к поиску и анализу различных формализа­ции понятия «алгоритм».

Первые фундаментальные работы по теории алгоритмов были опубликованы в середине 1930-х гг. Аланом Тьюрингом, Алоизом Черчем и Эмилем Постом. Предложенные ими машина Тьюринга, машина Поста и класс рекурсивно-вы­числимых функций Черча были первыми формальными описаниями алгоритма, опирающимися на строго определенные модели вычислений. Сформулированные гипотезы Поста и Черча—Тьюринга постулировали эквивалентность предложен­ных ими моделей вычислений, как формальных систем, и интуитивного понятия алгоритма. Важным развитием этих работ стала формулировка и доказательство существования алгоритмически неразрешимых проблем.

В 1950-х гг. существенный вклад в развитие теории алгоритмов внесли работы Колмогорова и основанный на теории формальных грамматик алгоритмический формализм Маркова — так называемые нормальные алгоритмы Маркова. Формаль­ные модели алгоритмов Поста, Тьюринга и Черча, равно как и модели Колмогорова и Маркова, оказались эквивалентными в том смысле, что любой класс проблем, разрешимых в одной модели, разрешим и в другой.

Появление доступных ЭВМ и существенное расширение круга решаемых на них задач привели в 1960—1970-х гг. к практически значимым исследованиям алгоритмов и вычислительных задач. На этой основе впоследствии выделилось несколько разделов теории алгоритмов (рис. 14.4).

Глава 14. Основы теории алгоритмов

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

 

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

Рис. 14.4. Разделы современной теории алгоритмов

Классическая теория алгоритмов: формулировка задач в терминах формальных языков; понятие задачи разрешения; описание сложностных классов задач; фор­мулировка в 1965 г. Эдмондсом проблемы Р = NP; открытие класса TVP-полных задач и его исследование; введение новых моделей вычислений — алгебраического дерева вычислений (Бен-Ор), машины с произвольным доступом к памяти, схем алгоритмов Янова, стандартных схем программ Котова и др.

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

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

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

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

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

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

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

□ классификации задач, определение и исследование сложностных классов;

□ доказательство теоретических нижних оценок сложности задач;

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

□ асимптотический анализ сложности итерационных алгоритмов;

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

14.2. Способы записи алгоритмов

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

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

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

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

Способы записи алгоритмов

Для строгого задания различных структур данных и алгоритмов их обработки требуется иметь такую систему формальных обозначений и правил, чтобы смысл всякого используемого предписания трактовался точно и однозначно. Соответ­ствующие системы правил называют языками описаний. К средствам описания алгоритмов относятся следующие основные способы их представления: словесный, графический (блок-схема), псевдокоды, программный, диаграмма Несси—Шней­дермана (рис. 14.5).

Способы представления алгоритмов

Словесный

Графический (блок-схема)

Псевдокоды

Программный

Диаграмма Нэсси—Шнейдермана

Рис. 14.5. Способы представления алгоритмов