Кузнецов О П., Адельсон-Вельский Г. М. Дискретная математика дли инженера

Кузнецов О П., Адельсон-Вельский Г. М. Дискретная математика дли инженера. - Изд.2, перераб. и доп— М.: 1988. — 408 с, ил.
Изложены основные понятия теории множеств, общей алгебры, логики, теории графов, теории алгоритмов и формальных систем. По сравнению с изданием 1980 г. существенно переработана и расширена глава по сложности вычислений, добавлен раздел о раскраске графов, включены новые главы по теории формальных языков и линейному программированию. Излагаются основы теории автоматов. Рассматриваются дискретные экстремальные задачи и методы их решения.Книга предназначена для инженеров, специализирующихся в области автоматического управления, вычислительной техники, систем передачи информации, а также студентов и аспирантов соответствующих специальностей.
ОГЛАВЛЕНИЕ
Предисловие ко второму изданию 3
Предисловие к первому изданию ........4
Глава первая. Множества, функции, отношения ....... 9
1.1. Множества и операции под ними ...........9
1.2. Соответствия и функции...... 19
1.3. Отношения....................29
Глава вторая. Элементы общей алгебры..........37
2.1. Операции на множествах к их свойства .... 37
2.2. Полугруппы, группы, решетки........43
Глава третья. Введение в логику.......50
3.1. Логические функции (функции алгебры логики) . . 50
3.2. Булева алгебра . ..........56
3.3. Полнота и замкнутость.........70
3.4. Язык логики предикатов ..........80
Глава четвертая. Графы.........88
4.1. Основные понятия и операции........88
4.2. Маршруты, цепи и циклы ........99
4.3. Некоторые классы графов и их частей ..........109
4.4. Ориентированные графы..........124
4.5. Графы с помеченными вершинами и ребрами ..............131
Глава пятая. Теория алгоритмов ....... 144
5.1. Предварительное обсуждение ....... 144
6.2. Машины Тьюринга .......... 155
5.3. Рекурсивные функции.............178
5.4. Вычислимость и разрешимость ....... 201
Глава шестая. Формальные системы ...... 215
6.1. Формальные теории (логические исчисления). Исчисление высказываний............217
6.2. Исчисление предикатов и теории первого порядка .......228
6.3. Метатеория логических исчислений ...... 238
6.4. Абстрактные формальные системы ...... 246
Глава седьмая. Языки и грамматики ......261
7.1. Формальные грамматики и их свойства ..... 263
7.2. Операции над языками.............283
7.3. О семантике формальных языков ...... 292
Глава восьмая. Автоматы ........295
8.1. Основные понятия.............295
8.2. Распознавание множеств автоматами ............303
8.3. Сети из автоматов, их анализ и синтез ............331
8.4. Программная реализация логических функций и автоматов ...............347
Глава девятая. Комбинаторные задачи и трудоемкость вычислений ............351
9.1. Трудоемкость относительно разных машин .............351
9.2. Классы трудоемкости комбинаторных задач ........371
9.3. Метод ветвей и границ ..........399
Глава десятая. Линейное программирование ......................411
10.1. Некоторые сведения из линейной алгебры и многомерной геометрии ...............411
10.2. Задачи линейного программирования. Области допустимости..................421
10.3. Двойственные задачи линейного программирования
10.4. Симплекс-метод для решения задач линейного программирования ..... ........ 446
10.5. О полиномиальной трудоемкости задач линейного программирования ...........454
Список литературы ............ 473
Предметный указатель .......... 476

Created using FlowPaper Flipbook Maker ↗