Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

§5.14. Задачи и упражнения 531

5.10. Доказать, что решение задачи теоретико-структурной минимизации

системы булевых функций, задаваемой табл. 5.12 предложенным в § 5.4 мето

дом, который осиоваи на функционале (5.2), абсолютно минимально.

5.11. Определить абстрактную параллельную декомпозицию автомата (см.

рис. 5.28, а), начиная с построения второго подавтомата (имеющего четыре со

стояния). Изменится ли результат декомпозиции?

5.12. Выполнить семантическое эквивалентирование мографа (см.

рис. 5.30, в) в циклический Фь с функционалом качества (минимум расщепле

ний) и следующими способами преобразования запрещенных фигур в разрешен

ные: а) расщепление элемента носителя; б) расщепление слова.

5.13. Минимизировать с учетом теоретико-структурных свойств булеву функ

цию

/(*1, х2, х3, **)|i = V(2, 3,. 4, 5, 8, 9, 11, 12, 13, 14, 15).

5.14. Минимизировать с учетом теоретико-структурных свойств булеву функ

цию

с, - / 1 на 3' 4- 7- 9- 12’ 14' 28’ 31-

д * 1, *а, ..., * s )- ^ 0 иа 0 ,2 ,5 ,1 0 ,1 6 ,2 8 .

5.15. Синтезировать диаграмму Хассе минимальной сложности, реализую

щую систему булевых функций вида

fi(xi, хз, хз, i:4)|i = V(l, 3, 4, 5, 6, 7, 9, 11, 13, 15),

fi(xu Xi, x3, i 4)|i = V(l, 3, 5, 7, 9, 11, 12, 13, 14, 15),

/«(*1, *2. is, **)|i = V(l, 3, 5, 7, 8, 9, 10, 11, 13, 15),

/«(*i, *2, is, H)|i =V (1, 2, 3, 5, 7, 9, 10, 11, 13, 15),

fs(xi, Xi, хз, i4)|i = V(l, 2, 3, 5, 6, 7, 9, 11, 13, 15).

5.16. Разложить автомат G, переходы которого заданы матрицей смежности

31 32 *3 94 9$ 96 *7

-(G) =

11 6

3 V 8 11

2 1 3

1 4

6 4 9

7 6 2

*4 ’

«5

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

5.17. Найти предельное разложение автомата, заданного в упр. 5.16.

5.18. Синтезировать функциональную декомпозицию булевой функции

f(x, - / 1 на °- 2- 4> 7' 14> 16> 21' 29' 30-

Л * 1, х2, . . . , xs) - „ j , l t 5, 6, 9, 17, 18, 28.

5.19. Синтезировать функциональную декомпозицию трехзиачной функции

Дх 1, х3, ..., xs)

иа 1, 2, 11, 14, 86, 117, 240,

иа 3, 5, 17, 27, 39, 181, 222,

на 7, 9, 43, 51, 64, 201.

5.20. Синтезировать нейрон, реализующий булеву функцию

f(x 1, а , х3, i 4)|i = V(0, 1, 2, 7, 11).

532

Гл. 5. Прикладная теория алгоритмов

5.21. Синтезировать нейрон, реализующий булеву функцию

/(х 1, х2, хз, x4)|i = V(0, 1, 2, 4, 9, 14).

5.22. Вычислить трассы булевой функции

/(*1, Х2, Хз, x«)|i = v(0, 1, 2, 4, 9).

5.23. Вычислить аномальную область функционирования логической струк

туры, реализующей булеву функцию

/(х 1, х2, х3, x«)|i = V(0, 1, 2, 7, 13).

5.24. Вычислить трассы булевой функции

/(х 1, х 2, хз, X4)|i = v(0, 1, 2, 9, 15).

5.25. Вычислить трассы булевой функции

/(х 1, Х2, Хз, x 4)|i = V(0, 1, 2, 4, 7, 8, 11).

§ 5.15. Еомментарии

Борьба с перебором вариантов при решении задач дискретной математи

ки — одна из актуальнейших проблем современного математического обеспе

