Комбинаторика для программистов
- Автор(ы)
- Липский В
- Год
- 1988
- Издательство
- Мир
- Язык
- rus
- ISBN
- 5-03-000979-5
- Библиографическая ссылка
- М.: Мир, 1988. —213 с.
- Теги
- Компьютеры и информационные технологии Математика Программирование
Аннотация
Комбинаторика для программистов Год издания : 1988 Автор : Липский В. Переводчик : Евстигнеев В.А., Логинова О.А. Жанр или тематика : Математика Издательство : Мир ISBN : 5-03-000979-5 Язык : Русский Формат : DjVu Качество : Отсканированные страницы + слой распознанного текста Интерактивное оглавление : Нет Количество страниц : 217 Описание : Аннотация: «Книга польского специалиста по программированию знакомит читателей с широким спектром комбинаторных и теоретико-графовых алгоритмов. Описание алгоритмов дано на языке Паскаль; стиль изложения близок к справочному — постановка задачи, алгоритм ее решения, комментарии, трудоемкость, примеры. Русское издание дополнено новыми результатами. Для специалистов в области информатики, исследования операций, методов оптимизации, а также для студентов вузов как учебное пособие». Книгу отсканировал, обработал и предоставил для раздачи krius1 . Опубликовано группой OCR здесь . Примеры страниц Оглавление Предисловие редактора перевода 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