Дискретная математика : теория и практика решения задач по информатике: учебное пособие

Автор: Окулов С. М.

Предмет: Информатика
Математика

Год издания: 2020

Серия: Педагогическое образование

Класс: 10 класс 11 класс

Издательство: Лаборатория знаний

Возрастное ограничение: 12+

Объем (стр.): 425

Постраничный просмотр для данной книги Вам недоступен.
Оплатить доступ к режиму онлайн-чтения.

Книга доступна только по дополнительной подписке.

Узнать подробнее

Книга находится в издательской коллекции:

Коллекция издательства «Лаборатория знаний» «Информационные технологии»

Аннотация / Содержание / Библиографическое описание

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

Предисловие	7
Глава 1. Основные методы дискретной математики (счет и перебор)	10
1.1. Счет и перебор	10
1.2. Асимптотические обозначения и основная теорема	17
1.3. Эффект «комбинаторного взрыва»	20
Упражнения и задачи	22
Комментарии	24
Глава 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
Комментарии	51
Глава 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
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
Глава 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

Дискретная математика : теория и практика решения задач по информатике: учебное пособие

Дополнительные материалы к этой книге

Рекомендуем посмотреть