чения систем переработки информации. Успеха можио достичь, только решая

проблему характеризации реализуемых модельных преобразований. Если же

характеризациониая проблема не решена, то используют эвристический подход

к оптимизации комбинаторных алгоритмов.

Характеризационный анализ является метатеорией, конструктивно связы

вающей различные формальные системы иа семантическом уровне знаний, что

позволяет разрабатывать принципиально новые информационные технологии ре

шения проблемных задач большой размерности иа дискретных структурах.

В настоящее время интенсивно развивается перспективная иаука, позволяю

щая с единых методологических принципов исследовать и прогнозировать общие

законы развития микромира, мира, макромира. Эта наука названа ее основате

лем академиком И.И. Юзвишиным имформациологией.

СПИСОК ЛИТЕРАТУРЫ

1. Автоматизация проектирования сложных логических структур /Под

ред. В.А. Горбатова.—М.: Энергия, 1978.

2. Ахо А., Хопкрофт Дж., Ульман Дж. Построение и анализ вычи

слительных алгоритмов.—М.: Мир, 1979.

3. Гильберт Д., Бернайс П. Основания математики. Логические исчи

сления и формализация арифметики.—М.: Наука, 1979.

4. Горбатов В.А. Квазиполные графы и их некоторые свойст

ва Ц Доклады НТК МЭИ. Вычислительная техника. — М.: МЭИ,

1965. — С. 3-10.

5. Горбатов В.А. О минимальной раскраске графа Ц Доклады НТК.

МЭИ, 27 марта — 10 апреля 1964 г. Подсекция вычислительной

техники.—М.: МЭИ, 1964.—С. 17.

6. Горбатов В.А. Оценки при выборе направления вычислений в за

дачах синтеза конечных автоматов/ Изв. АН СССР. Техническая

кибернетика.—1970.—№ 4.—С. 91-101.

7. Горбатов В.А. Семантическая теория проектирования автоматов.—

М.: Энергия, 1979.

8. Горбатов В.А. Синтез логических схем в многозначных логи

ках, основанный на структурных соотношениях Ц Многозначные

элементы и структуры.—М.: Сов. радио, 1967.

9. Горбатов В.А. Синтез логических схем в произвольном бази

се/Теория дискретных автоматов.—Рига: Зинатне, 1967.

10. Горбатов В.А. Схемы управления ЦВМ и графы.—М.: Энергия,

1971.

11. Горбатов В.А. Теория частично упорядоченных систем.—М.: Сов.

радио, 1976.

12. Горбатов В.А., Кафаров В.В., Павлов П.Г. Логическое управление

технологическими процессами.—М.: Энергия, 1978.

13. Горбатов В.А., Останков Б.Л., Фролов С.А. Регулярные струк

туры автоматного управления / Под ред. В.А. Горбатова.—М.: Ма

шиностроение, 1980.

14. Горбатов В.А., Павлов П.Г., Четвериков В.Н. Логическое управ

ление информационными процессами.—М.: Энергоатомиздат, 1984.

15. Горбатов В.А., Смирнов М.И., Хлытчиев И.С. Логическое упра

вление распределенными системами.—М.: Энергоатомиздат, 1991.

534 Список литературы

16. Горбатова М.В. Теория трасс/Информационные коммуникации,

сети, системы и технологии.—М.: МАИ, 1993.

17. Гудман С., Хидетниеми С. Введение в разработку и анализ

алгоритмов.—М.: Мир, 1981.

18. Гэри М., Джонсом Д. Вычислительные машины и труднорешаемые

задачи.—М.: Мир, 1982.

19. Зыков А.А. О некоторых свойствах линейных комплексовЦМат.

сборник.—1949.—Т. 24, № 2.—С. 163-188.

20. Зыков А.А. Теория конечных графов.—Новосибирск: Наука, 1969.

21. Лазарев В.Г., Пийль Е.И. Синтез управляющих автоматов.—М.:

Энергия, 1978.

22. Майника Э. Алгоритмы оптимизации на сетях и графах.—М.: Мир,

1981.

