Съдържание
Въведение IХ
1 Основни понятия 1
1.1 Множества 1
1.2 Релации 9
1.3 Функции 14
1.4 Множества с операции 20
1.4.1 Полугрупи, групи и полета 22
1.4.2 Решетки. Булеви алгебри 27
1.4.3 Алгебри на Клини 31
1.4.4 Множества с външни операции 32
Упражнения 35
2 Комбинаторика 41
2.1 Принципи на изброителната комбинаторика 42
2.2 Основни комбинаторни конфигурации 47
2.3 Производящи функции и рекурентни отношения 52
2.4 Комбинаторни конфигурации в наредени множества 56
2.5 Крайни геометрии и блок-дизайни 60
2.6 Дискретна вероятност 67
Упражнения 73
3 Крайни графи и мултиграфи 79
3.1 Основни понятия 79
3.2 Дървета 86
3.3 Обхождане на графи 93
3.4 Оптимизационни задачи в графи 101
Упражнения 114
4 Формални езици и абстрактни машини 119
4.1 Формални езици и граматики 119
4.2 Автоматни езици 128
4.2.1 Свойства на автоматните езици 129
4.2.2 Крайни автомати 134
4.2.3 Регулярни изрази и езици 142
4.2.4 Минимизация на КДА 145
4.2.5 ЦУЧУ-Теорема 152
4.3 Контекстно-свободни езици 154
4.3.1 Дърво на извод на КСГ 154
4.3.2 Недетерминирани стекови автомати 160
4.3.3 Нормални форми на КСГ 169
4.3.4 хуиу\у-Теорема 173
Упражнения 175
5 Дискретни функции 179
5.1 Суперпозиция и формули 179
5.2 Булеви (двоични) функции 187
5.3 Пълни множества от функции 192
5.4 Затворени множества от функции 197
5.4.1 Булеви функции, запазващи константите 199
5.4.2 Самодвойнствени булеви функции 199
5.4.3 Монотонни булеви функции 203
5.4.4 Линейни функции 205
5.5 Критерий за пълнота на множество булеви функции 206
5.6 Задача за минималните покрития 210
5.7 Схеми от функционални елементи 213
5.8 Минимизация на булеви функции 224
Упражнения 231
6 Кодиране на информацията 237
6.1 Побуквено кодиране 238
6.2 Оптимално побуквено кодиране 242
6.3 Шумозащитно кодиране 252
6.4 Криптология 264
6.4.1 Криптосистеми с общ ключ 265
6.4.2 Криптосистеми с публичен ключ 273
Упражнения 280
7 Масови задачи и алгоритми 285
7.1 Масови задачи 285
7.2 Алгоритми и разрешимост на масови задачи 288
7.3 Машини на Тюринг 290
7.4 Неразрешими масови задачи 300
7.5 Сложност на алгоритми и масови задачи 303
7.6 Универсална машина на Тюринг 312
Упражнения 314
Литература 319
Предметен указател 322
Списък на таблиците 333
Списък на илюстрациите 335
