Обложка Карпов Ю. Теория автоматов: Учебник для вузов
Id: 23394

Теория автоматов:
Учебник для вузов

2003. 208 с. ISBN 5-318-00537-3.
  • Твердый переплет

Аннотация

Эта книга служит формированию знаний и умений, которые образуют теоретический фундамент, необходимый для корректной постановки и решения проблем в области информатики, для осознания целей и ограничений при создании вычислительных структур, алгоритмов и программ обработки информации.

В этом учебнике практическое использование моделей не является частной иллюстрацией теоретических результатов — наоборот, автор постарался практические проблемы ...(Подробнее)проектирования и анализа систем сделать отправной точкой, а формальный аппарат — средством систематического решения этих проблем.

В каждом разделе книги важное внимание уделено вопросам абстрагирования и адекватной интерпретации и реализации результатов аналитических преобразований.

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


Содержание

Введение
От издательства

ГЛАВА 1. Конечные функциональные преобразователи
Постановка проблемы
Булевы функции
Свойства булевых функций
Нормальные формы представления булевых функций
Преобразование в нормальную форму
Реализация булевых функций
Минимизация булевых функций
Функциональная полнота
Алгебра Жегалкина и линейные функции
Замкнутые классы булевых функций
Теорема Поста
Формы представления булевых функций
Семантические деревья
Бинарные диаграммы решений — БДР
Булевы алгебры
Пороговая логика
Контрольные задания
ГЛАВА 2. Введение в математическую логику
Формальные модели
Логика высказываний
Формулировка и доказательство теорем
Проверка доказательных рассуждений
Силлогизмы
Логическое следствие
Основная теорема логического вывода
Приведение к нормальным формам
Метод резолюции
Другие методы
Адекватность логики высказываний
Основы логики предикатов и логического вывода
Предикаты
Свободные и связанные переменные
Интерпретации
Равносильности логики предикатов
Ограниченные предикаты
Логический вывод в логике предикатов
Скулемовская стандартная форма
Алгоритм унификации
Логическое программирование
Логический вывод в Прологе
Стратегии вывода
Применение логического вывода для анализа схем
Экспертные системы
Контрольные задания
ГЛАВА 3. Конечные автоматы
Автоматное преобразование информации
Реализация КА
Эквивалентность КА: теорема Мура
Минимизация КА
Автоматы Мили и Мура
Примеры КА
Триггеры
Электронные часы
Схема управления микрокалькулятором
Команды операционной системы UNIX
Реактивные системы
Протокол РАR передачи сообщений в сетях
Протокол выбора лидера в распределенной системе
Визуальный формализм представления моделей реактивных систем: Statecharts
Протокол IEEE 802.12
Автомат, регулирующий пешеходный переход
Графы переходов при спецификации и анализе параллельных программ
Проблема умножения: алгоритм, который не может выполнить КА
Алгебраическая структурная теория конечных автоматов
Кодирование внутренних состояний конечного автомата
Разбиения и частично упорядоченные множества
Универсальные алгебры и конгруэнции
Последовательная декомпозиция конечных автоматов
Параллельная декомпозиция конечных автоматов
Алгоритм поиска конгруэнций конечного автомата
Контрольные задания
ГЛАВА 4. Автоматные языки
Языки
Грамматики. Автоматные грамматики и языки
Лемма о накачке
Эквивалентность и минимизация конечноавтоматных распознавателей
Недетерминированные конечно-автоматные распознаватели
Синтаксические диаграммы. Связь синтаксических диаграмм и автоматных языков
Трансляторы автоматных языков
Транслятор языка ЛИНУР
Транслятор языка EXPR
Регулярные множества и регулярные выражения
Регулярные множества
Регулярные выражения
Теорема Клини
Контрольные задания
ГЛАВА 5. Машины Тьюринга
Формальные модели алгоритмов
Понятие алгоритма
Формализация понятия алгоритма
Машина Тьюринга
Примеры машин Тьюринга
Свойства машины Тьюринга
Реализация машины Тьюринга
Универсальная машина Тьюринга
Алгоритмически неразрешимые проблемы
Частично разрешимые проблемы
Контрольные задания

Литература