В.А. Носов - Основы теории алгоритмов и анализа их сложности (курс лекций)

Носов Валентин АлександровичОСНОВЫ ТЕОРИИ АЛГОРИТМОВИ АНАЛИЗА ИХ СЛОЖНОСТИК у р сл е к ц и йМосква 1992Настоящее пособие возникло на основекурса лекций, читаемыхслушателям, обучающимся по специальности “Прикладная математика”.В настоящее время имеется много обстоятельных руководств по теорииалгоритмов, однако данное пособие отличается тем, что в нем основноевнимание уделяется той части теории алгоритмов, которая относится кизучению возможностей вычислительных машин, к сложности вычислений, книжним оценкам сложности иоптимизации алгоритмов.

Перечисленныевопросыимеют важное значение для специалистов,использующихвычислительную технику в своей практической деятельности.Список литературы указан в конце пособия, использовалась такжежурнальная литература и результаты автора по сложности алгоритмов.Автор признателен всем специалистам, прочитавшим рукопись пособия ивысказавшим конструктивные замечания.Электронная версия подготовлена к публикации на web-сервере"Интеллектуальные системы" (http://intsys.msu.ru) кафедры Математическойтеории интеллектуальных систем механико-математического факультета МГУимени М.В. ЛомоносоваВсе вопросы использования пособия просьба согласовывать с авторомЭлектронный адрес автора - vnosov@intsys.msu.ruОглавление§ 1. ВВЕДЕНИЕ§ 2 МАШИНА ТЬЮРИНГА И ФУНКЦИИ, ВЫЧИСЛИМЫЕ ПО ТЬЮРИНГУ§ 3 МАШИНЫ ПРОИЗВОЛЬНОГО ДОСТУПА И ВЫЧИСЛИМЫЕ ФУНКЦИИ.§ 4.ЧАСТИЧНО РЕКУРСИВНЫЕ ФУНКЦИИ И ИХ ВЫЧИСЛИМОСТЬ§ 5.

НУМЕРАЦИЯ НАБОРОВ ЧИСЕЛ И СЛОВ..§ 6 ВЫЧИСЛЕНИЕ ПО ТЬЮРИНГУ ЧАСТИЧНО РЕКУРСИВНЫХ ФУНКЦИЙ .§ 7.АРИФМЕТИЗАЦИЯ МАШИН ТЬЮРИНГА И ЧАСТИЧНАЯ РЕКУРСИВНОСТЬ ФУНКЦИЙ,ВЫЧИСЛИМЫХ ПО ТЬЮРИНГУ§ 8 НОРМАЛЬНЫЕ АЛГОРИТМЫ§ 9 НУМЕРАЦИЯ АЛГОРИТМОВ§10 АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ§ 11. ПРОБЛЕМА ТОЖДЕСТВА СЛОВ В КОНЕЧНО ОПРЕДЕЛЕННЫХ ПОЛУГРУППАХ И ДРУГИЕПРИМЕЧАТЕЛЬНЫЕ АЛГОРИТМИЧЕСКИ НЕРАЗРЕШИМЫЕ ПРОБЛЕМЫ§ 12 ХАРАКТЕРИСТИКИ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ§ 13. НИЖНИЕ ОЦЕНКИ ВРЕМЕННОЙ СЛОЖНОСТИ ВЫЧИСЛЕНИЙ НА МАШИНАХ ТЬЮРИНГА§ 14. КЛАССЫ СЛОЖНОСТИ P И NP И ИХ ВЗАИМОСВЯЗЬ§ 15.

NP -ПОЛНЫЕ ЗАДАЧИ. ТЕОРЕМА КУКА§ 16. ОСНОВНЫЕ NP -ПОЛНЫЕ ЗАДАЧИ. СИЛЬНАЯ NP -ПОЛНОТА§ 17. СЛОЖНОСТЬ АЛГОРИТМОВ, ИСПОЛЬЗУЮЩИХ РЕКУРСИЮ§ 18. АЛГОРИТМ БЫСТРОГО ПРЕОБРАЗОВАНИЯ ФУРЬЕ И ЕГО ПРИЛОЖЕНИЯ§ 19. СЛОЖНОСТЬ АЛГОРИТМОВ ВЫБОРА НА ЧАСТИЧНО УПОРЯДОЧЕННОМ МНОЖЕСТВЕ ИИХ ОПТИМАЛЬНОСТЬ§ 20.ОПТИМАЛЬНОСТЬ ЖАДНОГО АЛГОРИТМАЛИТЕРАТУРА2§ 1. Введение.Понятие “алгоритм” давно является привычным не только дляматематиков. Оно является концептуальной основой разнообразных процессовобработки информации. Возможность автоматизации таких процессовобеспечивается наличием соответствующих алгоритмов.

С алгоритмами первоезнакомство происходит в нача-льной школе при изучении арифметическихдействий с натуральными числами. В упрощенном понимании “алго-ритм” - этото, что можно запрограммировать на ЭВМ.Слово алгоритм содержит в своем составе преобразованноегеографическое название Хорезм. Термин “алгоритм” обязан своимпроисхождением великому ученому средневекового Востока - Муххамад ибнМуса ал-Хорезми ( Магомет, сын Моисея, из Хорезма ). Он жил приблизительнос 783 по 850 гг., и в 1983 году отмечалось 1200 летие со дня его рождения вгороде Ургенче - областном центре современной Хорезмской областиУзбекистана. В латинских переводах с арабского арифметического трактата алХорезми его имя транскрибировалось как algorismi. Откуда и пошло слово“алгоритм” - сначала для обозначения алгоритмов цифровых вычисленийдесятичной позиционной арифметики, а затем для обозначения произвольныхпроцессов, в которых искомые величины решаемых задач находятсяпоследовательно из исходных данных по определенным правилам иинструкциям.Вплоть до 30-х годов нашего столетия понятие алгоритма оставалосьинтуитивно понятным, имевшем скорее методологическое, а не математическоезначение.

Так, к началу ХХ в. много ярких примеров дала алгебра и теориячисел. Среди них упомянем алгоритм Евклида нахождения наибольшего общегоделителя двух натуральных чисел или двух целочисленныхмногочленов,алгоритм Гаусса решения системы линейных уравнений над полем,алгоритм нахождения рациональных корней многочленов одного переменного срациональными коэффициентами, алгоритм Штурма определения числадействительных корней многочлена с действительными коэффициентами нанекотором отрезке действительных чисел, алгоритм разложения многочленаодного переменного над конечным полем на неприводимые множители.Указанные алгоритмические проблемы решены путем указания конкретныхразрешающих процедур. Для получения результатов такого типа достаточноинтуитивного понятия алгоритма. Однако, в начале ХХ в.

былисформулированы алгоритмические проблемы, положительное решение которыхпредставлялось маловероятным. Решение таких проблем потребовалопривлечения новых логических средств. Ведь одно дело доказать существованиеразрешающего алгоритма - это можно сделать, используя интуитивное понятиеалгоритма. Другое дело - доказать несуществование алгоритма - для этого нужнознать точно - что такое алгоритм.Задача точного определения понятия алгоритма была решена в 30-х годахв работах Гильберта, Черча, Клини, Поста, Тьюринга в двух формах: на основепонятия рекурсивной функции и на основе описания алгоритмического3процесса.

Рекурсивная функция это функция, для которой существует алгоритмвычисления ее значений по произвольному значению аргумента. Классрекурсивных функций был определен строго как конкретный класс функций внекоторой формальной системе. Был сформулирован тезис ( называемый “тезисЧерча” ), утверждающий, что данный класс функций совпадает с множествомфункций, для которых имеется алгоритм вычисления значений по значениюаргументов. Другой подход заключался в том, что алгоритмический процессопределяется как процесс, осуществимый на конкретно устроенной машине (называемой “машиной Тьюринга” ). Был сформулирован тезис ( называемый“тезис Тьюринга” ), утверждающий, что любой алгоритм может бытьреализован на подходящей машине Тьюринга.

Оба данных подхода, а такжедругие подходы ( Марков, Пост ) привели к одному и тому же классуалгоритмически вычислимых функций и подтвердили целесообразностьиспользования тезиса Черча или тезиса Тьюринга для решения алгоритмическихпроблем. Поскольку понятие рекурсивной функции строгое, то с помощьюобычной математической техники можно доказать, что решающая некоторуюзадачу функция не является рекурсивной, что эквивалентно отсутствию дляданной задачи разрешающего алгоритма. Аналогично, несуществованиеразрешающей машины Тьюринга для некоторой задачи равносильноравносильно отсутствию для нее разрешающего алгоритма.

Указанныерезультаты составляют основу так называемой дескриптивной теорииалгоритмов, основным содержанием которой является классификация задач попризнаку алгоритмической разрешимости, т.е. получение высказываний типа“Задача П алгоритмически разрешима” или “Задача П алгоритмическинеразрешима”. В данном направлении получен ряд фундаментальныхрезультатов. Среди них отрицательное решение Новиковым П.С. в 1952 годуклассической проблемы тождества для конечно определенных групп,сформулированной Деном в 1912 году. Знаменитая десятая проблема Гильберта,сформулированная им в 1900 году ( среди других 23 проблем ) формулируетсятак : “10. Задача о разрешимости диофантова уравнения.

Пусть заданодиофантово уравнение с произвольными неизвестными и целымирациональными числовыми коэффициентами. Указать способ, при помощикоторого возможно после конечного числа операций установить, разрешимо лиэто уравнение в целых рациональных числах”. Алгоритмическаянеразрешимость 10-й проблемы Гильберта была доказана в 1970 годуМятиясевичем Ю.В.В настоящее время теория алгоритмов образует теоретический фундаментвычислительных наук. Применение теории алгоритмов осуществляется как виспользовании самих результатов ( особенно это касается использованияразработанных алгоритмов ), так и в обнаружении новых понятий и уточнениистарых.

С ее помощью проясняются такие понятия как доказуемость,эффективность, разрешимость, перечислимость и другие.В технику термин “алгоритм” пришел вместе с кибернетикой. Понятиеалгоритма помогло, например, точно определить, что значит эффективно задатьпоследовательность управляющих сигналов. Применение ЭВМ послужилостимулом развитию теории алгоритмов и изучению алгоритмических моделей, к4самостоятельному изучению алгоритмов с целью их сравнения по рабочимхарактеристикам ( числу действий, расходу памяти ), а также их оптимизации.Возникло важное направление в теории алгоритмов - сложность алгоритмов ивычислений. Начала складываться так называемая метрическая теорияалгоритмов, основным содержанием которой является классификация задач поклассам сложности.