Читать онлайн «Теория алгоритмов»

Федеральное агентство по образованию Московский инженерно-физический институт (государственный университет) А. Н. Тихомирова Теория алгоритмов Рекомендовано УМО «Ядерные физика и технологии» в качестве учебного пособия для студентов высших учебных заведений Москва 2008 УДК 519. 712(075) ББК 22. 176. я7 Т46 Тихомирова А. Н. Теория алгоритмов: Учебное пособие. М. : МИФИ, 2008. 176 с. Книга посвящена теории алгоритмов и содержит основные сведения о свойствах алгоритмов и способах их формального представления (машины Тьюринга, алгоритмы Маркова, рекурсивные функции). Изложены основы теории бесконечных множеств, рассмотрены вопросы нахождения эффективных процедур для перечисления объектов различной природы. Затронуты проблемы алгоритмической неразрешимости и базовые понятия сложности алгоритмов. Книга представляет интерес для студентов технических вузов, аспирантов, научных работников и всех, интересующихся теорией алгоритмов и связанными с ней аспектами истории развития математики. Работа подготовлена в рамках Инновационной образовательной программы МИФИ. Рецензент д-р техн. наук, доц. Андросов В. А. ISBN 978-5-7262-1078-0 © Московский инженерно- физический институт (государственный университет), 2008  Оглавление Предисловие ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 5 Введение ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 6 Глава 1. Формальные описания алгоритмов... ... ... ... ... ... ... ... ... . . 7 § 1. 1. Алгоритмы: определение и основные свойства... ... ... ... ... ... ... ... . . 7 § 1. 2. Классические машины Тьюринга... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 9 § 1. 3. Специальные машины Тьюринга ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 20 § 1. 4. Теоремы Шеннона ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 27 § 1. 5. Алгоритмически неразрешимые задачи ... ... ... ... ... ... ... ... ... ... ... ... . 34 § 1. 6. Нормальные алгоритмы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 47 § 1. 7. Эффективные перечислимость и распознаваемость ... ... ... ... ... . . 49 Задачи к главе 1 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 56 Глава 2. Числовые множества ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 62 § 2. 1. Множества: определение и основные свойства ... ... ... ... ... ... ... ... . 62 § 2. 2. Классификация множеств ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 64 § 2. 3. Счетные множества ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 67 § 2. 4. Несчетные множества ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 78 § 2. 5. Множества с мощностью, больше чем мощность континуума 91 § 2. 7. Вычислимые числа ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 104 Задачи к главе 2 ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 105 Глава 3.