Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 93
Текст из файла (страница 93)
Проводим сечение по дугам (ХЗ> ХЭ)> (Хт> Хб)> (Х1> Хь)> (Хб> ХВ)> (Хт> Хе) ° На выходах автоматов хе, хь, хэ получаем правильные значения: хе = хб — — хэ — 1. Проводим второе сечение по дугам (ХЗ> Х2)> (ХЗ> Х1)> (Х10> Х1)> (Х10> Хб)> (Х10> ХТ). На выходах автоматов х2, х1, хб, хт получаем значения, соответствующие хз = 0: х1 — — хб = ху = 1. Следовательно, неисправен автомат хт, так квк хз ( х1, и, следовательно, третье сечение, разрывающее дугу (хз, ХЗ), реалйзовывать нет необходимости. В случае, если модель Ф, содержит запрещенные фигуры, их устранение осуществляется путем сужения ее сигнатуры.
Использование предлагаемого метода в практических разработках значительно уменьшает время диагностирования н упрощает контрольную аппаратуру. 25.14. Задачи и упрахиеиия $.1. Определить трудоемкость и емкостную сяоиность злгорптме сиитзксяческого эквивэлентнровзняк неорнеитнровзняого трефе в двудольный путем удзленяя ребер, если функшюиелом кзчестве кзлке>ск минимум удаленных ребер, $.2.
Проверить зыполненяе принципе локзльностн длк хзрзктеряззцнонной задачи креобрззоэзяия грефе в двудольный и отношевня подчинения "быть подгрефом" (попомним, что кодгреф отзичзется от чэстичного подгрзфз тем, что если в ием иег кзкЖ-либо вершины графа, то иет я всех инцндентпых ей в грзфе ребер). Обрэзуют ли циклы ихгетной длины мнояество ззпрешекных фигуру $.3. Определить отношение подчинения, удовлетворяющее принципу локзльнасти длк кроблешя >сзрзктериззцин гзмньътоиозых графов. $.4. Определить отношеяяе кодчннешгк, удовлетворшощее принципу пепельности для проблемы хэрзвтериэзции эйлеровых графов. $.$. Предлоиить алгоритмы сннтзксичесвого, эвристического и семзнтяческого эквивэлентироэзннк неориептнровзяных грэбюв в зйлеровы.
Сровнять трулоемкость и емкостпую слоиность алгоритмов. $.$. Выполнить семэнтнческое эквнвзлегпировэние графа С>, который является дополнением грзфе, изобрзяениого ио рис. 5.4,6, в двудольный граф Сз —— (>з, Уз) лля следующшс способов преобрззовзннй ззкрещенных фигур в рззрешенные н фунвционзлов качества: э) удзление нз нечетного днкле ребра, >з(Сз) = и>зх (Уз(; б) рзсаиеклеиие вершины нежтиого цикла, Ч>(Сз) = ппп (Уз).
$7. Докеззть, что ври удзленни коглошзющихск строк и столбцов (см. 1 5 2), применяемом для сокрзшеянк трудоемкостя изхозщеиня покрытнк семзнтпческой тзблицы, минимзльяое решеняе остэегск. $.8. Определить, кзлккяск ли неустойчивыми зекрешенные фягуры типов А и Б, присутствующие в могрзфе, приведенном из ряс. 5.10, а. $.9.
Домазать, чтр решение ззлечи теорепгко-структурной минимиээкни функции У(х> > хз, хз, ха)П = >/(2> 3, 4, 5, 8, 9, 11, 12, 14, 15) ареллоиенным в 1 5 4 методом, который основзи из фукяционзле (5.1), об солюпю минимально. У(ха хз ха, ха)(> = Ч(2> 3> 4 5 8, 9, 11, 12 13 14 15) $.14. Миннмвзировзть с учетом теоретико-структурных свойств булеву фуик- шоо >1 нз 1,3,4,7,9,12,14,28,31, $.1$. Синтезировать диаграмму Хассе мянкмзльной слоиности, реэлизую- щую систему булевых функций вила У>(х» хз, хз, ха)(> = >Г(1> 3, 4, 5, 6, 7, 9, 11, 13, 15), Уз(х» хз> ха> ха))> = П(1> 3, 5, 7> 9> 11, 12, 13> 14, 15), ааа(х» хз, хз, ха))> = Ч(1> 3, 5, 7, 8, 9, 10, 11, 13, 15), Уа(х>, хз, ха, ха))> = >Г(1> 2, 3, 5, 7, 9, 10, 11, 13, 15), Уа(х>, хз, ха, ха)(> = Ч(1, 2, 3, 5, 6, 7, 9, 11, 13, 15).
$.1$. Рэзлояять эвтомзт С, переходы которого заданы мзтрипей сменности а> аз аа аа аз аа а> аз аа' а(С)— аг ие двз несвязных кзрзллелыю фуикционвруюшнх звтомзтз. $.17. Нейти пределыюе рззлаиеине звтомете, зздзнного в упр. 5.16. $.18. Сннтезнровзть фуивционельиую декомпозшопо булевой функция 71 нз О, 2, 4, 7, 11, 14, 16, 21, 29, 30, У(хьхз, >хз)=),0 нэ 1 5,6 9,17,18 28 $.19. Синтезировать фунвциоиэльиую декомаозккшо трехзизчной функции 1'0 из 1, 2, 11, 14,86, 117, 240, У(х>, хз, ..., хз) = 1 иэ 3, 5, 17, 27, 39, 181, 222, 2 не 7,9,43,51,64,201. $.30.
Синтезнровзть нейрон, резлязующяй булеву функцию у(х>, хз, хз, ха)(> = >Г(0, 1, 2, 7, 11). $.10. Доказать, что решение зедечн теарепако-структурной минимизации системм булевых функций, зздзвеемой тзбл. 5.12 кредлоиенным в $ $.4 методом, который осиозен нз фуиккионэле (5.2), абсолютна минимельно. $.11. Определить ебстрзктную дорэллельную декомкозшооо звтомэтз (см, рис. 5.28, а), нзчинзя с построения второго кодзвтомзтз (имеющего четыре состояния).
Изменится ли результзт декомпознкниу $.13. Выволиить семзнтическое эквивзлентнровзняе могрзфз Ф (см. рис. 5.30, е) в циклнческвй Фь с фуявцнонзлом кзчесгвз (мннимум рэсщепленяй) и следующими спасобзми преобреэовзняк запрещенных фигур в разрешенные> з) рэсщепл>юие элементе носителя; б) ресщевление слово, $.13. Мииимнэировзть с учетом теоретико-структурных свойств булеву функ- дню 532 Гл.5. Прикладная теория алгоритмов $.31. Синтеаировать нейрон, реализующий булеву функцию /(хз, хг, хз, хз)(з = Ч(0, 1, 2, 4, 9, 14).
$.33. Вычислить трассы булевой функции /(хз, хг, хз, хз)(з = и(0, 1, 2, 4, 9). $.33. Вычислять анамальпучо область функционирования лагичесвай струвтуры, реалиэуюшей булеву фунвдию /(хи хг, хз, хз)(з = и(0, 1, 2, 7, 13). $.34. Вычислить трассы булевой фунацви /(хн хг, хз, хз)(з = и(0, 1, 2, 9, 1$). $.3$. Вычислить трассы булевой фунвции /(хз, хг, хз, хз))з ю и(0, 1, 2, 4, 7, б, 11). 3 5.15.
Комментарии Борьба с перебором вариантов при решении задач дисарепюй математики — одна из автуальиейшях проблем современного математичесвога обеспечения систем переработан информапни. Усвеха можно достичь, талька решая проблему хараатериэацни реализуемых модельшлх вреобрааований. Если яе хараатеризациониая вроблема не решена, та исвальауют эвристический подход в автнмнаацин аамбинатарных алгоритмов. Харавтеризаэмонцьзй анализ является метатеорией, аонструатявиа сюзэываюшей различные формальные системы иа семеитичесаом уровяе знаний, что паавацяет разрабатывать аринцвииальио новые инфармаююнные технологии решения враблемзпах задач большой раамериости иа лисаретиых струатурах.
В иастаяшее время интенсивна развивается перспевтивная пауза, позволташая с единых методологических а рюши воз исследовать и прагиааяровать общие законы развития мяврамира, мира, маврамира. Эта наука названа ее основателем академиком И.И. Юзэншиным ииформачиолоеией. СПИСОК ЛИТЕРАТУРЫ Автоматизация проектирования сложных логических структур /Под ред. В.А. Горбатова.— Мл Энергия, 1978.
Ахо А., Хопкрофт Дж., Ульмак Дж. Построение н анализ вычислительных алгоритмов.— Мл Мир, 1979. Гильберт Д., Бернайс П. Основания математики. Логические исчисления н формализация арифметики.— Мл Наука, 1979. ГорБатов В.А. Квазнполные графы и их некоторые свойства // Доклады НТК МЭИ. Вычислительная техника. — Мл МЗИ, 1965. — С. 3-10.
Горбатов В.А: О минимальной раскраске графа//Доклады НТК. МЗИ, 27 марта — 10 апреля 1964 г. Подсекция вычислительной техники.— Мл МЗИ, 1964.— С. 17. Горбатое В.А. Оценки при выборе направления вычислений в задачах синтеза конечных автоматов1Г Изв. АН СССР. Техническая кибернетика. †19. — № 4. — С, 91-101. Горбат оа В.А.
Семантическая теория проектирования автоматов.— Мл Энергия, 1979. Горбатое В.А. Синтез логических схем в многозначных логиках, основанный на структурных соотношениях//Многозначные элементы н структуры.— Мл Сов. радио, 1967. Горбатов В.А. Синтез логических схем в произвольном базисе // Теория дискретных автоматов.— Рига: Зннатне, 1967. 10.
Горбатов В,А. Схемы управления ЦВМ н графы.— М.: Энергия, 1971. 11. Горбатов В.А. Теория частично упорндоченных систем.— М.: Сов. радио, 1976. 12. Горбатов В.А., Кафаров В.В., Павлов П.Г. Логическое управление технологическими процессамн.— Мл Энергия, 1978. 13. Горбатов В.А., Останков Б.Л., Фролов СА. Регулярные структуры автоматного управления / Под ред.
В.А. Горбатова.— М.: Машиностроение, 1980. 14. Горбатое В.А,, Павлов П.Г., Четвериков В.П. Логическое управление информационными процессамн.— М.: Знергоатомнздат, 1984. 15. Горбатое В.А., Смирнов МИ., Хлытчиее Н.С. Логическое управление распределенными системами.— Мл Знергоатомнздат, 1991. 534 Список литеротпуры Список литературы 535 16. Горбатова М.В. Теория трасс у Информационные коммуникации, сети, системы и технологии.— Мл МАИ, 1993, 1Т. Гудман С., Хидентниеми С. Введение в разработку и анализ алгоритмов.— Мл Мир, 1981. 18.
Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи.— Мл Мир, 1982. 19. Зыков А.А. О некоторых свойствах линейных комплексов//Мат. сборник.— 1949.— Т. 24, Хт 2.— С. 163 — 188. 20. Змков А.А. Теория конечных графов.— Новосибирск: Наука, 1969. 21. Даэарев В.Г., Пийль Е.И. Синтез управляющих автоматов.— М.: Энергия, 1978. 22. Майника Э. Алгоритмы оптимизации на сетях и графах.— Мл Мир, 1981.
23. Мальцев А.И. Алгебраические системы.— Мл Наука, 1970. 24. Новиков П.С. Конструктивная математическая логика с точки зрения классической.— Мл Наука, 1977. 25. Общая теория систем.— Мл Мир, 1966. 26. Оре О. Теория графов.— Мл Наука, 1980. 2Т. Поспелов Д.А. Логике-лингвистические модели в системах управления.— Мл Энергия, 1981. 28. Рейнгольд Э.„Ниеергельтп ТО., Део Н.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
