Лучшее в категории - Книги / Научная литература

25
апр
2019

Комбинаторика для программистов (1988, Липский В.)

Год издания: 1988
Автор: Липский В.
Переводчик: Евстигнеев В.А., Логинова О.А.
Жанр или тематика: Математика
Издательство: Мир
ISBN: 5-03-000979-5
Язык: Русский
Формат: DjVu
Качество: Отсканированные страницы + слой распознанного текста
Количество страниц: 217

Описание: «Книга польского специалиста по программированию знакомит читателей с широким спектром комбинаторных и теоретико-графовых алгоритмов. Описание алгоритмов дано на языке Паскаль; стиль изложения близок к справочному — постановка задачи, алгоритм ее решения, комментарии, трудоемкость, примеры. Русское издание дополнено новыми результатами.
Для специалистов в области информатики, исследования операций, методов оптимизации, а также для студентов вузов как учебное пособие».

Примеры страниц

Оглавление

Предисловие редактора перевода 5
От автора 7
1. Введение в комбинаторику 9
1.1. Основные понятия 9
1.2. Функции и размещения 14
1.3. Перестановки: разложение на циклы, знак перестановки 17
1.4. Генерирование перестановок 24
1.5. Подмножества множества, множества с повторениями, генерирование подмножеств множества 34
1.6. k-элементные подмножества, биномиальные коэффициенты .... 39
1.7. Генерирование k-элементных подмножеств 45
1.8. Разбиения множества 48
1.9. Числа Стирлинга второго и первого рода 50
1.10. Генерирование разбиений множества 55
1.11. Разбиения чисел 60
1.12. Производящие функции 64
1.13. Принцип включения и исключения 72
1.14. Задачи 76
2. Алгоритмы на графах 84
2.1. Машинное представление графов 84
2.2. Поиск в глубину в графе 88
2.3. Поиск в ширину в графе 92
2.4. Стягивающие деревья (каркасы) 94
2.5. Отыскание фундаментального множества циклов в графе 98
2.6. Нахождение компонент двусвязности 101
2.7. Эйлеровы пути 106
2 8. Алгоритмы с возвратом 108
2.9. Задачи 114
3. Нахождение кратчайших путей в графе 119
3.1. Начальные понятия 119
3.2. Кратчайшие пути от фиксированной вершины 121
3.3. Случай неотрицательных весов — алгоритм Дейкстры 124
3.4. Пути в бесконтурном графе 127
3.5. Кратчайшие пути между всеми парами вершин, транзитивное замыкание отношения 130
3.6. Задачи 134
4. Потоки в сетях и родственные задачи 136
4.1. Максимальный поток в сети 136
4.2. Алгоритм построения максимального потока 141
4.3. Наибольшие паросочетания в двудольных графах 154
4.4. Системы различных представителей 163
4.5. Разложение на цепи 172
4.6. Задачи 178
5. Матроиды 183
5.1. Жадные алгоритмы решения оптимизационных задач 183
5.2. Матроиды и их основные свойства 185
5.3. Теорема Радо — Эдмондса 190
5.4. Матричные матроиды 193
5.5. Графовые матроиды 195
5.6. Матроиды трансверсалей 199
5.7. Задачи 202
Литература 205
Указатель 203