Горбатов В.А. Фундаментальные Основы Дискретной Математики. Информационная Математика
Подождите немного. Документ загружается.
В.А. ГОРБАТОВ
Ф у н д ам ен тальн ы е
основы
ДИСКРЕТНОЙ
МАТЕМАТИКИ
ИНФОРМАЦИОННАЯ МАТЕМАТИКА
Рекомендовано Министерством общего и профессионального
образования Российской Федерации в качестве учебника
для студентов высших технических учебных заведений
Ш
МОСКВА
НАУКА • ФИЗМАТЛИТ
2000
УДК 519.45
Г 62
ББК 22.145 (075.8)
Издание осуществлено при содействии
ООО tФирма Издательство АСТ»
Горбатов В. А. Фундаментальные основы дискретной математики.
Информационная математика. — М.: Наука. Физматлит, 2000.—544 с.—
ISBN 5-02-015238-2.
В учебнике излагаются основы многосортных множеств, математической ло
гики, теории графов и мографов, теории формальных грамматик и автоматов,
прикладной теории алгоритмов и характеризационного анализа, которые в сово
купности образуют основы дискретной математики, представляющие собой ме
тодически взаимосвязный курс “Компьютерно-информационная математика”.
Для студентов технических университетов, академий и институтов, обучаю
щихся по специальности “Информатика и вычислительная техника”, а также
научных работников и инженеров, работающих в области информатики и вычи
слительной техники.
Табл. 163. Ил. 313. Библиогр. 46 назв.
Рецензенты :
кафедра “Информационные технологии”
Московского государственного института электроники и математики;
доктор фиаико-математических наук, профессор В. Н. Решетников
ТП-99-И
ISBN 5-02-015238-2
© В. А.Горбатов, 1999
© Наука. Физматлит, оформление, 1999
ОГЛАВЛЕНИЕ
К читателю......................................................................................... 5
Предисловие ...................................................................................... 7
Введение ........................................................................................... 10
Глава 1. Основы многосортных множеств............................... 13
S 1.1. Множество, функция, операция. Способы задания . . . . 13
j 1.2. Понятие алгебры. Фундаментальные алгебры
..............
18
11.3. Бинарные отношения, способы их задания и свойства . 22
* 1.4. Решетка
............................................................................. 29
§1.5. Модель. Алгебра отношений............................................ 36
§1.6. Аксиоматика теории множеств, минимизация представ
ления множеств ................................................................ 44
§ 1.7. Алгоритм — двусортное множество. Системы счисления 55
11.8. Компьютерные арифметики 61
§ 1.9. Нечеткие подмножества 75
§ 1.10. Метрические пространства............................................... 83
§ 1.11. Задачи и упражнения....................................................... 86
§ 1.12. Комментарии..................................................................... 93
Глава 2. Математическая логика ............................................... 94
§2.1. Логика высказываний....................................................... 94
§ 2.2. Разложение Шеннона. Декомпозиция булевых функций 98
§2.3. Минимизация булевых функций в классе Д Н Ф
...........
102
§ 2.4. Полнота. Построение суперпозиций булевых функций . 108
§2.5. Дифференцирование булевых функций
.........................
116
§2.6. Разложение булевой функции в заданной точке прост
ранства ................................................................................ 123
§2.7. Исчисление высказываний
............................................... 127
§2.8. Коиечнозначные логики..................................................... 132
§ 2.9. Исчисление предикатов 142
§ 2.10. Теория трасс 145
я 2.11. Задачи и упражнения....................................................... 150
S 2.12. Комментарии 156
Глава
3. Теория графов и мографов .......................................... 157
§3.1. Взвешенный граф и его матричное задание................. 157
§ 3.2. Связность и сильная связность графа 163
S 3.3. Цикломатика и коцикломатика....................................... 170
§3.4. Дифференцирование графов и мографов
......................
174
13.5. Устойчивость, покрытия, паросочетания 183
§3.6. Вложение графов 194
§3.7. Раскраска вершин и ребер графа. Характеризация ре-
берности
............................................................................. 208
§ 3.8. Квазиполные модели, их структура и свойства
..............
216
4
Оглавление
S 3.9. Характеризация частичного упорядочения мографа . . .
...
227
§ 3.10. Логарифмические оценки хроматического числа. Реше
ние проблемы четырех красок
.........................................
...
239
§3.11. Задачи и упражнения
.......................................................
...
255
§ 3.12. Комментарии.....................................................................
...
257
Глава 4. Теория формальных грамматик и автоматов
...........
...
258
§4.1. Формальные грамматики..................................................
...
258
§ 4.2. Основные этапы проектирования автоматов
................
...
265
§4.3. Алгоритмический этап проектирования
.........................
...
271
§ 4.4. Абстрактное проектирование автоматов
.........................
...
279
§ 4.5. Кодирование внутренних состояний
..............................
...
292
§ 4.6. Построение выходных функций и функций возбуждения
памяти автомата
...............................................................
...
305
§4.7. Синтез логических структур в топологических базисах 310
§ 4.8. Синтез логических структур в несвязных базисах . . . 342
§4.9. Синтез логических структур в связных базисах
...........
...
361
14.10. Синтез нейронных структур 370
§4.11. Моделирование автоматных систем сетями Петри .... 373
§4.12. Задачи и упражнения
.......................................................
...
385
§4.13. Комментарии.....................................................................
...
387
Глава 5. Прикладная теория алгоритмов
.................................
...
388
§5.1. Принципы характеризационного анализа. Построение
комбинаторных алгоритмов
............................................
...
388
§5.2. Характеризация и методы оптимального размещения
данных в памяти ЭВМ ............................
..
.....................
...
404
§ 5.3. Характеризация выходной связности логических струк
тур 414
§5.4. Теоретико-структурная минимизация булевых функций
...
423
§ 5.5. Характеризация разложения графа переходов в частич
ное декартово произведение
................................................
429
§5.6. Семантическое ослабление функциональной связности
памяти автомата
...............................................................
....
000
§ 5.7. Решение проблемы повторной функциональной деком
позиции в булевой логике 454t
§5.8. Синтез функциональной декомпозиции в к-значной ло
гике 467
§ 5.9. Синтез функциональной декомпозиции заданной размер
ности 473
§ 5.10. Семантическое проектирование нейронных сетей .... 478
§ 5.11. Оценка динамики логических структур 494
§5.12. Семантическое проектирование скоростной транспорт
ной сети большого города 518
§ 5.13. Техническая диагностика сильносвязных объектов . . . 526
§ 5.14. Задачи и упражнения 530
§ 5.15. Комментарии 532
Список литературы .............................................................
.............
....
533
Предметный указатель.....................................................................
....
536
К ЧИТАТЕЛЮ
Горбатов Вячеслав Афанасьевич, академик многих академий,
в том числе Международной академии информатизации (МАИ),
РАЕН, Российской академии медико-технических наук, профес
сор, доктор физико-математических наук, доктор технических
наук, родился 19 апреля 1939 года в Москве. С отличием закончил
Московский энергетический институт, в тридцать три года защи
тил докторскую диссертацию, женат, имеет дочь и сына. Много
лет возглавляет кафедру’’Вычислительные машины” Московского
государственного горного университета.
В,А. Горбатов является автором научного открытия — теории
характеризационного анализа. Это открытие, сделанное в сере
дине 60-х годов, явилось основой научной школы В.А. Горбатова
по информационной математике, идеи которой получили разви
тие как у нас в стране, так и за рубежом. В рамках этого науч
6
К читателю
ного направления В.А. Горбатовым разработана теория частично
упорядоченных систем, получившая большое практическое значе
ние в информатике; при этом решена проблема проектирования
больших и сложных систем при различных предметных интер
претациях (информационной, компьютерной, транспортной, диа
гностической, атомной, экономической, медицинской и других).
Им создана семантическая теория проектирования автоматов, в
которой предложен принципиально новый путь эффективного ре
шения фундаментальных общетеоретических проблем синтеза ав
томатов на основе интерпретации выражений входного языка в
категориях выходного без фактического построения соответствую
щих конструкций на выходном языке, что позволило эффективно
проектировать оптимальные системы логического управления на
современных интегральных структурах, в том числе с использо
ванием нейронной технологии.
На основе характеризационного анализа В.А. Горбатовым пред
ложена новая интеллектуальная информационная технология ре
шения проблемных задач большой размерности на дискретных
структурах. Используя эту технологию, он и его ученики разрабо
тали и успешно внедрили в различные области народного хозяй
ства системы автоматизированного проектирования, системные и
семантические прикладные программные пакеты, инструменталь
ные компьютерные средства.
Научные достижения В.А. Горбатова отмечены рядом междуна
родных и российских премий и медалей, в том числе Международ
ной премией фон Неймана, медалью Лауреата Нобелевской премии
П.Л. Капицы за научное открытие, медалью Петра I “За заслуги в
деле возрождения науки и экономики России”, Георгиевским Кре
стом I степени “За заслуги в деле развития науки и экономики
России”, именной медалью ООН, Международной премией и Зо
лотой медалью ООН за большой вклад в области информатизации
мирового сообщества, медалью “Лауреат премии имени Алексан
дра Чижевского”.
В.А. Горбатов уделяет большое внимание научным кадрам: им
подготовлено свыше ста кандидатов и докторов наук в области ин
форматики, вычислительной техники и экономики.
Основные научные результаты профессора В.А. Горбатова опу
бликованы более чем в 400 научных трудах. В.А. Горбатов —
автор 35 книг, в том числе 18 монографий по дискретной мате
матике, информатике и вычислительной технике, ряд которых
переведен на английский, испанский, немецкий, китайский, бол
гарский, польский языки.
Академик МАИ, РАЕН, профессор МГУ,
доктор физико-математических наук
С.Я. Герценштейн
ПРЕДИСЛОВИЕ
Общество XXI века — общество информационное (постинду
стриальное), в котором одной из главных проблем является про
блема гармонии Человека и Природы. Составляющей этой гармо
нии является мощная информационная инфраструктура общества.
Вопрос об исключительности Человека в связи с наличием у него
разума после Коперника и Дарвина был поставлен в конце 50-х
годов нашего столетия, когда началось исследование “искусствен
ного интеллекта”, когда центр тяжести решения задач переме
стился от задач конечномерной (вычислительной) математики к
Задачам на дискретных структурах. Если задачи конечномерной
математики были связаны с проблемой создания ракетно-ядерного
щита, то задачи дискретной математики — с проблемами управле
ния и организации в сложных системах. Заметим, что эти задачи
волновали Человека и в древние времена.
...Весна. Север. Вождь одного из племен задумчиво смотрит на
собранный хворост. Сегодня ему предстоит большое испытание:
управление построением ритуальных костров.
Его предки установили весенний ритуальный праздник по
строения костров. На этом празднике племя радуется приходу
солнечных теплых дней, тому, что благодаря удачной охоте племя
пережило суровую зиму. На празднике строятся ритуальные ко
стры в виде цепочек. Каждая цепочка посвящена одной из охот ми
нувшей холодной зимы. Между кострами стоят воины, отличив
шиеся на охоте силой удара или быстротой бега, или смелостью,
находчивостью, позволившими заманить зверя в гибельную для
него яму, или меткостью, или проявлением другого охотничьего
качества. На празднике молодежь посвящается в воины, она в
плясках проходит по. цепочке, и тепло ритуальных костров “пере
дает” молодежи отвагу, силу удара и другие навыки воинов-со-
племенников. В следующую зиму молодежь, посвященная в во
ины, будет достойной взрослых охотников при добыче пищи.
Всем построением ритуальных костров управляет вождь пле
мени: он определяет место каждого отличившегося воина в цепочке
так, чтобы каждая цепочка была посвящена одной и только одной
охоте. Для него этот день — день испытания его мудрости. Если
он не сможет построить ритуальных костров, то будет считаться,
что духи отвернулись от него, что он потерял мудрость и должен
лишиться шкуры вождя.
Вождь плотнее натягивает свою шкуру, хотя снежинки, сбро
сив свои белые шубки и образовав веселые потоки прозрачной
воды, уже возвестили о приходе тепла. Он начинает готовиться
8
Предисловие
к построению костров: в прошедшую зиму было пять охот (охоты
будем идентифицировать числами), в которых отличились девять
воинов (воинов идентифицируем буквами). В первой охоте отли
чились воины а, к, р; во второй — воины с, /, к, р; в третьей —
воины а, d, /, р; в четвертой — воины b, е, д, р\ в пятой — воины
а, с, €, р.
Вождь чертит на земле расположение воинов в цепочках. Один
вариант взаимного расположения воинов сменяет другой — ко
стры не строятся. Неужели он лишился мудрости? Воин р ему не
мешает — через него должны пройти все пять цепочек. Воинов Ъ
и д следует поставить рядом, ибо они отличились только в одной
охоте — четвертой. Воины о и Ь, с и d, ей /,дик соответственно
не должны находиться в одной и цепочке, так как ни одна из этих
пар, например а и d, не отличалась в одной и той же охоте. Все
эти рассуждения не дают вождю ключа к построению костров. Он
снова начинает перебирать варианты взаимного расположения во
инов в цепочках.
Перебирать ему придется долго — число таких вариантов со
ставляет около двух миллионов: П 5»' = 3! х 4! х 4! х 4! х 4! =
»
= 1 990 656, где s,- — число охотников, отличившихся в i-й охоте.
Костры не строились. Вождь вошел в пещеру и в изнеможе
нии опустился на шкуру. Шкура... а что, если тем воинам, из-за
которых не строились цепочки, выдать по шкуре за то, чтобы они
“забыли” о своих геройствах в некоторых охотах. Такая “забывчи
вость” воинов упростит процесс построения ритуальных костров.
Выход найден. Он останется вождем!..
Читатель, чтобы легче следить за дальнейшими рассуждения
ми вождя, давайте построим матрицу Q = [gtJ], каждой строке
которой взаимно однозначно соответствует охота, столбцу — воин,
и если j-й воин отличился в г-й охоте, то = 1 , в противном
1 0
0
0 0
0
0 1 1
0 0 1
0
0 1 0
1
1
1 0
0
1 0 1 0
0
1
0
1
0 0
1
0
1
0
1
1
0 1 0
1
0
0 0
1
Хотя глава племени и сохранил за собой шкуру вождя, перед
ним снова встала проблема: каким образом построить ритуальные
костры, истратив при этом минимальное число шкур? Что должен
сделать вождь?
Существовал такой обычай или нет — автору неизвестно. Но
пример построения ритуальных костров является хорошей иллю
страцией тех трудностей, которые появляются при решении про
блем организации некоторой системы, удовлетворяющей задан
ным свойствам.
Предисловие
9
Характерной чертой этих задач является проблема “проклятия
размерности”, или “информационного взрыва в ЭВМ”. Решение
их полным перебором вариантов невыполнимо даже при исполь
зовании самых мощных ЭВМ при реальной размерности задачи.
Решению задач реальной размерности с учетом ограниченно
сти временных и емкостных ресурсов ЭВМ и посвящен настоя
щий учебник. Учебник имеет двойное название. С точки зре
ния математика (внутренней) это — “Фундаментальные основы
дискретной математики” , с точки зрения пользователя (внешней)
это — “Информационная математика”. Книга написана на базе
учебника “Основы дискретной математики” (М.: Высшая школа,
1986, 312с).
Книга представляет собой единый методически взаимосвязан
ный курс, формирующий культуру абстрактного мышления при
подготовке бакалавров, инженеров и магистров наук по направле
нию “Информатика и вычислительная техника”. Она включает
основные разделы современной дискретной математики: основы
многосортных множеств, математическую логику, теорию графов
и мографов (гиперграфов), теорию формальных грамматик и ав
томатов, прикладную теорию алгоритмов и характеризационный
анализ.
Последняя глава посвящена центральному разделу компью
терно-информационной математики — характеризационному ана
лизу, позволившему впервые укрупнить варианты и осуществлять
их сравнение не на уровне фактически полученных решений, а
на уровне заданной информации. При этом каждый сравнивае
мый вариант соответствует целому классу в некотором смысле
изоморфных решений. Такое укрупнение перебора конструктивно
осуществляется интерпретацией исходной информации в терми
нах решения. Эта интерпретация, являющаяся связующим зве
ном между исходной информацией и решением, позволяет опреде
лять свойства решения без его фактического построения, что дает
возможность находить минимальное решение без перебора всех
эквивалентных решений.
Автор выражает искреннюю благодарность за критические за
мечания академику РАН А.А. Самарскому, академикам МАИ,
РАЕН Д.А. Поспелову, С.А. Редкозубову, В.Н. Решетникову, акаде
микам МАИ, член-корреспондентам РАЕН О.С. Бартеневу и
И.Г. Шрамкову.
Учебник создан в соавторстве с доцентом М.В. Горбатовой (ею
написаны § 1.9, 1.10, 2.10, 5.11) и академиком МАИ, член-коррес-
пондентом РАЕН А.В. Горбатовым (им написаны §2.2,4.10,5.7-
5.10).
Автор
Sapienter Cogitare Honeste Operare
Loqui Argute.
А. Комениус
ВВЕДЕНИЕ
Вы, читатель, являетесь уже студентом высшей школы (уни
верситета, академии или института), и пора вам узнать, что поня
тие ШКОЛА (SCHOLA) есть аббревиатура, составленная из шести
слов, приведенных в эпиграфе и принадлежащих перу известного
чешского гуманиста, просветителя Амоса Камениуса (1592-1671).
Переводятся первые два слова как “мудро мыслить”, следующие
два слова — “благородно действовать” , последние два слова —
“лаконично говорить”. По окончании высшей школы ты должен
обладать этими тремя свойствами. Первое свойство — мудро мы
слить — основывается на фундаментальных естественных зна
ниях, одной из основ которых является абстрактное мышление,
формированию которого и способствует дискретная математика;
ее ты будешь успешно использовать при решении проблем инфор
матизации в XXI веке.
Эффективность используемых информационных технологий во
многом определяется оптимальностью разработанного алгоритма,
которая оценивается временной и емкостной сложностью. Под вре
менной сложностью понимается время работы алгоритма, под
емкостной сложностью — объем памяти, необходимый для ре
шения задачи. Временная и емкостная сложности являются функ
циями от размерности задачи. В настоящее время в связи с широ
ким использованием вычислительной техники в различных сфе
рах человеческой деятельности все большее значение приобретают
вычисления на дискретных структурах — комбинаторные вычи
сления. Исследованию алгоритмов на дискретных структурах по
священы многочисленные публикации [2, 9, 11, 17, 18, 22, 25, 28,
29, 40, 43].
Анализ трудностей, имевших место при поиске эффективных
алгоритмов решения задач дискретной математики, привел к фор
мулировке центральной теоретико-методологической проблемы
дискретной математики — решению вопроса о возможности ис
ключения перебора вариантов при решении задач на дискретных
структурах. Была выдвинута гипотеза, что для широкого класса
задач дискретной математики, имеющих практический интерес,
не существует эффективного алгоритма их решения, трудоемкость
которого была бы полиномиальной функцией от размерности за
дачи. Эти задачи образуют класс N P -полных задач, трудоем
кость решения которых оценивается экспоненциальной функцией.
Согласно этой гипотезе задачи реальной размерности (равной не
скольким сотням) не могут быть эффективно решены даже на ЭВМ
будущих поколений. Действительно, если представить себе ЭВМ, в