Отправить другу/подруге по почте ссылку на эту страницуВариант этой страницы для печатиНапишите нам!Карта сайта!Помощь. Как совершить покупку…
московское время28.03.24 15:38:48
На обложку
Газохроматографический анализ природного газа: практическое…авторы — Другов Ю. С., Родин А. А.
Русская демократическая сатира XVII века. — 2-е изд., доп.Русская демократическая сатира XVII века. — 2-е изд., доп.
Нелинейная теория распространения волнавторы — Лайтхилл М., ред.
б у к и н и с т и ч е с к и й   с а й т
Новинки«Лучшие»Доставка и ОплатаМой КнигоПроводО сайте
Книжная Труба   поиск по словам из названия
Авторский каталог
Каталог издательств
Каталог серий
Моя Корзина
Только цены
Рыбалка
Наука и Техника
Математика
Физика
Радиоэлектроника. Электротехника
Инженерное дело
Химия
Геология
Экология
Биология
Зоология
Ботаника
Медицина
Промышленность
Металлургия
Горное дело
Сельское хозяйство
Транспорт
Архитектура. Строительство
Военная мысль
История
Персоны
Археология
Археография
Восток
Политика
Геополитика
Экономика
Реклама. Маркетинг
Философия
Религия
Социология
Психология. Педагогика
Законодательство. Право
Филология. Словари
Этнология
ИТ-книги
O'REILLY
Дизайнеру
Дом, семья, быт
Детям!
Здоровье
Искусство. Культурология
Синематограф
Альбомы
Литературоведение
Театр
Музыка
КнигоВедение
Литературные памятники
Современные тексты
Худ. литература
NoN Fiction
Природа
Путешествия
Эзотерика
Пурга
Спорт

/Наука и Техника/Математика

Ориентированные графы и конечные автоматы — Мелихов А. Н.
Ориентированные графы и конечные автоматы
Мелихов А. Н.
год издания — 1971, кол-во страниц — 416, тираж — 9000, язык — русский, тип обложки — твёрд. 7Б, масса книги — 460 гр., издательство — Физматлит
серия — Теоретические основы технической кибернетики
цена: 500.00 рубПоложить эту книгу в корзину
Сохранность книги — хорошая. Книжный знак прежнего владельца

Формат 84x108 1/32
ключевые слова — граф, конечн, автомат, комбинатор

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

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

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

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


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

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

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

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

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

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

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

ПРЕДИСЛОВИЕ

ОГЛАВЛЕНИЕ

Предисловие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. Параллельная поочередная декомпозиция автоматов290
§ 5. Последовательная декомпозиция автоматов297
§ 6. Общая декомпозиция абстрактных автоматов305
§ 7. Декомпозиция автоматов с выделением заданных стандартных
автоматов320
 
Г л а в а  IX.  Структурный синтез автоматов335
 
§ 1. Канонический метод синтеза автоматов335
§ 2. Построение функциональной схемы по графу автомата348
§ 3. Декомпозиционный метод синтеза автоматов355
§ 4. О синтезе автоматов в универсальных вычислительных средах367
 
Библиография381
Предметный указатель414

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

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

Напишите нам!© 1913—2013
КнигоПровод.Ru
Рейтинг@Mail.ru работаем на движке KINETIX :)
elapsed time 0.020 secработаем на движке KINETIX :)