23. Мальцев А.И. Алгебраические системы.—М.: Наука, 1970.

24. Новиков П.С. Конструктивная математическая логика с точки зре

ния классической.—М.: Наука, 1977.

25. Общая теория систем.—М.: Мир, 1966.

26. Оре О. Теория графов.—М.: Наука, 1980.

27. Поспелов Д-А. Логико-лингвистические модели в системах уп

равления.—М.: Энергия, 1981.

28. Рейнгольд Э., Нивергелът Ю., Део Н. Комбинаторные алгоритмы.

Теория и практика.—М.: Мир, 1980.

29. Свами М., Тхуласираман К. Графы, сети и алгоритмы.—М.: Мир,

1984.

30. Справочная книга по математической логике. Ч. I-IV / Под ред.

Дж. Барвайса.—М.: Наука, 1982, 1983.

31. Харари Ф. Теория графов.—М.: Мир, 1973.

32. Юзвишин И.И. Информациология.—М.: Радио и связь, 1996.

33. Appel К., Haken W. Every planar map is four colorableЦBull, of

Amer. Math. Soc.—1976.—V. 82, № 5.

34. Berge C.. Las Vergnas M. Sur un theoreme du type Konig pour hiper-

graphes/ Ann. V.Y. Acad. Sci.—1975. 36, № 1.

35. Birkhoff G., Lewis D. Chromatic polynomials/Trans. Amer. Math.

Soc.—1946.—№ 60.—P. 355-451.

36. Christofides N. Traph theory. An algorithmic approach.—New York—

London—San Francisco. Academic Press, 1975. [Рус. пер.: Kpu-

стофидес H. Теория графов. Алгоритмический подход.—М.: Мир,

1978.]

37. Descartes В. Solution to advanced problem № 4526 Ц Amer. Math.

Monthly.—1954—№ 61.—P. 352.

38. Dirac G.A. On the structure of /^-chromatic graphs /Proc. Cam

bridge Philos. Soc.—1967—№ 63.—P. 683-691.

Список литературы

535

39. Dirac G.A. The structure of /f-chromatic graphs/Fund. Math.—

1953—№ 40— P. 42-55.

40. Goldberg D.E. Genetic Algorithms.—Addison-Wesley, 1989.

41. Hardwiger H. Uber eine Klassifekation der Strecken Komp-

lexe Ц Vierteljschr. Naturforsch. Ges. Zurich.—1943.—№ 88.—P. 133—

142.

42. Kelly J.B., Kelly L.M. Path and circuits in critical graphs / Amer. J.

Math.—1954.—№ 76.—P. 786-792.

43. Michalewicz Z. Genetic Algorithms + Data Structures = Evolution

Programs.—Springer-Verlag, 1992.

44. Mycielski J. Sur le coloriage des graphs Ц Colloq. Math.—1955.—

№ 3.—P. 161-162.

45. Saatu T.L. Thirteen corolful variation on Gulhrie’s four-color conjec-

tire / Amer. Math. Monthlu.—1972.—№ 72.—P. 2-43.

46. Whitney H. Congruent praphs and the connectivity of graphs Ц Amer.

J. Math.—1932,—№ 54.—P. 150-168.

ПРЕДМЕТНЫЙ УКАЗАТЕЛЬ

Автомат асинхронный 266

— конечный 264

— магазинный 263

— Майхилла 262

— микропрограммный 282, 283

— операционный 267

— синхронный 266

— управляющий 267

Алгебра 18

— булева 33

— Вебба 132

— множеств (алгебра Кантора) 21

— отношений

— Поста 132

— реляционная 42

— Россера — Тьюкетта 132

— схемная 367

Алгоритм 55

Антисиндром 344

Базис булев 108

— дизъюнктивный 113

— конъюнктивный 113

— Вебба 113

— Жегалкина 113

— импликативный 113

— коимпликативный 113

— несвязный 347

— связный 347

— циклов 171

— Шеффера 113

Буква 216, 259

— крайняя второго рода 327

первого рода 327

— обобщенная второго рода 322

-------

