89 Дискретная математика для инженера. — 2-е изд., перераб. и доп. — М.; Энергоатомиздат, 1988.— 480 с.: ил.
ISBN 5-283-01563-7
Изложены основные понятия теории множеств, общей алгебры, логики, теории графов, теории алгоритмов и формальных систем. По сравнению с изданием 1980 г. существенно переработана и расширена глава по сложности вычислений, добавлен раздел о раскраске графов, включены новые главы по теории формальных языков и линейному программированию.
Для инженеров, специализирующихся в области автоматизированного управления и проектирования, вычислительной техники, системного программирования, передачи информации, а также студентов и аспирантов соответствующих специальностей.
ПРЕДИСЛОВИЕ КО ВТОРОМУ ИЗДАНИЮ
Второе издание книги существенно дополнено. В гл. 4 добавлен раздел, посвященный знаменитой задаче о четырех красках и ее решению, полученному недавно с помощью ЭВМ. Написаны две новые главы: гл. 7 «Языки и грамматики» (О. П. Кузнецов) и гл. 10 «Линейное программирование» (Г. М. Адельсон-Вельский).
В гл. 8 («Автоматы») добавлен раздел о связи между грамматиками и автоматами.
Существенно изменена и расширена глава о сложности вычислений (гл. 9 во втором издании). В ней дано изложение и сопоставление двух независимо сложившихся подходов к классификации комбинаторных задач по сложности: хорошо известного в американской литературе NP-подхода, использующего недетерминированные машины Тьюринга и понятие WP-полноты, и подхода, сложившегося в советских работах и основанного на понятии задачи со степенной проверкой. Обсуждению этих подходов предшествует сравнение сложности вычислений одной и той же задачи на абстрактных машинах разных типов. Определения и доказательства в этой главе довольно сложны и громоздки, поскольку они по существу связаны с программированием на абстрактных машинах. Эта глава более трудна для чтения, чем другие.
Подробнее, чем в первом издании, описаны некоторые «хорошие» комбинаторные задачи. В конце гл. 10 приведено полученное недавно доказательство полиномиально-сти задачи линейного программирования.
Обновлен и дополнен список литературы. Как и в первом издании, этот список не имеет цели отразить историю предмета, приоритеты или дать его полное библиографическое описание. Его задача —указать работы, в которых вопросы, кратко упомянутые в книге, изложены более подробно.
Авторы 1*
ОГЛАВЛЕНИЕ
Предисловие ко второму изданию .....••• 3
Предисловие к первому изданию ......... *
Глава первая. Множества, функции, отношения ... 9
1.1. Множества и операции под ними ...... 9
1.2. Соответствия и функции ......... 19
1.3. Отношения ............. 29
Глава вторая. Элементы общей алгебры ..... 3?
2.1. Операции на множествах и их свойства . . . , 37
2.2, Полугруппы, группы, решетки ....... 43
Глава третья. Введение в логику ....... 50
3.1. Логические функции (функции алгебры логики) . . ^
3.2. Булева алгебра.........• • °6
3.3. Полнота и замкнутость . ,....... JO
3.4. Язык логики предикатов ......... 80
Глава четвертая. Графы ........< 88
4.1. Основные понятия я операции ....... 88
4.2. Маршруты, цепи и циклы ........ 99
4.3. Некоторые классы графов и их частей ..... 109
4.4. Ориентированные графы......... 124
4.5. Графы с помеченными вершинами и ребрами ... 131
Глава пятая. Теория алгоритмов ....... 144
5.1. Предварительное обсуждение ....... 144
5.2. Машины Тьюринга .......... 155
5.3. Рекурсивные функции ......... 178
5.4. Вычислимость и разрешимость ....... 201
Глава шестая. Формальные системы ...... 216
6.1. Формальные теории (логические исчисления). Исчисление высказываний........... 217
6.2. Исчисление предикатов и теории первого порядка , . 228
6.3. Метатеория логических исчислений ...... 238
6.4. Абстрактные формальные системы ...... 246
Глава седьмая. Языки и грамматики ...... 261
7.1. Формальные грамматики и их свойства ..... 263
7.2. Операции над языками ......... ?°J
7.3. О семантике формальных языков ...... *&*
Глава восьмая. Автоматы ......... 295
8.1. Основные понятия .......... 295
8.2. Распознавание множеств автоматами , . . . . 313
8.3. Сети из автоматов, их анализ и синтез . . . , . 331
8.4. Программная реализация логических функций и автоматов.............. 347
Глава девятая. Комбинаторные задачи и трудоемкость вычислений.............. 351
9.1. Трудоемкость относительно разных машин . . . 351
9Л. Классы трудоемкости комбинаторных задач , . , 371
9,3. Метод ветвей и границ ......... 399
Глава десятая. Линейное программирование.....411
10.1. Некоторые сведения из линейной алгебры и многомерной геометрии ..... ...... 411
10.2. Задачи линейного программирования. Области допустимости.............. 421
10.3. Двойственные задачи линейного программирования .
10.4. Симплекс-метод для решения задач линейного программирования............. 44"6
10.5. О полиномиальной трудоемкости задач линейного программирования ........... 454
Список литературы............ 473
Предметный указатель..........,476
Цена: 150руб.
