Аддитивность задач, или динамическое программирование 101 Упражнения и задачи . <...> Понятие графа, основные методы просмотра вершин графа 111 5.1. <...> Математические факты и доказательства отдельных теорем . <...> Для вычисления и хранения чисел такого порядка в компьютере использовать величину типа Integer нельзя. <...> Следовательно, общее количество способов выбора k элементов есть Ci i=0 k Из формулы Ck нию n=0,вторая—n=1 и т. д. <...> Количество способов выбрать k скобок из n равно Ck n. <...> Сумма элементов в таблице инверсий равна 5. <...> Подсчитаем количество перестановок, в которых ровно один элемент находится на своем месте. <...> Без учета повторений количество перестановок равно n! <...> Разбиение числа на слагаемые Дано натуральное число n. <...> Иллюстрация к задаче 2.49 B(7B(7B(7 ГЛАВА 3 ПЕРЕЧИСЛЕНИЕ КОМБИНАТОРНЫХ ОБЪЕКТОВ 3.1. <...> Если отношение порядка определено, т. е. для каждого объекта можно сказать, какой предшествует ему и какой следует за ним, то общая схема генерации объектов независимо от их типа (размещения, сочетания, перестановки) имеет следующий вид: Procedure GetAll; Var tt:<тип tt>; {Переменная tt описывает комбинаторный объект} Begin <сформировать начальный объект tb>; <сформировать конечный объект te>; tt:=tb; <вывести или запомнить значение tt>; While tt<>te Do Begin tt:=<следующий в соответствии с введенным отношением порядка комбинаторный объект>; <вывести или запомнить значение tt>; End; End; Основная часть логики «зарыта» в процедуре получения следующего (в соответствии с введенным отношением порядка) комбинаторного объекта. <...> Лексикографический порядок намножестве всех перестановок определяется следующим образом. <...> 3.1 перечислены перестановки в лексикографическом порядке и указаны их номера в соответствии с принципом перечисления. <...> Генерация сочетаний без повторений Отношение лексикографического порядка на множестве сочетаний определяется так же, как и для перестановок. <...> Сочетания в лексикографическом порядке (хранятся в массиве A)приведены в табл. <...> Генерация размещений без повторений <...>
Дискретная_математика._Теория_и практика_решения_задач_по информатике.pdf
ПЕДАГОГИЧЕСКОЕ ОБРАЗОВАНИЕ
С. М. Окулов
ДИСКРЕТНАЯ МАТЕМАТИКА
ТЕОРИЯ И ПРАКТИКА
РЕШЕНИЯ ЗАДАЧ ПО ИНФОРМАТИКЕ
Учебное пособие
4е издание, электронное
Москва
Лаборатория знаний
2020
Стр.2
УДК 519.85(075)
ББК 22.174я7
О-52
С е р и я о с н о в а н а в 2007 г.
Рецензенты:
академик РАО, доктор педагогических наук, профессор А. А. Кузнецов
доктор технических наук, профессор В. Н. Комаров
Окулов С. М.
О-52
Дискретная математика. Теория и практика решения задач
по информатике : учебное пособие / С. М. Окулов. — 4-е изд.,
электрон. — М. : Лаборатория знаний, 2020. — 425 с. — (Педагогическое
образование). — Систем. требования: Adobe Reader XI ;
экран 10".— Загл. с титул. экрана. — Текст : электронный.
ISBN 978-5-00101-684-7
В учебном пособии даны ключевые разделы дискретной математики
с практической реализацией алгоритмических решений. Книга написана
на основе лекционного курса и практических занятий для студентов факультета
информатики Вятского государственного гуманитарного университета,
а также спецкурса, читаемого автором для школьников, занимающихся
информатикой по углубленной программе.
Для студентов высших учебных заведений, а также старшеклассников,
углубленно изучающих информатику.
УДК 519.85(075)
ББК 22.174я7
Деривативное издание на основе печатного аналога: Дискретная математика.
Теория и практика решения задач по информатике : учебное пособие /
С. М. Окулов. — М. : БИНОМ. Лаборатория знаний, 2008. — 422 с. : ил. —
(Педагогическое образование). — ISBN 978-5-94774-498-9.
В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений,
установленных техническими средствами защиты авторских прав,
правообладатель вправе требовать от нарушителя возмещения убытков
или выплаты компенсации
ISBN 978-5-00101-684-7
○c Лаборатория знаний, 2015
Стр.3
ОГЛАВЛЕНИЕ
Предисловие . . . . . . . . . . . . . . . . . . . . . . .
7
Глава 1. Основные методы дискретной математики (счет и перебор) 10
1.1. Счет и перебор . . . . . . . . . . . . . . . . . . 10
1.2. Асимптотические обозначения и основная теорема . . 17
1.3. Эффект ≪
комбинаторного взрыва≫
. . . . . . . . . . 20
Упражнения и задачи . . . . . . . . . . . . . . . . 22
Комментарии
Глава 2. Основные комбинаторные принципы и понятия в примерах 25
2.1. Принципы сложения и умножения . . . . . . . . . 25
2.2. Подмножества . . . . . . . . . . . . . . . . . . . 25
2.3. Принцип включения и исключения . . . . . . . . . 26
2.4. Выборки . . . . . . . . . . . . . . . . . . . . . 28
2.5. Размещения с повторениями . . . . . . . . . . . . 28
2.6. Размещения без повторений . . . . . . . . . . . . 29
2.7. Сочетания без повторений . . . . . . . . . . . . . 30
2.8. Бином Ньютона и полиномиальная формула (комбинаторный
смысл) . . . . . . . . . . . . . . . . . . . 32
2.9. Сочетания с повторениями . . . . . . . . . . . . . 33
2.10. Перестановки без повторений . . . . . . . . . . . . 33
2.11. Перестановки с повторениями . . . . . . . . . . . 38
2.12. Задача о размещениях . . . . . . . . . . . . . . . 39
2.13. Разбиения . . . . . . . . . . . . . . . . . . . . . 42
2.14. Разбиения на циклы . . . . . . . . . . . . . . . . 43
2.15. Разбиение числа на слагаемые . . . . . . . . . . . 45
Упражнения и задачи . . . . . . . . . . . . . . . . 46
Комментарии
. . . . . . . . . . . . . . . . . . . 24
. . . . . . . . . . . . . . . . . . . 51
Стр.4
4
Оглавление
Глава 3. Перечисление комбинаторных объектов . . . . . . . 52
3.1. Общая схема генерации комбинаторных объектов . . 52
3.2. Генерация перестановок без повторений . . . . . . . 53
3.3. Генерация сочетаний без повторений . . . . . . . . 54
3.4. Генерация размещений без повторений . . . . . . . 55
3.5. Генерация перестановок с повторениями . . . . . . 57
3.6. Генерация сочетаний с повторениями . . . . . . . . 57
3.7. Генерация размещений с повторениями . . . . . . . 57
3.8. Генерация подмножеств . . . . . . . . . . . . . . 58
3.9. Генерация разбиений . . . . . . . . . . . . . . . . 60
3.10. Генерация разбиений на циклы . . . . . . . . . . . 66
3.11. Генерация разбиений числа на слагаемые . . . . . . 73
Упражнения и задачи . . . . . . . . . . . . . . . . 74
Комментарии
. . . . . . . . . . . . . . . . . . . 75
Глава 4. Рекуррентные и нерекуррентные формулы . . . . . . 76
4.1. Простые примеры . . . . . . . . . . . . . . . . . 76
4.2. Числа Фибоначчи . . . . . . . . . . . . . . . . . 77
4.3. Числа Каталана . . . . . . . . . . . . . . . . . . 82
4.4. Схема нахождения общего решения линейных рекуррентных
уравнений . . . . . . . . . . . . . . . . 86
4.5. Производящие функции . . . . . . . . . . . . . . 90
4.6. Ладейные полиномы . . . . . . . . . . . . . . . . 97
4.7. Аддитивность задач, или динамическое программирование 101
Упражнения и задачи . . . . . . . . . . . . . . . . 106
Комментарии
. . . . . . . . . . . . . . . . . . . 110
Глава 5. Понятие графа, основные методы просмотра вершин графа 111
5.1. Терминология . . . . . . . . . . . . . . . . . . . 111
5.2. Способы представления графа . . . . . . . . . . . 112
5.3. Поиск в глубину . . . . . . . . . . . . . . . . . . 114
5.4. Поиск в ширину . . . . . . . . . . . . . . . . . . 116
5.5. Основные понятия . . . . . . . . . . . . . . . . . 117
Упражнения и задачи . . . . . . . . . . . . . . . . 124
Комментарии
. . . . . . . . . . . . . . . . . . . 129
Глава 6. Деревья . . . . . . . . . . . . . . . . . . . . . 130
6.1. Определение дерева . . . . . . . . . . . . . . . . 130
6.2. Перечисление остовных деревьев связного помеченного
графа . . . . . . . . . . . . . . . . . . . . . . . 131
6.3. Матричная формула Кирхгофа . . . . . . . . . . . 134
Стр.5
Оглавление
5
6.4. Алгоритм представления дерева в виде последовательности
чисел . . . . . . . . . . . . . . . . . . . . . 135
6.5. Остовные деревья минимального веса . . . . . . . . 137
6.6. Задача Штейнера . . . . . . . . . . . . . . . . . 141
Упражнения и задачи . . . . . . . . . . . . . . . . 143
Комментарии
. . . . . . . . . . . . . . . . . . . 144
Глава 7. Связность . . . . . . . . . . . . . . . . . . . . 145
7.1. Вершинная и реберная связность . . . . . . . . . . 145
7.2. Метод нахождения блоков графа . . . . . . . . . . 147
7.3. Теорема Менгера . . . . . . . . . . . . . . . . . 149
7.4. Связность в орграфе . . . . . . . . . . . . . . . . 151
Упражнения и задачи . . . . . . . . . . . . . . . . 154
Комментарии
. . . . . . . . . . . . . . . . . . . 155
Глава 8. Циклы . . . . . . . . . . . . . . . . . . . . . 156
8.1. Эйлеровы графы . . . . . . . . . . . . . . . . . . 156
8.2. Гамильтоновы графы . . . . . . . . . . . . . . . . 158
8.3. Фундаментальное множество циклов . . . . . . . . 161
8.4. Матроиды . . . . . . . . . . . . . . . . . . . . . 166
Упражнения и задачи . . . . . . . . . . . . . . . . 172
Комментарии
. . . . . . . . . . . . . . . . . . . 173
Глава 9. Покрытия и независимость . . . . . . . . . . . . 174
9.1. Основные понятия . . . . . . . . . . . . . . . . . 174
9.2. Метод генерации всех максимальных независимых множеств
вершин графа . . . . . . . . . . . . . . . . 175
9.3. Клики . . . . . . . . . . . . . . . . . . . . . . 179
9.4. Доминирующие множества . . . . . . . . . . . . . 180
9.5. Паросочетания . . . . . . . . . . . . . . . . . . . 185
9.6. Матроиды трансверсалей . . . . . . . . . . . . . . 196
9.7. Диаграмма взаимосвязей между задачами . . . . . . 198
Упражнения и задачи . . . . . . . . . . . . . . . . 201
Комментарии
. . . . . . . . . . . . . . . . . . . 203
Глава 10. Планарные графы . . . . . . . . . . . . . . . . 204
10.1. Основные понятия . . . . . . . . . . . . . . . . . 204
10.2. Формула Эйлера . . . . . . . . . . . . . . . . . . 204
10.3. Алгоритм укладки графа на плоскости . . . . . . . . 206
Упражнения и задачи . . . . . . . . . . . . . . . . 214
Комментарии
. . . . . . . . . . . . . . . . . . . 215
Стр.6
6
Оглавление
Глава 11. Раскраска вершин графа . . . . . . . . . . . . . 216
11.1. Хроматическое число . . . . . . . . . . . . . . . . 216
11.2. Метод правильной раскраски . . . . . . . . . . . . 217
11.3. Методы поиска минимальной раскраски . . . . . . . 219
Упражнения и задачи . . . . . . . . . . . . . . . . 222
Комментарии
. . . . . . . . . . . . . . . . . . . 223
Глава 12. Кратчайшие пути в графе . . . . . . . . . . . . 224
12.1. Постановка задачи. Вывод пути . . . . . . . . . . . 224
12.2. Алгоритмы поиска кратчайших путей . . . . . . . . 226
Упражнения и задачи . . . . . . . . . . . . . . . . 234
Комментарии
. . . . . . . . . . . . . . . . . . . 235
Глава 13. Потоки в сетях . . . . . . . . . . . . . . . . . 236
13.1. Основные понятия и постановка задачи . . . . . . . 236
13.2. Алгоритм К. Эдмондса—Р. Карпа . . . . . . . . . . 237
13.3. Введение в метод блокирующих потоков или алгоритм
Е. А. Диница . . . . . . . . . . . . . . . . . . . 244
13.4. Модификация алгоритма Е. А. Диница . . . . . . . 252
Упражнения и задачи . . . . . . . . . . . . . . . . 260
Комментарии
. . . . . . . . . . . . . . . . . . . 262
Ответы и решения . . . . . . . . . . . . . . . . . . . . 263
Задачи для самостоятельного решения . . . . . . . . . . . 353
П р и л о ж е н и е 1. Математические факты и доказательства
отдельных теорем . . . . . . . . . . . . . . . . . 375
П р и л о ж е н и е 2. Описание основных элементов языков
программирования Паскаль, визуального Бейсика и С++ 396
Литература . . . . . . . . . . . . . . . . . . . . . . . 414
Предметный указатель . . . . . . . . . . . . . . . . . . 416
Стр.7