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

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

Книга рассчитана на специалистов в области теоретической кибернетики и вычислительной техники, а также студентов и аспирантов соответствующих специальностей.

Илл. 163. Библ. 662 назв.

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

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

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

В последние годы при синтезе схем автоматов помимо логического аспекта важную роль приобретает комбинаторный аспект, который в значительной мере оказывает влияние на сложность схемы и решение которого связано с перебором. Следует отметить, что логическая теория синтеза автоматов достаточно хорошо развита в работах советских и зарубежных авторов, среди которых можно отметить работы К. Шеннона, В. И. Шестакова, Г. Мили, Э. Мура, М. А. Гаврилова, Дж. фон Неймана, С. Клини, В. М. Глушкова, С. В. Яблонского, С. Колдуэлла, М. Фистера, Г. Н. Поварова, О. Б. Лупанова, Ю. И. Журавлёва, Н. Е. Кобринского, Б. А. Трахтенброта, Э. А. Якубайтиса, Ж. Флорина, А. Д. Закревского, Д. А. Поспелова, 3. Л. Рабиновича, П. П. Пархоменко и многих других.

Комбинаторный аспект в логическом проектировании связан, в основном, с поиском оптимальных вариантов кодирования состояний, входных и выходных сигналов автомата и приводит к задачам декомпозиции сложных автоматов на более простые по тем или иным критериям. Среди работ, которые освещают вопросы комбинаторного порядка в логическом проектировании автоматов, необходимо отметить работы Хартманиса, Стёрнза, А. Гилла, Йоли, Кохави, М. А. Айзермана, Е. Н. Вавилова и др.

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

Книга содержит 9 глав. Главы I—IV посвящены методам теории графов, на которых основано решение задач логического проектирования автоматов. В них рассматриваются теоретико-множественные и алгебраические операции над ориентированными графами, определяются свойства операций и основные алгебраические структуры, которые они образуют по аналогии с известными структурами множеств. Решаются задачи разложения графов по алгебраическим и теоретико-множественным операциям. Доказываются теоремы о разложении графов по различным операциям, формулируются алгоритмы разложения, даются оценки числа разложимых графов, а также решается задача отыскания минимального дополнения неразложимых графов до разложимых. Главы V—IX посвящены изложению логического проектирования автоматов и вычислительных структур с помощью методов теории графов. Здесь излагается алгебра абстрактных автоматов, которая, на абстрактном уровне описывает различные виды соединений автоматов при построении схем сложных автоматов, и проблема декомпозиции абстрактных автоматов, которая заключается в представлении сложного абстрактного автомата совместной работой более простых абстрактных автоматов. Решается задача общей декомпозиции, позволяющая любой абстрактный автомат представлять работой элементарных абстрактных автоматов с минимальным числом связей между ними, и задача декомпозиции автомата на заданные блоки, которая приводит к представлению автомата в виде однородной структуры заданных стандартных блоков, соединённых между собой последовательно, параллельно или произвольным образом. Описывается декомпозиционный метод синтеза автоматов, основанный на решении задачи общей декомпозиции автоматов, исключающий этап структурного синтеза и приводящий к единому сквозному синтезу автоматов, который решает задачи логического проектирования на абстрактном уровне…

ПРЕДИСЛОВИЕ

Книги на ту же тему

1. Булева алгебра и конечные автоматы, Кунцман Ж., Наслен П., ред., 1969
2. Машины клеточных автоматов, Тоффоли Т., Марголус Н., 1991
3. Графы, сети и алгоритмы, Свами М., Тхуласираман К., 1984
4. Алгоритмы и вычислительные автоматы, Трахтенброт Б. А., 1974
5. Машины Тьюринга и рекурсивные функции, Эббинхауз Г. Д., Якобс К., Ман Ф. К., Хермес Г., 1972
6. Теория графов, Оре О., 1968
7. Графы и их применение, Оре О., 1965
8. Теория графов, Харари Ф., 1973
9. Эйлеровы графы и смежные вопросы, Фляйшнер Г., 2002
10. Группы и их графы, Гроссман И., Магнус В., 1971
11. Теория просачивания для математиков, Кестен X., 1986