Дискретная математика для инженера (6-е изд.)

Купить бумажную книгу и читать

Название: Дискретная математика для инженера (6-е изд.)

Автор: Кузнецов О.П.

Издательство: Лань

Год: 2009

Страниц: 396

ISBN: 978-5-8114-0570-1

Формат: PDF

Размер: 7.3 Мб

Язык: русский

В книге изложены основные понятия теории множеств, общей алгебры, логики, теории графов, теории алгоритмов и формальных систем, теории автоматов. По сравнению с изданием 1988 г. заново написаны разделы по теории графов и сложности вычислений.

Пособие предназначено инженерам, которые специализируются в области автоматизированного управления и проектирования, информационных технологий, вычислительной техники, передачи информации, а также для студентов и аспирантов соответствующих специальностей.

ОГЛАВЛЕНИЕ

Предисловие к третьему изданию....................... 3

Глава первая.

Множества, функции, отношения.................... 4

1.1. Множества и операции над ними................. 4

1.2. Соответствия и функции....................... 15

1.3. Отношения................................ 27

Глава вторая.

Элементы общей алгебры......................... 35

2.1. Операции на множествах и их свойства............ 35

2.2. Полугруппы, группы, решетки.................. 41

Глава третья.

Введение в логику.............................. 50

3.1. Логические функции (функции алгебры логики)...... 50

3.2. Булева алгебра ............................. 56

3.3. Полнота и замкнутость........................ 71

3.4. Язык логики предикатов ...................... 82

Глава четвертая.

Графы...................................... 91

4.1. Основные понятия........................... 91

4.2. Пути и связность в неориентированных графах....... 99

4.3. Пути и связность в ориентированных графах....... 107

4.4. Деревья................................. 114

4.5. Пространство циклов........................ 118

4.6. Двудольные и планарные графы................ 125

4.7. Раскраски, устойчивость, покрытия.............. 132

4.8. Оптимизационные задачи на графах............. 137

Глава пятая.

Теория алгоритмов ............................ 151

5.1. Предварительное обсуждение.................. 151

5.2. Машины Тьюринга......................... 163

5.3. Рекурсивные функции....................... 188

5.4. Вычислимость и разрешимость................. 211

5.5. Вычислительная сложность и NP-трудные задачи .... 227

Глава шестая.

Формальные системы........................... 240

6.1. Формальные теории (логические исчисления). Исчисление высказываний.................... 242

6.2. Исчисление предикатов

и теории первого порядка..................... 254

6.3. Метатеория логических исчислений.............. 265

6.4. Абстрактные формальные системы.............. 274

Глава седьмая.

Языки и грамматики........................... 291

7.1. Формальные грамматики и их свойства........... 293

7.2. Операции над языками....................... 315

7.3. О семантике формальных языков ............... 324

Глава восьмая.

Автоматы................................... 328

8.1. Основные понятия.......................... 328

8.2. Распознавание множеств автоматами............. 347

8.3. Сети из автоматов, их анализ и синтез............ 366

8.4. Программная реализация

логических функций и автоматов ............... 383

Рекомендуемая литература....................... 388

Основная литература........................ 388

Дополнительная литература................... 389

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