Введение в теорию автоматов, языков и вычислений
- Автор(ы)
- Хопкрофт Д, Мотвани Р, Ульман Дж
- Год
- 2008
- Язык
- rus
- ISBN
- 978-5-8459-1347-0
- Теги
- Программирование Языкознание
Аннотация
Введение в теорию автоматов, языков и вычислений Год издания : 2008 Авторы : Хопкрофт Д., Мотвани Р., Ульман Дж. Переводчики : Вясылык О.И., Саит-Аметов М., Ставровский А.Б. Жанр или тематика : Научно-популярное введение в дисциплину Издательство : М.: ИД “Вильямс” ISBN : 978-5-8459-1347-0 Язык : Русский Формат : PDF Качество : Издательский макет или текст (eBook) Интерактивное оглавление : Да Количество страниц : 529 Тираж : 1000 экз. Описание : 2-е, переработанное издание. Книга известных американских ученых посвящена теории автоматов и соответствующих формальных языков и грамматик - как регулярных, так и контекстно-свободных. Во второй части рассматриваются различные машины Тьюринга, при помощи которых формализуются понятия разрешимых и неразрешимых проблем, а также определяются функции временнóй и емкостной оценки сложности алгоритмов. Изложение ведется строго, но доступно, и сопровождается многочисленными примерами, а также задачами для самостоятельного решения. Книга будет полезна читателям различных категорий - студентам, аспирантам, научным сотрудникам, преподавателям высших учебных заведений, а также всем, кто интересуется математическими основами современной вычислительной техники. Примеры страниц Оглавление Предисловие 14 Как пользоваться книгой 15 Требования к уровню подготовки 15 Упражнения 16 Поддержка в World Wide Web 16 Благодарности 16 Глава 1. Автоматы: методы и понятия 17 1.1. Зачем изучается теория автоматов? 18 1.1.1. Введение в теорию конечных автоматов 18 1.1.2. Структурные представления 20 1.1.3. Автоматы и сложность 21 1.2. Введение в теорию формальных доказательств 21 1.2.1. Дедуктивные доказательства 22 1.2.2. Сведение к определениям 25 1.2.3. Другие формы теорем 27 1.2.4. Теоремы без гипотезы 30 1.3. Дополнительные схемы доказательств 30 1.3.1. Доказательства эквивалентностей, связанных с множествами 30 1.3.2. Контрапозиция 32 1.3.3. Доказательство методом "от противного" 33 1.3.4. Контрпримеры 34 1.4. Индуктивные доказательства 36 1.4.1. Индукция по целым числам 36 1.4.2. Более общие формы целочисленных индуктивных доказательств 39 1.4.3. Структурная индукция 40 1.4.4. Совместная индукция 43 1.5. Основные понятия теории автоматов 45 1.5.1. Алфавиты 45 1.5.2. Цепочки 46 1.5.3. Языки 47 1.5.4. Проблемы 48 Резюме 50 Литература 52 Глава 2. Конечные автоматы 53 2.1. Неформальное знакомство с конечными автоматами 54 2.1.1. Основные правила 54 2.1.2. Протокол 55 2.1.3. Возможность игнорирования автоматом некоторых действий 57 2.1.4. Система в целом как автомат 59 2.1.5. Проверка протокола с помощью автомата-произведения 61 2.2. Детерминированные конечные автоматы 61 2.2.1. Определение детерминированного конечного автомата 62 2.2.2. Как ДКА обрабатывает цепочки 62 2.2.3. Более простые представления ДКА 64 2.2.4. Расширение функции переходов на цепочки 65 2.2.5. Язык ДКА 68 2.2.6. Упражнения к разделу 2.2 69 2.3. Недетерминированные конечные автоматы 71 2.3.1. Неформальное описание недетерминирован