первого рода 321

Булеан 15

Вершина граничная 379

Вершина покрывающая 331

— разделяющая 312

Вершины соцветные 208

Вес производной от булевой функ

ции 119

Вид 359

Высказывание 94

Гамак 312

Гиперграф 38

Гиперкуб (n-мерный куб) 50

Грамматика бесконтекстная 263

— контекстная 262

— контекстно свободная 263

связаная 262

— линейная 263

— металинейная 263

— односторонне линейная 263

— с конечным числом состояний

258

— языка 258

Грань нижняя 27

наибольшая 27

— верхняя 27

-------наименьшая 27

Граф взвешенный 158

— , вложимый в булево простран

ство 198

— гомеоморфный 194, 229

— двудольный 39

— затирания 291

— зацепления 287

— звездный 208

— изоморфный 160

— квазиполный 217

невключаемый 242

— кубируемый 198

— линейный 339

— незацепленный 286

Предметный указатель

537

Граф переходов 272

— планарный 194

— полный 37

— , приводимый к цунгу 283

— предквазиполный 440

— противоречивости столбце-

вой 456

-------

строчный 456

— п-раскрашиваемый 208

— п-связный 166

— п-хроматический 208

— связный 163

-------

сильно 168

-------

несильно 168

— типа к<г

— частичный 24

Группа 19

— подстановок (группа Галуа) 19

Группоид аддитивный 18

— ассоциативный 19

— идемпотентный 19

— коммутативный (абелев) 19

— мультипликативный 18

Декомпозиция автоматов абст

рактная 282

-------

параллельная 282

— структурная 342

— функции булевой 100

-------

fc-значной 467

Дерево 171

— достижимости 379

Диаграмма гомеоморфная 36

— Хассе 26

— Эйлера 15

Дифференцирование булевой фун

кции 117

— графа 176

Задача достижимости 379

Запуск переходов 374, 375

Изоморфизм алгебр 33

— упорядоченных множеств 27

Импликанта простая 52

многовыходная 419

Интервал булевой функции макси

мальный 103

-----------

многовыходной 419

---------------

максимальный 419

— множества 51

Исчисление высказываний 127

— предикатов 142

-------

расширенное 144

------- узкое 144

Канал информационный 267

— управляющий 267

Квазиплотность квазиполного гра

фа 217

— модели 217

-------

квазиполной 217

Квантор всеобщности 142

— существования 142

Класс булевых функций линейных

109

-----------монотонных 110

-----------самодвойственных 110

----------

, сохраняющих константу

0(1) 109

— хроматический 209

— эквивалентности

Коалгебра графов 343

Код дополнительный 64

— обратный 64

— прямой 61

Кодирование Айкена — Эмери 72

— “в остатках” 73

— внутренних состояний 292

соседнее 297

-------

частотно-матричное 293

— Штибитца 70

Кольцо 21

Комплект 373

— пустой 373

Кооперация 343

Конституента 47

Контур 168

Конфигурация комбинаторная 14

Мажоранта подмножества 26

538

Предметный указатель

Матрица базисная разрезов (коци-

кломатическая) 173

-----------

дипломатическая 170

— инциденций 158

-------

вторая 172

-------

первая 172

— fc-клеточная 165

— смежности 159

-------

модифицированная 190

-------

базисная 325

— частотная отношений 176

-------

п-мерная 180

Машина Тьюринга 260

Микролуч 283

Микрооперация 273

Микропрограмма 273

Миноранта подмножества 26

Мограф 58

Модель 39

— гомеоморфная 229

— изоморфная 229

— квазиполная 217

Окрестность единичного радиуса

элемента (сечение) 23

— вершины 184

Операция дизъюнкции 94

— дополнения 17

— инверсии 343

— конъюнкции 94

— обратная 343

— объединения 17, 40, 373

пересечения 17, 40

— произведения декартова расши

ренного 40

— разложения 343

— разности 17, 40

симметрической 46

— расщепления второго типа 332

первого типа 331

Остов 171

Отношение п-арное 36

-------

симметричное (5-отноше

ние) 37

