Логика, автоматы, алгоритмы

Научная библиотека

Научная библиотека

Логика, автоматы, алгоритмы

М. А. Айзерман, Л. А. Гусев, Л. И. Розоноэр И. М. Смирнова, А. А. Таль. Логика, автоматы, алгоритмы. М. - 1963.

Оглавление

ПРЕДИСЛОВИЕ
ВВЕДЕНИЕ
ГЛАВА 1. ЭЛЕМЕНТЫ МАТЕМАТИЧЕСКОЙ ЛОГИКИ
§ 1.2. Основные понятия
§ 1.3. Исчисление высказываний
б) Функции одной и двух переменных
в) Функции n переменных. Конъюнктивные и дизъюнктивные нормальные формы
г) Функции n переменных. Алгебра исчисления высказываний
§ 1.4. Об исчислении предикатов (двузначных)
ГЛАВА II. ТЕХНИЧЕСКИЕ ПРИЛОЖЕНИЯ ИСЧИСЛЕНИЯ ВЫСКАЗЫВАНИЙ
§ 2.1. Однотактные релейно-контактные схемы
§ 2.2. Анализ однотактных релейно-контактных схем
§ 2.3. Синтез однотактных релейно-контактных схем
§ 2.4. Иные методы технической реализации логических функций
б) Схемы на триодах
в) Схемы на магнитных элементах
д) Схемы на пневмореле
§ 2.5. Проблема минимизации устройств, реализующих логические функции
ГЛАВА III. ОБЩИЕ ПОНЯТИЯ О КОНЕЧНЫХ АВТОМАТАХ И ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИНАХ
§ 3.1. Дискретное время и такты
§ 3.2. О динамических системах
§ 3.3. Конечные автоматы
§ 3.4. Последовательностные машины
§ 3.5. Методы задания конечного автомата и последовательностной машины
§ 3.6. Методы записи работы автомата
§ 3.7. Замечание об ограничении входных последовательностей
ГЛАВА IV. АБСТРАКТНАЯ СТРУКТУРА И СЕТЬ
§ 4.1. Общие понятия о замещении последовательностных машин
§ 4.2. Абстрактная структура автомата
§ 4.3. Сеть
§ 4.4. Абстрактная агрегатизация автоматов и последовательностных машин
§ 4.5. Абстрактный нейрон и абстрактные модели нейронных сетей
ГЛАВА V. ТЕХНИЧЕСКАЯ РЕАЛИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ И ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИН
§ 5.1. Два метода технической реализации конечных автоматов и последовательностных машин
§ 5.2. Агрегатное построение конечных автоматов и последовательностных машин
§ 5.3. Построение конечных автоматов и последовательностных машин с использованием естественных задержек и обратных связей
§ 5.4. Метод и реализация Хафмана
а) Замечания о типе автомата или последовательностной машины
б) Построение таблицы переходов по заданной таблице последовательностной машины
в) Сокращение (сжатие) таблицы переходов
г) Составление таблицы релейной схемы
д) Реализация схемы по Хафману
ГЛАВА VI. АВТОНОМНЫЙ КОНЕЧНЫЙ АВТОМАТ И АВТОНОМНАЯ ПОСЛЕДОВАТЕЛЬНОСТНАЯ МАШИНА
§ 6.1. Что «могуть делать» автономный конечный автомат и автономная последовательностная машина
§ 6.2. Синтез двоичной структуры автономной последовательностной машины
ГЛАВА VII. ПРЕДСТАВЛЕНИЕ СОБЫТИЙ В КОНЕЧНОМ АВТОМАТЕ И ПОСЛЕДОВАТЕЛЬНОСТНОЙ МАШИНЕ
§ 7.2. Событие. Представление событий
§ 7.3. Действия над множествами входных последовательностей. Регулярные события
§ 7.4. Представимость регулярных событий
§ 7.5. Регулярность представимых событий
§ 7.6. Существуют ли нерегулярные (непредставимые) события?
§ 7.7. Что «может делать» конечный автомат
ГЛАВА VIII. РАСПОЗНАВАНИЕ РЕАЛИЗУЕМОСТИ ЗАДАНИЯ И АБСТРАКТНЫЙ СИНТЕЗ КОНЕЧНЫХ АВТОМАТОВ И ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИН
§ 8.2. Случай, когда задание перечисляет требуемые соответствия между входными и выходными последовательностями
§ 8.3. Алгоритмическая неразрешимость проблемы распознавания представимости рекурсивных событий
§ 8.4. Синтез конечных автоматов и последовательностных машин при задании, сформулированном на языке регулярных выражений
ГЛАВА IX. ЭКВИВАЛЕНТНОСТЬ И МИНИМИЗАЦИЯ ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИН
§ 9.2. Алгоритмическая неразрешимость проблемы распознавания эквивалентных состояний в общем случае
§ 9.3. Распознавание эквивалентности состояний в случае, когда множество входных последовательностей не ограничено
§ 9.4. Распознавание эквивалентности состояний в случае, когда ограничения наложены на длину входных последовательностей
§ 9.5. Понятия об эквивалентности, отображении и минимизации последовательностных машин
§ 9.6. Минимизация последовательностной машины в случае, когда множество входных последовательностей не ограничено
§ 9.7. Минимизация последовательностной машины в случае, когда она работает как конечный автомат
1. Множество L допустимых входных последовательностей содержит все возможные последовательности, т. е. L=E
2. Множество L не содержит последовательностей, имеющих два одинаковых символа подряд
§ 9.8. Минимизация последовательностных машин в случае ограничений типа Ауфенкампа
§ 9.9. Об ином определении эквивалентности последовательностных машин
ГЛАВА Х. ПРЕОБРАЗОВАНИЕ ТАКТНОСТИ ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИН
§ 10.1. Общие соображения о преобразовании тактности. Определение понятий изображения и воспроизведения
§ 10.2. Примеры изображения и воспроизведения
б. Линия задержки
§ 10.3. Воспроизведение медленной последовательностной машины быстрой машиной в случае, когда тактность медленной машины определяется сменой состояний на входе
§ 10.4. Минимизация воспроизводящей последовательностной машины, построенной в предыдущем параграфе
ГЛАВА XI. ОПРЕДЕЛЕНИЕ СВОЙСТВ ПОСЛЕДОВАТЕЛЬНОСТНЫХ МАШИН ПО ИХ РЕАКЦИИ НА ВХОДНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ КОНЕЧНОЙ ДЛИНЫ
§ 11.2. Определение эквивалентности состояний последовательностных машин по реакции машины на входные последовательности конечной длины
§ 11.3. Изучение последовательностных машин с помощью кратных экспериментов
§ 11.4. Изучение последовательностных машин с помощью простых экспериментов
ГЛАВА XII. АЛГОРИТМЫ
§ 12.1. Примеры алгоритмов
§ 12.2. Общие свойства алгоритмов
§ 12.3. Проблема слов в ассоциативном исчислении
§ 12.4. Алгоритм в некотором алфавите А. Нормальный алгоритм Маркова
§ 12.5. Сведение любого алгоритма к численному алгоритму. Гёделизация
§ 12.6. Элементарные и примитивно-рекурсивные функции
§ 12.7. Предикаты. Ограниченный оператор наименьшего числа
§ 12.8. Пример построения вычислимой, но не примитивно-рекурсивной функции
§ 12.9. Общерекурсивные функции. Определение Эрбрана — Гёделя
§ 12.10. Явная форма общерекурсивных функций
§ 12.11. Тезис Чёрча
§ 12.12. Рекурсивные действительные числа
§ 12.13. Рекурсивно-перечислимые и рекурсивные множества
ГЛАВА XIII. МАШИНЫ ТЬЮРИНГА
§ 13.1. Описание и примеры машин Тьюринга
§ 13.2. Композиция машин Тьюринга
§ 13.3. Вычисления на машинах Тьюринга
ЗАКЛЮЧЕНИЕ
§ 2. Последовательность синтеза технического устройства, реализующего конечный автомат или последовательностную машину
БИБЛИОГРАФИЯ