Теория автоматов
Карпов Ю.Г.
Эта книга служит формированию знаний и умений, которые образуют теоретический фундамент, необходимый для корректной постановки и решения проблем в области информатики, для осознания целей и ограничений при создании вычислительных структур, алгоритмов и программ обработки информации.
В этом учебнике практическое использование моделей не является частной иллюстрацией теоретических результатов - наоборот, автор постарался практические проблемы проектирования и анализа систем сделать отправной точкой, а формальный аппарат - средством систематического решения этих проблем. В каждом разделе книги большое внимание уделено вопросам абстрагирования и адекватной интерпретации и реализации результатов аналитических преобразований.
Усвоение рассмотренных в книге моделей теоретической информатики, способов их анализа и синтеза должно создать основу, позволяющую читателю воспринимать и усваивать многие другие общетехнические и специальные дисциплины по информационным технологиям, вычислительным средствам и системам, инструментарию и методам проектирования программных систем, входящим в программу высшей школы.
Книга допущена Министерством образования Российской Федерации в качестве учебника для студентов высших учебных заведений, обучающихся по направлению подготовки бакалавров «Информатика и вычислительная техника» и по специальности «Вычислительные машины, комплексы, системы и сети» направления подготовки дипломированных специалистов «Информатика и вычислительная техника».
СПб.: Питер, 2003.
ISBN 5-318-00537-3
Количество страниц: 208.
Содержание книги «Теория автоматов»:
- 6 Введение
- 7 От издательства
- 8 ГЛАВА 1. Конечные функциональные преобразователи
- 8 Постановка проблемы
- 11 Булевы функции
- 17 Свойства булевых функций
- 14 Нормальные формы представления булевых функций
- 15 Преобразование в нормальную форму
- 16 Реализация булевых функций
- 17 Минимизация булевых функций
- 22 Функциональная полнота
- 24 Алгебра Жегалкина и линейные функции
- 26 Замкнутые классы булевых функций
- 27 Теорема Поста
- 32 Формы представления булевых функций
- 32 Семантические деревья
- 32 Бинарные диаграммы решений - БДР
- 34 Булевы алгебры
- 36 Пороговая логика
- 37 Контрольные задания
- 40 ГЛАВА 2. Введение в математическую логику
- 40 Формальные модели
- 44 Логика высказываний
- 48 Формулировка и доказательство теорем
- 50 Проверка доказательных рассуждений
- 52 Силлогизмы
- 54 Логическое следствие
- 57 Основная теорема логического вывода
- 57 Приведение к нормальным формам
- 58 Метод резолюции
- 61 Другие методы
- 61 Адекватность логики высказываний
- 62 Основы логики предикатов и логического вывода
- 62 Предикаты
- 65 Свободные и связанные переменные
- 65 Интерпретации
- 66 Равносильности логики предикатов
- 68 Ограниченные предикаты
- 71 Логический вывод в логике предикатов
- 71 Скулемовская стандартная форма
- 73 Алгоритм унификации
- 78 Логическое программирование
- 79 Логический вывод в ПРОЛОГЕ
- 80 Стратегии вывода
- 84 Применение логического вывода для анализа схем
- 85 Экспертные системы
- 88 Контрольные задания
- 95 ГЛАВА 3. Конечные автоматы
- 96 Автоматное преобразование информации
- 99 Реализация КА
- 102 Эквивалентность КА: теорема Мура
- 106 Минимизация КА
- 110 Автоматы Мили и Мура
- 112 Примеры КА
- 112 Триггеры
- 112 Электронные часы
- 114 Схема управления микрокалькулятором
- 118 Команды операционной системы LINUX
- 118 Реактивные системы
- 119 Протокол PAR передачи сообщений в сетях
- 121 Протокол выбора лидера в распределенной системе
- 124 Визуальный формализм представления моделей реактивных систем: Statecharts
- 125 Протокол IEEE 802.12
- 126 Автомат, регулирующий пешеходный переход
- 127 Графы переходов при спецификации и анализе параллельных программ
- 131 Проблема умножения: алгоритм, который не может выполнить КА
- 132 Алгебраическая структурная теория конечных автоматов
- 133 Кодирование внутренних состояний конечного автомата
- 136 Разбиения и частично упорядоченные множества
- 139 Универсальные алгебры и конгруэнции
- 142 Последовательная декомпозиция конечных автоматов
- 143 Параллельная декомпозиция конечных автоматов
- 143 Алгоритм поиска конгруэнции конечного автомата
- 146 Контрольные задания
- 96 Автоматное преобразование информации
- 151 ГЛАВА 4. Автоматные языки
- 152 Языки
- 153 Грамматики. Автоматные грамматики и языки
- 158 Лемма о накачке
- 160 Эквивалентность и минимизация конечно-автоматных распознавателей
- 163 Недетерминированные конечно-автоматные распознаватели
- 167 Синтаксические диаграммы. Связь синтаксических диаграмм и автоматных языков
- 168 Трансляторы автоматных языков
- 170 Транслятор языка ЛИНУР
- 172 Транслятор языка EXPR
- 174 Регулярные множества и регулярные выражения
- 174 Регулярные множества
- 174 Регулярные выражения
- 176 Теорема Клини
- 183 Контрольные задания
- 187 ГЛАВА 5. Машины Тьюринга
- 188 Формальные модели алгоритмов
- 188 Понятие алгоритма
- 188 Формализация понятия алгоритма
- 190 Машина Тьюринга
- 193 Примеры машин Тьюринга
- 194 Свойства машины Тьюринга
- 196 Реализация машины Тьюринга
- 198 Универсальная машина Тьюринга
- 198 Алгоритмически неразрешимые проблемы
- 202 Частично разрешимые проблемы
- 202 Контрольные задания
- 188 Формальные модели алгоритмов
- 204 Литература
Инструкция как скачать книгу Карпов Ю.Г.: Теория автоматов в форматах DjVu, PDF, DOC или fb2 совершенно бесплатно.
