Математика	Физика	Химия	Биология	Техника и технологии
	Ориентированные графы и конечные автоматы. Мелихов А. Н., Главная редакция физико-математической литературы изд-ва «Наука», М., 1971, 416 стр. В монографии рассматриваются вопросы преобразования ориентированных графов и излагается систематический подход к логическому проектированию автоматов методами теории графов. Описываются свойства теоретико-множественных и алгебраических операций над графами и решаются задачи разложения сложных графов на более простые по различным операциям. Определяются основные понятия теории автоматов и формулируются алгоритмы абстрактного анализа и синтеза автоматов. Изучается алгебра абстрактных автоматов и рассматривается проблема декомпозиции автоматов. Книга рассчитана на специалистов в области теоретической кибернетики и вычислительной техники, а также студентов и аспирантов соответствующих специальностей. Илл. 163. Библ. 662 назв.
ОГЛАВЛЕНИЕ Предисловие.................... 8 Глава I. Некоторые понятия теории графов....., . 11 § 1. Ориентированные графы и мультиграфы. Способы задания графов ................ 11 § 2. Смешанные графы .............. 17 § 3. Проблема изоморфизма и изоморфного вложения графов .................... 22 § 4. Алгоритм распознавания изоморфизма графов .... 23 § 5. Об изоморфном вложении графов......... 29 Глава II. Теоретико-множественные свойства графов .... 34 § 1. Графы и подграфы.............. 34 § 2. Операции объединения, пересечения и соединения гра,- фов .................... 40 § 3. Основные свойства операций. Дистрибутивные и булевы структуры графов............... 50 § 4. Графы и функции ............... 59 Глава III. Алгебраические свойства графов...... . 64 § 1. Декартово произведение множеств........ 64 § 2. Умножение, суммирование, композиция и суперпозиция графов................... 70 § 3. Множество операций объединяющего и суперпозиционного типов. Теорема двойственности...... 80 § 4. Множество операций пересекающего типа..... 87 § 5. Представление алгебраических операций......89 § 6. Преобразования матриц смежности графов. Операции над смешанными графами , , , , ,...... .92 Глава IV. Разложение графов по алгебраическим и теоретико-множественным операциям............. 99 § 1. Постановка задачи разложения графов...... 99 § 2. Теорема разложения графа в произведение двух графов 102 § 3. Алгоритм разложения графа по операции умножения 112 § 4. О разложении мультиграфов.......... 116 § 5. Дополнение неразложимых графов до разложимых . 120 § 6. Представление произвольного графа объединением произведений графов ............. 126 § 7. Теорема разложения графа в сумму двух графов . . 130 § 8. Оценка числа графов, разложимых по операции суммирования ................. 137 § 9. Разложение графов по операции композиции .... 138 § 10. Разложение графов по операции суперпозиции . . . 144 Глава V. Основные понятия теории автоматов..... 154 § 1. Автоматы первого и второго рода. Способы 'задания абстрактных автоматов............. 154 § 2. Представление событий в автоматах....... 172 § 3. Задачи анализа и синтеза автоматов....... 182 § 4. Об изоморфизме и изоморфном вложении абстрактных автоматов ................. 187 Глава VI. Абстрактный анализ и синтез автоматов .... 196 § 1. Основные понятия теории линейных-переходных графов 196 § 2. Алгоритм анализа автоматов..........201 § 3. Минимальная форма регулярного выражения .... 207 § 4. Задание регулярных выражений в форме графов . .212 § 5. Алгоритм синтеза автоматов..........216 Глава VII. Алгебра абстрактных автоматов.......227 § 1. О содержательном смысле операций над автоматами . 227 § 2. Теоретико-множественные операции над автоматами . 235 § 3. Алгебраические операции над автоматами.....240 § 4. Операции над вероятностными автоматами.....265 Глава VIII. Декомпозиция абстрактных автоматов .... 273 § 1. Постановка задачи декомпозиции, автоматов .... 273 § 2. Параллельная декомпозиция автоматов с разделением входов ...................276 § 3. Параллельная декомпозиция автоматов с общим входом 283 § 4. Параллельная поочередная декомпозиция автоматов . 29.0 .»• § 5. Последовательная декомпозиция автоматов ..... 297 & 6 Общая декомпозиция абстрактных автоматов .... 305 \| 7. Декомпозиция автоматов с выделением заданных стан- ^ дартных автоматов .............. 335 Глава IX. Структурный синтез автоматов........ & 1 Канонический метод синтеза автоматов .....» \| 2 Построение функциональной схемы по графу автомата 348 Б 3 Декомпозиционный метод синтеза автоматов . . . . <юо § 4! О синтезе автоматов в универсальных вычислительных ^ средах ............ ......381 Библиография............ „......414 Предметный указатель....... • • Цена: 150руб.*
Назад	Заказ	На главную страницу