Бунаков П. Ю.
Содержит материалы по отдельным разделам дискретной математики: теории множеств, комбинаторике, дискретной теории вероятностей, теории графов, теории алгоритмов и теории конечных автоматов. Имеет практическую направленность и помимо теоретических сведений включает задачи для решения и лабораторные работы по программированию на языке Python. Особое внимание уделяется разбору примеров решения задач и написания программ, а также самостоятельной работе обучающихся, для чего каждая тема сопровождается дополнительными заданиями. Для студентов высших учебных заведений, изучающих основы дискретной математики. Будет полезно студентам средних специальных учебных заведений, школьникам старших классов и всем интересующимся вопросами дискретной математики и программирования.
Введение 5
1. Множества 8
1.1. Кванторы и специальные математические символы 8
1.2. Основные понятия теории множеств 9
1.3. Способы задания множеств 11
1.4. Операции над множествами 13
1.5. Покрытие множества 18
1.6. Отображения, соответствия и отношения множеств 19
1.7. Способы задания отношений 26
1.8. Практическая часть 27
1.9. Лабораторный практикум 35
Вопросы для повторения 42
2. Комбинаторика 44
2.1. Основные понятия комбинаторики 45
2.2. Перестановки, сочетания и размещения 47
2.3. Биноминальные коэффициенты 51
2.4. Практическая часть 54
2.5. Лабораторный практикум 58
Вопросы для повторения 62
3. Математическая логика 64
3.1. Логика высказываний 65
3.2. Логические операции над высказываниями 65
3.3. Булевы функции 67
3.4. Нормальные формы 70
3.5. Карты Карно 74
3.6. Логический базис 78
3.7. Практическая часть 84
3.8. Лабораторный практикум 90
Вопросы для повторения 95
4. Дискретная теория вероятностей 96
4.1. События 97
4.2. Алгебра событий 101
4.3. Вероятность события 102
4.4. Условная вероятность события и умножение вероятностей 111
4.5. Сложение вероятностей 113
4.6. Формула полной вероятности 117
4.7. Формула Байеса 119
4.8. Повторные независимые испытания 123
4.9. Дискретные случайные величины 128
4.10. Числовые характеристики дискретных случайных величин 131
4.11. Практическая часть 136
4.12. Лабораторный практикум 154
Вопросы для повторения 167
5. Основы теории графов 169
5.1. Основные понятия теории графов 170
5.2. Типы графов 173
5.3. Операции над графами 175
5.4. Способы задания графов 177
5.5. Связность графов 180
5.6. Деревья 185
5.7. Поиск путей в графе 189
5.8. Циклы в графе 191
5.9. Поиск кратчайших путей в графе 196
5.10. Практическая часть 202
5.11. Лабораторный практикум 220
Вопросы для повторения 243
6. Теория алгоритмов 244
6.1. Формальное определение и свойства алгоритма 244
6.2. Способы представления алгоритмов 248
6.3. Типы моделей алгоритмов 250
6.3.1. Алгоритмические машины 250
6.3.2. Нормальный алгоритм Маркова 252
6.3.3. Рекурсивные функции 255
6.4. Рекурсивные функции 258
6.5. Лямбда-исчисление 260
6.6. Введение в теорию сложности алгоритмов 266
6.7. Практическая часть 269
Вопросы для повторения 278
7. Введение в теорию конечных автоматов 279
7.1. Основные понятия 279
7.2. Автоматное программирование 283
7.3. Лабораторный практикум 286
Вопросы для повторения 289
Библиографический список 290
