Изложены методы и средства дискретной математики как инструментария при обработке информации в компьютерах. Книга состоит из трех частей: математические основы, математические модели и приложения, в которых представлены наиболее часто употребляемые в теоретической и прикладной информатике математические конструкции. Освещаются основные математические свойства той или иной теории вместе с данными, необходимыми для решения упражнений. Материал пособия построен на использовании аксиоматического метода и может служить основой для таких курсов как базы данных и базы знаний, теории сетей Петри и транзиционных систем, методы оптимизации и обоснования алгоритмов и программ, системы искусственного интеллекта, компьютерная алгебра и геометрия.ПредисловиеЧАСТЬ I. МАТЕМАТИЧЕСКИЕ ОСНОВЫГлава 1. Множества, отношения, комбинаторикаГлава 2. Основные понятия общей алгебрыГлава 3. Элементы теории алгоритмов и математической логикиГлава 4. Элементы теории графовЧАСТЬ II. МАТЕМАТИЧЕСКИЕ МОДЕЛИГлава 5. Абстрактная теория автоматовГлава 6. Теория конечных автоматовГлава 7. Модели алгоритмов и программГлава 8. Формальные грамматики и формальные языкиЧАСТЬ III. ПРИЛОЖЕНИЯГлава 9. Алгебры в компьютерных информационных технологияхГлава 10. Теория автоматов и графов в компьютерных информационных технологияхГлава 11. Методы поиска доказательств теорем в логике предикатовГлава 12. Основные понятия теории программных инвариантовСписок литературы
Author(s): Капитонова Ю.В. и др.
Series: Учебное пособие
Publisher: BHV
Year: 2004
Language: Russian
Commentary: 1146134281-хор
Pages: 624
Tags: Математика;Дискретная математика;
Предисловие ......Page 12
ЧАСТЬ I. МАТЕМАТИЧЕСКИЕ ОСНОВЫ ......Page 16
1.1.1. Интуитивное понятие множества. Основные принципы ......Page 18
1.1.2. Операции над множествами. Законы для операций ......Page 22
1.1.3. Декартово произведение множеств. Отношения ......Page 28
1.1.4. Примеры отношений ......Page 30
1.1.5. Примеры отображений ......Page 43
1.1.7. Контрольные вопросы ......Page 50
1.1.8. Задачи и упражнения ......Page 51
1.2.1. Основное правило комбинаторики ......Page 57
1.2.2. Число различных k-элементных подмножеств n-элементного множества ......Page 58
1.2.3. Число подмножеств данного множества ......Page 61
1.2.4. Перестановки и размещения упорядоченных множеств ......Page 62
1.2.5. Перестановки с повторениями ......Page 63
1.2.6. Размещение элементов множества ......Page 64
1.2.7. Комбинации элементов с повторениями ......Page 66
1.2.8. Бином Ньютона ......Page 67
1.2.9. Свойства биномиальных коэффициентов ......Page 69
1.2.10. Метод рекуррентных соотношений ......Page 70
1.2.11. Метод включений и исключений ......Page 73
1.2.12. Метод производящих функций ......Page 76
1.2.14. Задачи и упражнения ......Page 80
2.1.1. Общие сведения ......Page 83
2.1.2. Отношение конгруэнтности ......Page 84
2.1.3. Гомоморфизмы универсальных алгебр ......Page 86
2.1.4. Язык (алгебра) термов ......Page 89
2.1.5. Производные операции и конечные алгебры ......Page 91
2.2.2. Свободный группоид ......Page 93
2.2.3. Свободная полугруппа ......Page 94
2.2.4. Свободная коммутативная полугруппа ......Page 95
2.2.5. Свободные группы ......Page 96
2.2.6. Свободные абелевы группы ......Page 100
2.2.7. Свободное кольцо ......Page 105
2.2.8. Векторные пространства ......Page 111
2.2.9. Булевы алгебры ......Page 113
2.2.10. Структуры ......Page 125
2.2.11. Многоосновные алгебры. Алгебра алгоритмов Глушкова ......Page 132
2.3.1. Полные структуры ......Page 136
2.3.2. Замкнутые полукольца ......Page 137
2.5. Задачи и упражнения ......Page 140
3.1.1. Интуитивное понятие алгоритма ......Page 144
3.1.2. Вычислимые и частично рекурсивные функции. Тезис Черча ......Page 145
3.1.3. Алгоритмические проблемы ......Page 151
3.1.4. Машины Поста и машины Тьюринга ......Page 153
3.1.5. Алгоритмическая система Маркова ......Page 158
3.1.6. Задачи и упражнения ......Page 173
3.2.1. Алфавит и формулы ......Page 176
3.2.2. Интерпретация формул логики и высказываний ......Page 178
3.2.3. Полные системы связок ......Page 179
3.2.4. Система аксиом для исчисления высказываний ......Page 181
3.2.5. Теорема дедукции ......Page 184
3.2.6. Непротиворечивость и полнота исчисления высказываний ......Page 188
3.2.7. Исчисление высказываний и булевы алгебры ......Page 191
3.3. Методы проверки тождественной истинности формул исчисления высказываний ......Page 192
3.3.2. Метод Куайна ......Page 193
3.3.3. Метод редукции ......Page 194
3.3.4. Метод Девиса-Патнема ......Page 195
3.3.5. Метод резолюций ......Page 197
3.3.6. Контрольные вопросы ......Page 199
3.3.7. Задачи и упражнения ......Page 200
3.4.1. Алфавит и формулы ......Page 202
3.4.2. Истинность интерпретации, модели ......Page 204
3.4.3. Аксиоматика и правила вывода ......Page 208
3.4.4. Основные свойства теории первого порядка ......Page 209
3.4.5. Нормальные формы формул логикипредикатов первого порядка ......Page 220
3.4.6. Скулемовские стандартные формы ......Page 223
3.4.7. Классификация логик ......Page 226
3.4.8. Понятие о неклассических логиках ......Page 228
3.4.9. Понятие алгебраической системы ......Page 245
3.4.11. Задачи и упражнения ......Page 249
4.1.1. Определение неориентированного графа ......Page 252
4.1.2. Разновидности графов ......Page 254
4.1.3. Изоморфизм графов. Подграфы ......Page 257
4.1.5. Задачи и упражнения ......Page 258
4.2.2. Операция удаления вершины ......Page 259
4.2.5. Операция объединения графов ......Page 260
4.2.7. Отождествление (слияние) вершин ......Page 261
4.2.9. Операция раздвоения (расщепления) вершины ......Page 262
4.2.11. Операция дополнения графа ......Page 263
4.3.1. Маршруты, циклы, связность ......Page 264
4.3.2. Свойства регулярных графов ......Page 265
4.3.3. Свойства двудольных графов ......Page 266
4.3.4. Свойства связных графов ......Page 268
4.3.5. Метрические характеристики связных графов ......Page 271
4.3.6. Свойства эйлеровых графов ......Page 272
4.3.7. Свойства гамильтоновых графов ......Page 275
4.4.1. Матрицы смежностей и достижимости ......Page 276
4.4.2. Матрица Кирхгофа ......Page 279
4.5.1. Плоские и планарные графы ......Page 280
4.5.2. Грани плоского графа. Формула Эйлера ......Page 287
4.6. Раскраска графов. Хроматическое число ......Page 288
4.6.1. Правильная раскраска ......Page 289
4.6.2. Практические задачи, сводящиеся к задаче раскраски ......Page 290
4.6.3. Хроматические числа некоторых графов ......Page 291
4.6.5. Гипотеза четырех красок для карт ......Page 294
4.7. Бесконечные фафы ......Page 295
4.7.1. Конфольные вопросы ......Page 298
4.7.2. Задачи и упражнения ......Page 299
4.8.1. Определение дерева. Свойства деревьев ......Page 300
4.8.2. Фундаментальная система циклов фафа ......Page 304
4.8.3. Остов наименьшего веса ......Page 306
4.9.1. Основные понятия ......Page 307
4.9.2. Бинарные отношения и орфафы ......Page 310
4.9.3. Размеченные фафы и представление термов ......Page 311
4.9.4. Конфольные вопросы ......Page 314
4.9.5. Задачи и упражнения ......Page 315
ЧАСТЬ II. МАТЕМАТИЧЕСКИЕ МОДЕЛИ ......Page 318
5.1.1. Определение автомата и его разновидности ......Page 320
5.1.2. Таблицы переходов и выходов ......Page 323
5.1.3. Граф переходов и выходов ......Page 324
5.1.4. Подавтоматы. Гомоморфизмы автоматов ......Page 326
5.1.5. Теорема о приведенном автомате ......Page 331
5.2.1. Автоматные отображения ......Page 334
5.2.2. Автоматные системы событий ......Page 338
5.2.3. Автоматы Мура ......Page 340
5.2.4. Недетерминированные автоматы ......Page 344
5.2.5. Задачи и упражнения ......Page 346
6.1.1. Регулярные события ......Page 348
6.1.2. Теорема анализа конечных автоматов ......Page 350
6.1.3. Теорема синтеза конечных автоматов ......Page 354
6.1.4. Задачи и упражнения ......Page 362
6.2.1. Уравнения в алгебре событий ......Page 364
6.2.2. Системы линейных уравнений ......Page 365
6.2.3. Применение уравнений в алгебре событий к задачам анализа и синтеза конечных автоматов ......Page 367
6.2.4. Основной алгоритм синтеза конечных автоматов ......Page 369
6.2.6. Задачи и упражнения ......Page 374
6.3. Минимизация конечных автоматов без выходов ......Page 375
6.3.1. Общий алгоритм минимизации ......Page 376
6.3.2. Алгоритм минимизации конечных автоматов без выходов ......Page 377
6.3.3. Алгоритм минимизации ациклических автоматов ......Page 379
6.4.1. Определение отношения конгруэнтного замыкания ......Page 385
6.4.2. Общий алгоритм вычисления конгруэнтного и симметричного конгруэнтного замыканий ......Page 387
6.4.3. Алгоритм вычисления конгруэнтных замыканий для ациклических автоматов ......Page 395
6.4.4. Контрольные вопросы ......Page 398
6.4.5. Задачи и упражнения ......Page 399
7.1.1. Определение и функционирование ......Page 400
7.1.3. Алгоритмически разрешимые и неразрешимые проблемы ......Page 404
7.2.1. Определение автомата с одной лентой ......Page 409
7.2.3. Проблема бесконечности ......Page 411
7.3.1. Определение магазинного автомата ......Page 412
7.3.2. Представление языков в магазинных автоматах ......Page 415
7.3.3. Анализ магазинных автоматов ......Page 416
7.3.4. Синтез магазинных автоматов ......Page 418
7.3.6. Задачи и упражнения ......Page 420
7.4. Дискретные динамические системы ......Page 421
7.4.2. Задачи и упражнения ......Page 424
7.5. U—Y-схемы программ над памятью ......Page 425
7.5.2. Задачи и упражнения ......Page 429
8.1.1. Определение формальной грамматики ......Page 430
8.1.2. Классификация грамматик ......Page 435
8.1.3. Правоволинейные и леволинейные грамматики (регулярные грамматики) и конечные автоматы ......Page 438
8.1.4. Задачи и упражнения ......Page 442
8.2.1. Контекстно-свободные грамматики и уравнения ......Page 444
8.2.2. Уравнения, КС-языки и магазинные автоматы ......Page 449
8.2.3. Задачи и упражнения ......Page 451
ЧАСТЬ III. ПРИЛОЖЕНИЯ ......Page 452
9.1.1. Перемещения плоскости ......Page 454
9.1.2. Группы преобразований плоскости ......Page 459
9.1.3. Перемещения пространства ......Page 461
9.1.4. Группы преобразований пространства ......Page 467
9.1.5. Масштаб ......Page 469
9.1.6. Проекции ......Page 470
9.2.1. Определение реляционной алгебры ......Page 473
9.2.2. Некоторые свойства операций реляционной алгебры ......Page 479
9.2.3. Контрольные вопросы ......Page 481
9.2.4. Задачи и упражнения ......Page 482
9.3.1. Списки. Операции над списками ......Page 483
9.3.2. Реализация списков в памяти ЭВМ ......Page 490
9.3.3. Сложность выполнения операций над списками ......Page 491
9.3.4. Разновидности списков ......Page 492
9.3.5. Задание графов с помощью списков ......Page 493
9.3.6. Задание множеств и термов с помощью списков ......Page 494
9.3.8. Задачи и упражнения ......Page 497
10.1. Универсальный программный автомат ......Page 498
10.2.1. Идентификация слов при построении текстовых редакторов ......Page 504
10.2.2. Понятие гипертекста ......Page 509
10.3.1. Задача упрощения алгебраических выражений ......Page 510
10.3.2. Важные упрощения ......Page 513
10.3.3. Полные системы редукций, критические пары, алгоритм пополнения ......Page 514
10.3.4. Алгоритм Кнута-Бендикса критической пары ......Page 517
10.3.5. Алгоритм пополнения Кнута-Бендикса ......Page 520
10.3.6. Проблема общих подвыражений и канонизации для свободных групп ......Page 522
10.3.7. Задачи и упражнения ......Page 537
10.4. Теорема Холла и ее применение ......Page 538
10.4.1. Трансверсали ......Page 540
10.4.2. Латинские квадраты ......Page 541
10.5. Теорема Менгера и потоки в сетях ......Page 542
10.5.1. Задачи и упражнения ......Page 550
Глава 11. Методы поиска доказательств теорем в логике предикатов ......Page 551
1.1.1. Основные определения ......Page 552
11.1.2. Семантические деревья ......Page 556
11.1.3. Теорема Эрбрана ......Page 558
11.2.1. Контрарные пары и подстановки ......Page 559
11.2.2. Алгоритм унификации ......Page 561
11.2.3. Метод резолюций для логики предикатов первого порядка ......Page 566
11.2.4. Примеры применения метода резолюций ......Page 571
11.2.5. Правило поглощения ......Page 573
11.4. Задачи и упражнения ......Page 578
12.1.1. Определение программного инварианта ......Page 581
12.1.2. Методы поиска программных инвариантов ......Page 584
12.2.1. Основные задачи теории программных инвариантов ......Page 586
12.2.2. Алгоритмы поиска программных инвариантов ......Page 588
12.3. Поиск инвариантов в программах над свободными алгебрами данных ......Page 597
12.4.1. Решение основных задач ......Page 607
12.4.2. Свободные абелевы группы и коммутативные полугруппы ......Page 612
12.4.3. Примеры ......Page 613
12.5. Задачи и упражнения ......Page 620
Список литературы ......Page 622
