URSS.ru Магазин научной книги
Обложка Липский В. __Комбинаторика для программистов: Пер. с польск.
Id: 234265
899 р.

Комбинаторика для программистов:
Пер. с польск.

1988. 216 с. ISBN 5-03-000979-5. Букинист. Состояние: 4+. Погашенная библиотечная печать.
  • Мягкая обложка

Аннотация

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


Оглавление
top

Предисловие редактора перевода................ 5

От автора.........................7

1. Введение в комбинаторику................. 9

1.1. Основные понятия................... 9

1.2. Функции и размещения.................. 14

1.3. Перестановки: разложение на циклы, знак перестановки..... 17

1.4. Генерирование перестановок................ 24

1.5. Подмножества множества, множества с повторениями, генерирование подмножеств множества................ 34

1.6. 6-элементные подмножества, биномиальные коэффициенты.... 39

1.7. Генерирование й-элементных подмножеств........... 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