Горбатов В. А. Фундаментальные основы дискретной математики. Информационная математика. — М., 2000.— 544с.
В учебнике излагаются основы многосортных множеств, математической логики, теории графов и мографов, теории формальных грамматик и автоматов, прикладной теории алгоритмов и характеризационного анализа, которые в совокупности образуют основы дискретной математики, представляющие собой методически взаимосвязанный курс "Компьютерно-информационная математика". Для студентов технических университетов, академий и институтов, обучающихся по специальности "Информатика и вычислительная техника", а также научных работников и инженеров, работающих в области информатики и вычислительной техники.
ОГЛАВЛЕНИЕ
К читателю..................................................................5
Предисловие ................................................................7
Введение ....................................................................10
Глава 1. Основы многосортных множеств........................13
§1.1. Множество, функция, операция. Способы задания . ... 13
§1.2. Понятие алгебры. Фундаментальные алгебры............18
§1.3. Бинарные отношения, способы их задания и свойства . 22
§1.4. Решетка..........................................................29
§1.5. Модель. Алгебра отношений..................................36
§1.6. Аксиоматика теории множеств, минимизация представления множеств ................................................44
§1.7. Алгоритм — двусортное множество. Системы счисления 55
§1.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
§2.12. Комментарии....................................................156
Глава 3. Теория графов и мографов ................................157
§3.1. Взвешенный граф и его матричное Задание..............157
§ 3.2. Связность и сильная связность графа......................163
§3.3. Цикломатика и коцикломатика..............................170
§3.4. Дифференцирование графов и мографов ..................174
§3.5. Устойчивость, покрытия, паросочетания ..................183
§3.6. Вложение графов................................................194
§3.7. Раскраска вершин и ребер графа. Характеризация реберности...............................208
§ 3.8. Квазиполные модели, их структура и свойства............216
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. Семантическое ослабление функциональной связности
памяти автомата................................................ООО
§5.7. Решение проблемы повторной функциональной декомпозиции в булевой логике......................................454,
§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
Часть 1
Часть 2
