Элементы теории алгоритмов, Дурнев В.Г., 2008

Элементы теории алгоритмов, Дурнев В.Г., 2008.

   В учебном пособии рассматриваются основные понятия теории алгоритмов: машины Тьюринга, примитивно рекурсивные, рекурсивные и частично рекурсивные функции, рекурсивные и рекурсивно перечислимые множества, их нумерация, арифметизация теории машин Тьюринга, алгоритмически неразрешимые проблемы из теории алгоритмов, математической логики и алгебры, недетерминированные машины Тьюринга и классы NP и Р.
Пособие предназначено для студентов, обучающихся по направлениям 010100 Математика и 010500 Прикладная математика и информатика, специальности 090102 Компьютерная безопасность, очной формы обучения. Оно может быть использовано при изучении дисциплин “Математическая логика и теория алгоритмов”, “Теория алгоритмов”, “Математическая логика” и “Дискретная математика и математическая логика” (блок ОПД, ДС), а также специальных дисциплин.




Недетерминированные многоленточные машины Тьюринга.
В предыдущих параграфах рассматривался в определенном смысле простейший вариант машины Тьюринга - детерминированные машины Тьюринга с одной конечной лентой потенциально бесконечной в обе стороны. Как уже отмечалось выше, существуют различные варианты машин Тьюринга - с одной или с несколькими лентами, с дополнительной входной лентой, с входной, выходной и рабочей лентами, с многомерными лентами и т.д., детерминированные и недетерминированные. С точки зрения принципиальных вычислительных возможностей различные варианты машин Тьюринга эквивалентны. Однако особенности вычислительной модели играют существенную роль, когда нас интересует не только принципиальная возможность реализации того или иного алгоритма, но и сложностные характеристики его выполнения на рассматриваемой модели.

Рассматривавшиеся выше одноленточные машины Тьюринга являются детерминированными вычислительными устройствами - на каждом такте работы машина Тьюринга может выполнить лишь одну команду из своей программы, поэтому из текущего незаключительного состояния машина Тьюринга переходит в однозначно определенное следующее состояние.

ОГЛАВЛЕНИЕ.
Предисловие.
Введение.
ГЛАВА I. КОНЕЧНЫЕ АВТОМАТЫ И ЯЗЫКИ.
§1. Алфавиты. Слова.
§2. Конечные представления языков.
§3. Конечные автоматы.
§4. Конечные автоматы и регулярные выражения.
§5. Некоторые алгоритмические проблемы для языков.
§6. Минимизация автоматов.
§7. Конечные автоматы с выходом.
ГЛАВА II. ЧАСТИЧНО РЕКУРСИВНЫЕ ФУНКЦИИ.
§1. Примитивно рекурсивные и частично рекурсивные функции.
§2. Нумерационные функции.
§3. Рекурсивно перечислимые множества и предикаты.
ГЛАВА III. МАШИНЫ ТЬЮРИНГА.
§1. Машины Тьюринга.
§2. Арифметизация теории машин Тьюринга.
§3. Нумерация функций и множеств.
ГЛАВА IV. АЛГОРИТМИЧЕСКИЕ ПРОБЛЕМЫ.
§1. Арифметические множества и теорема А. Тарского.
§2. Проблема выводимости для полусистем Туэ и комбинаторная проблема Поста.
§3. Недетерминированные многоленточные машины Тьюринга.
ГЛАВА V. NР-ТРУДНЫЕ И NР-ПОЛНЫЕ ПРОБЛЕМЫ.
§1. NР-полнота проблемы выполнимости для формул логики высказываний.
§2. Сложность решения систем линейных уравнений.
§3. NР-полнота проблемы разрешимости для уравнений с нетривиальной правой частью в свободной полугруппе.
§4. NР-полные проблемы в теории графов.
§5. Алгоритмически неразрешимые проблемы в области защиты информации.
§6. Несколько NР-полных проблем.
Послесловие.
Литература.



Бесплатно скачать электронную книгу в удобном формате, смотреть и читать:
Скачать книгу Элементы теории алгоритмов, Дурнев В.Г., 2008 - fileskachat.com, быстрое и бесплатное скачивание.

Скачать djvu
Ниже можно купить эту книгу, если она есть в продаже, и похожие книги по лучшей цене со скидкой с доставкой по всей России.Купить книги


Скачать - djvu - Яндекс.Диск.




Теги: учебник по математике :: математика :: Дурнев