Элементы теории алгоритмов: учебное пособие

Description

Элементы теории алгоритмов. Дурнев В.Г. Ярославль: ЯрГУ, 2008. 248 с. ISBN 978-5-8397-0622-4 Оглавление Предисловие Введение Глава I. Конечные автоматы и языки § 1. Алфавиты. Слова § 2. Конечные представления языков § 3. Конечные автоматы § 4. Конечные автоматы и регулярные выражения § 5. Некоторые алгоритмические проблемы для языков § 6. Минимизация автоматов § 7. Конечные автоматы с выходом Глава II. Частично рекурсивные функции § 1. Примитивно рекурсивные и частично рекурсивные функции § 2. Нумерационные функции § 3. Рекурсивно перечислимые множества и предикаты Глава III. Машины Тьюринга § 1. Машины Тьюринга § 2. Арифметизация теории машин Тьюринга § 3. Нумерация функций и множеств Глава IV. Алгоритмические проблемы § 1. Арифметические множества и теорема А. Тарского § 2. Проблема выводимости для полусистем Туэ и комбинаторная проблема Поста § 3. Недетерминированные многоленточные машины Тьюринга Глава V. NP-трудные и NP-полные проблемы § 1. NP-полнота проблемы выполнимости для формул логики высказываний § 2. Сложность решения систем линейных уравнений § 3. NP-полнота проблемы разрешимости для уравнений с нетривиальной правой частью в свободной полугруппе § 4. NP-полные проблемы в теории графов § 5. Алгоритмически неразрешимые проблемы в области защиты информации § 6. Несколько NP-полных проблем Послесловие Литература