Читать онлайн «Практикум по теории алгоритмов: Учебное пособие»

Министерство образования и науки Российской Федерации Национальный исследовательский ядерный университет «МИФИ» А. Н. Тихомирова, Н. В. Сафоненко Практикум по теории алгоритмов Рекомендовано УМО «Ядерные физика и технологии» в качестве учебного пособия для студентов высших учебных заведений Москва 2011 УДК 519. 712(075) ББК 22. 176. я7 Т46 Тихомирова А. Н. , Сафоненко Н. В. Практикум по теории алгоритмов: Учебное пособие. М. : НИЯУ МИФИ, 2011. – 132 с. Даны базовые понятия теории алгоритмов, основные определения, свойства и теоремы. Теоретическая часть изложена кратко и носит справочный характер, цель – дать основу для решения практических задач и подготовки к сдаче экзамена. В каждом разделе приведены типовые задачи и вопросы с подробными решениям. Материал ориентирован на темы, изучаемые на третьем семестре НИЯУ МИФИ в рамках дисциплины «Дискретная математика (Теория алгоритмов и сложность вычислений)». Приведенные задания для самостоятельной работы во многом покрывают контрольные экзаменационные задачи, а иногда и превосходят их по сложности. Предназначено студентам, изучающим курс «Дискретная математика (Теория алгоритмов и сложность вычислений)», а также всем, кто интересуется классическими формальными моделями представления алгоритмов, вопросами алгоритмической разрешимости, эффективной перечислимостью и вычислимостью чисел и функций, рекурсивными функциями. Подготовлено в рамках Программы создания и развития НИЯУ МИФИ. Рецензент канд. физ. -мат. наук, доц. А. З. Насыров ISBN 978-5-7262-1468-9 © Национальный исследовательский ядерный университет «МИФИ», 2011 ОГЛАВЛЕНИЕ Глава 1. Формальные описания алгоритмов ... ... ... ... ... ... ... ... ... ... ... 5 1. 1. Классические машины Тьюринга ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5 1. 1. 1. Теоретическая основа ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . . 5 1. 1. 2. Программы для одноленточных машин Тьюринга ... ... . . 6 Задачи для самостоятельной работы... ... ... ... ... ... ... ... ... ... ... ... ... ... 7 1. 2. Многоленточные машины Тьюринга ... ... ... ... ... ... ... ... . . ………. . 26 1. 2. 1. Теоретическая основа ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 26 1. 2. 2. Программы для многоленточных машин Тьюринга ... . 27 Задачи для самостоятельной работы... ... ... ... ... ... ... ... ... ... ... ... ... . 28 1. 3. Нормальные алгоритмы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 32 1. 3. 1. Теоретическая основа ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 32 1. 3. 2. Программы в формате алгоритмов Маркова... ... ... ... ... . . 33 Задачи для самостоятельной работы... ... ... ... ... ... ... ... ... ... ... ... ... . 35 1. 4. Преобразования машин Тьюринга ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 43 1. 5. Алгоритмически неразрешимые задачи ... ... ... ... ... ... ... ... ... ... ... . . 43 1. 6. Эффективная перечислимость и распознаваемость множеств ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 44 Проверочные задания и вопросы ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... . 46 Глава 2.