Отношение бинарное 22

-------

упорядоченности 25

-----------строгой 25

— достижимости 375

непосредственной 375

— обратное 28

— предпорядка 25

— рефлексивное 23

— симметричное 24

— транзитивное 24

— эквивалентности 28

Паросочетание 184

— наибольшее 184

— совершенное 184

Перестановка 14

— модели 217

Подмножество 13

— нечеткое 75

— собственное 14

Подмодель 216

Подстановка 19

Покрытие 53

Поле 21

Полугруппа 19

Полусистема Туэ 258

Порядок модели 217

Посет 75

Предикат 142

Проблема алгоритмически нераз

решимая 262

— характеризационная 395

Проекция бинарного отношения

Произведение декартово 15

-------частичное 282

— подстановок 20

Производная временная 495

— графа 176

-------

первого порядка 117

— fc-го порядка 118, 178

смешанная 117, 178

— модели 333

Пространство булево 198

— метрическое 83

Предметный указатель

539

Путь простой 168

— сложный 168

— составной 168

Разбиение 29

Размещение 14

Разложение столбцевое 100

— строчное 100

— Шеннона 98

-------

в точке 00.. .0 124

-------

в заданной точке 127

-------

двойственное 99

-------предельное 98

Разрез 167

Раскраска вершин 208

— ребер 209

Расстояние Евклидова (квадрат

ное) 84

------- относительное 84

— Хемминга (линейное) 83, 84

------- относительное 84

Реберность 210

Решетка 29

— векторная 80

— дедекиндова (модулярная) 32

— дистрибутивная 32

— полная 32

— с дополнениями 33

Риск 496

Род графа 194

— поверхности 194

Связность реберная 166

Семантика дескриптивная 393

— проективная 393

— рефлексивная 393

Сеть Петри 374

-------

маркированная 374

-----------

безопасная 377

Сечение 328

Символ 258

— нетерминальный 260

— терминальный 260

Система алгебраическая 40

Система счисления 56

аддитивная 58

-------асимметрическая 58 ч

-------

весомозначная 58

-------естественная 58

-------мультипликативная 58

-------непозиционная 58

-------позиционная 58

-------с основанием S 58

-------симметрическая 58

Состояния незацепленные 284

— неустойчивые 297

— псевдоэквивалентные 289

— совместимые 283

— эквивалентные 279

Суперпозиция 108

Таблица истинности 95

— Квайна (импликантная) 53

Тело 21

Терм первичный 96

Тип 359

Трасса 146

Уровень типа А 331

-------В 331

-------С 332

-------D 334

Фактормножество 23

Фигура запрещенная 198

Форма Кантора 51

-------

нормальная (НФК) 51

-----------минимальная 52

-----------

совершенная 51

-----------сокращенная 52

-----------тупиковая 52

------- скобочная 54

Форма (булевой функции) нормаль

ная дизъюнктивная (ДНФ) 96

-----------совершенная 96

-----------сокращенная 103

-----------тупиковая 107

---------------минимальная 107

-------------------

решетчатая 317

Функция 16

540

Предметный указатель

Функция булева

-------

остаточная 100

-------

слабоопределенная 105

— fc-значной логики 132

— полностью определенная 16

— частично определенная (недо-

определенная) 16

Хорда 171

Цепь 26

— простая 163

-------

составная 163

-------

сложная 163

Цикл гамильтонов 163

— эйлеров 166

Цунг 283

Число графа внешней устойчи

вости 183

---------------

вершинное 183

-------------------

отрицательное 191

Число графа внешней устойчи

вости вершинное положитель

ное 191

--------------- реберное 183

— цикломатическое 171

мографа 325

Элемент дополнительный 31

— единичный 27

— максимальный 27

— минимальный 27

— наибольший 27

— наименьший 27

— нейтральный 19

-------двусторонний 19

-------левый 19

-------правый 19

— сравнимый 27

Язык конечноавтоматный 264

— с конечным числом состоя

ний 259

— эквивалентный 258

Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика

Подождите немного. Документ загружается.