Тихомирова А.Н., Сафоненко Н.В. Практикум по теории алгоритмов

М.: НИЯУ МИФИ, 2011. – 132 с. Даны базовые понятия теории алгоритмов, основные определения, свойства и теоремы. Теоретическая часть изложена кратко и носит справочный характер, цель – дать основу для решения практических задач и подготовки к сдаче экзамена. В каждом разделе приведены типовые задачи и вопросы с подробными решениям. Материал ориентирован на темы, изучаемые на третьем семестре НИЯУ МИФИ в рамках дисциплины «Дискретная математика (Теория алгоритмов и сложность вычислений)». Приведенные задания для самостоятельной работы во многом покрывают контрольные экзаменационные задачи, а иногда и превосходят их по сложности. Предназначено студентам, изучающим курс «Дискретная математика (Теория алгоритмов и сложность вычислений)», а также всем, кто интересуется классическими формальными моделями представления алгоритмов, вопросами алгоритмической разрешимости, эффективной перечислимостью и вычислимостью чисел и функций, рекурсивными функциями. Подготовлено в рамках Программы создания и развития НИЯУ МИФИ. Содержание
Формальные описания алгоритмов
Классические машины Тьюринга
Теоретическая основа
Программы для одноленточных машин Тьюринга
Задачи для самостоятельной работы
Многоленточные машины Тьюринга
Теоретическая основа
Программы для многоленточных машин Тьюринга
Задачи для самостоятельной работы
Нормальные алгоритмы
Теоретическая основа
Программы в формате алгоритмов Маркова
Задачи для самостоятельной работы
Преобразования машин Тьюринга
Алгоритмически неразрешимые задачи
Эффективная перечислимость и распознаваемость множеств
Проверочные задания и вопросы
Числовые множества
Классификация и мощность множеств
Счетность и эффективная перечислимость числовых множеств
Вычислимость чисел
Проверочные задания и вопросы
Арифметические вычисления
Арифметические и частичные
арифметические функции
Эффективная перечислимость
и распознаваемость арифметических функций
Проверочные задания и вопросы
Рекурсивные функции
Примитивно-рекурсивные функции
Теоретическая основа
Методология составления схем
примитивной рекурсии
Методология восстановления примитивно-рекурсивных функций из схем примитивной рекурсии
Общерекурсивные и частично-рекурсивные функции
Теоретическая основа
Обращение функций
Дополнительные способы задания примитивно-рекурсивных функций
Методология нахождения значений частично-рекурсивных функций на основе систем рекурсивных уравнений
Эффективная перечислимость и распознаваемость рекурсивных функций
Проверочные задания и вопросы
Сложность алгоритмов
Теоретическая основа
Методология оценки сложности
Проверочные задания и вопросы
Ответы на проверочные задания и вопросы
Список использованной литературы